IPSC Logo

Internet Problem Solving Contest

Archive

This is the list of problems from all past IPSC contests.

Please note that all IPSC problems are licensed under the CC BY-SA 3.0 license.

IPSC 2013 IPSC 2013 problems and solutions booklet
Advice for Olivia
Pay a sum using sufficiently few coins and banknotes.
Boredom buster
Find the best way of breaking a number into ones.
Code Inception
Analyze programs that output instructions how to modify them.
Do the grading
Write a grader for the practice task R.
Exploring the cave
Find a NFA with n states such that the corresponding DFA has d states.
Feeling lucky?
Play a weighing game that involves randomness.
Solutions: Booklet.
Grid travel
Find the longest path from A to B on a rectangular grid.
Histiaeus
Locate a hidden message carried by a slave.
Invisible cats
Descramble a collection of images and find all cats.
Just a single gate
Find all universal ternary gates.
Knee problems
Count the ways of walking up and down the stairs.
Labyrinth
Find your way through a seemingly simple labyrinth with buttons.
Morning hassle
Find the fastest way to drive your car over railroad crossings.
IPSC 2013 practice session  
Plus one
Increment the given number by 1... with a twist!
Quite the cheater!
Find a sequence with a given mean and a given variance.
Rearranged alphabet
Find a short string that contains each permutation as a subsequence.
IPSC 2012 IPSC 2012 problems and solutions booklet
Abundance of sweets
Look for all candies in a matrix of characters.
(blank)
Solve a task with no problem statement, using just the messages from the grader.
Card game
Find the best strategy in a card game involving probability.
Data mania
Answer queries about data from past years of IPSC.
Evil matching
Solve a pattern matching problem in which we can add adjacent elements of text.
Fair coin toss
Try to simulate a fair coin by xor-ing biased ones.
Gems in the maze
Find the longest path in a graph with outdegree 1.
Harvesting potatoes
Plan the optimal schedule for a harvester.
Invert the you-know-what
Recover a password from a related MD5 hash.
Jukebox
Convert a recording of a simple song into musical notes.
Keys and locks
Determine the master key for a pin tumbler lock.
Light in a room
Compute the area lit by a cone of light in a room.
Matrix nightmare
Given a polynomial, find a matrix such that its determinant is the given polynomial.
IPSC 2012 practice session  
Partitioning containers
Split numbers with sum S into two subsets of size at most S/2 and possibly one extra element.
Solutions: Booklet.
Quaint encryption
Find one alphabet permutation consistent with a given substitution cipher.
Solutions: Booklet.
Rebel Alliance attacks
In a sphere, find all grid points with integer distance to the center.
Solutions: Booklet.
IPSC 2011 IPSC 2011 problems and solutions booklet
Against a rock play Spock
Always win in a Rock-Paper-Scissors-Lizard-Spock game.
BFS killer
Find a maze for which BFS needs a long queue.
Candy for each guess
Find the optimal strategies for 'binary search' played as a game.
Divide the rectangle
Divide a rectangle into two equal parts, each containing one given cell.
Elementary math
Compute square roots of numbers and format the output nicely.
Flipping coins
Find the optimal strategy in a puzzle about guessing your coin without seeing it.
Grid surveillance
Find a persistent data structure that supports additions and rectangle queries.
HQ0-9+-INCOMPUTABLE?!
Write a program that outputs your TIS in a very unfriendly language.
Inverting bits
Compute the negations of many bits using few NOTs.
Jedi academy
Compute lots of ray-object intersections.
Keep clicking, keep flipping
Play a game on a graph in which you flip vertex colors and adjacent edges.
Lame crypto
Break a cryptographic protocol in 'real time'.
Solutions: Booklet.
My little puppy
Take care of a virtual puppy for some bonus time.
Solutions: Booklet.
IPSC 2011 practice session  
Pancakes!
Maximize the number of pancakes given the resources you have.
Quality of Service
Assemble the problem statement from many sparse parts.
Solutions: Booklet, output checker.
Rotate to divide
Find a number that gets divided by K when we rotate it.
IPSC 2010 IPSC 2010 problems and solutions booklet
Antisort
Do NOT sort the input sequence.
Broadway
Find the shortest path in Manhattan that includes the Broadway.
Cells
Evaluate spreadsheet cells.
Dragon Slayer
Kill a magic dragon using two magic swords.
Eyjafjallajökull
Find the vulcano by making online measurements of the ash cloud.
Flawed Code
Find inputs for which incorrect greedy algorithms fail.
Grid is good
Draw a binary tree into a small grid.
Hash
Invert two hashes that use MD5 incorrectly.
Inside job
For a dart thrown onto a polygon, compute the expected sum of distances from the dart to all its sides.
Jimmy the Acting Teacher
Create a schedule of meetings where each pair meets once.
Klingon High Council Training
Find the optimal strategy for a game played with ships in a 3D grid.
Lovely stamps
Compute the number of ways in which some stamps can be bought.
Mass psychoanalysis
Guess two thirds of the average of all guesses.
Solutions: Booklet.
IPSC 2010 practice session  
Piece of cake!
Cut a cake shaped like a box in a way that leaves the largest uncut part.
Quick growth
Memory is being filled by multiplying arrays, compute the sum of all elements.
Round and round it goes
Find constants that turn the given program into the best infinite loop.
IPSC 2009 IPSC 2009 problems and solutions booklet
Arithmetics for dummies
Find the result of an expression computed on an oldschool calculator.
Bouncing balls
Find the state of a box full of bouncing balls.
Cryptic punchcards
Read text stored on punchcards.
Don't worry about wrong answers
A weird problem in which almost any submission is accepted.
Easy representation
Compute area of a pictorial representation of a correctly parentesized string.
Fish Fillets
Solve two new levels of the Fish Fillets puzzle.
Solutions: Solution, Booklet.
Going to the movies
Compute the probability that all girls will find a place to sit at the cinema.
Hunt!
Direct wolves to hunt sheep in real time.
Solutions: Solution, Booklet.
Instructions
Implement '+8' and 'next with same popcount' using a very restricted assembler.
Jumbo Airlines
Compute the number of ways of seating people in an airplane.
Karl's shopping
Find the smallest amount of additional cash needed when paying by various vouchers.
Let there be rainbows!
A tree is being colored using 7 colors, construct its final state.
Muzidabutur
Match regular expressions that are written in verbose English.
IPSC 2009 practice session  
Pathfinding
Given a maze, find a reasonably short solution.
Solutions: Solution, Booklet.
Quick search
Given a rectangle divided into polygons, find two identical ones.
Input files: Easy input, Hard input.
Solutions: Solution, Booklet.
Reverse quick search
Create valid test data for problem 'Quick search'.
Solutions: Solution, Booklet.
IPSC 2008  
Army Strength
Find the winner in a battle of two armies where the weakest unit always gets killed.
Breaking in
Find the server that gives you the most access when compromised.
Comparison Mysteries
Show that x==-x has a nontrivial solution in ints, and that equality is not transitive.
Solutions: Solution.
Discover All Sets
Play a generalized version of the game Sets.
Expected Cost
Compute the expected cost of a minimum spanning tree for a graph with random edge weights.
Find the Meaning
A message is somehow hidden in the input file, find it.
Game on Words
In real time, play against us a game where the players extend a string until it becomes a word.
Hidden Text
Show that blurred text can be recovered if you know the font.
Inventing Test Data
Given a weighted tree T, find the lightest complete graph for which T is the only MST.
Just a Single Lie
Find the optimal strategy in a number guessing game where you may receive a single lie.
K Equal Digits
Find the largest number with all digits equal that matches a set of criteria.
Large party
Count the ways in which men and women can sit at a table if large clusters of women are forbidden.
IPSC 2008 practice session  
Perfect Rhyme
Given a word, find another word that is the best rhyme.
Quiz
Answer all trivia questions about the history of IPSC correctly.
Railroad Map
Given a graph, replace all non-branching paths by direct edges.
IPSC 2007  
Anti-Blot System
Fix a simple equation that has a ink blot covering part of a number.
Bus Story
Check whether a story about passengers boarding and leaving a bus may be true.
Calling Me Calling You
Purchase enough free numbers to allow a group of friends call each other for free.
Delicious Cake
Count the ways of cutting a rectangular cake into pieces.
Enhancing IPSC Rules
Given a rock-paper-scissors game as a set of pictures, compute who won.
Finally some Sudoku
Solve several Sudoku instances that share some of their values.
Input files: Easy input, Hard input.
Guess the Numbers
In real time, guess a sequence by choosing another and getting their scalar product.
Solutions: Solution.
Here-There
Find the shortest path on a fractal board.
Internet is Faulty
Minimize the expected transfer time via a network with faulty links.
jPix
Draw lines and compute area reached by a flood fill on a huge grid.
Know Your Crypto
Solve a simple cipher and reverse a seemingly random one.
Little Peter's Tower
Maximize the expected height of a tower built from randomly drawn blocks.
IPSC 2007 practice session  
Paradox With Averages
If a person moves from group A to group B, the average IQ of both groups may increase.
QuackQuack
Factorize and duplicate the queue in our special queue-based scripting language.
Rasterized Lines
Given N, in how many ways can one draw a rasterized line segment with N black pixels?
IPSC 2006  
Another Candies
Kids brought candies, divide them evenly.
Biased Standings
Given the teams' wishes, produce a ranklist that matches them as closely as possible.
Counting Subsequences
Count all contiguous subsequences with sum equal to 47.
Digital Calculator
Compute the first few and the last few digits of a factorial.
Encoded Messages
Decrypt a permutation cipher and a substitution cipher.
Fractal Plants
Find the center of mass of a fractal plant.
Gotta Pick'em All
Count the largest subsets of {1,...,n} in which no two elements sum to a third one.
Input files: Input data set – G.
h4x0r t3h c0d3
Compute a discrete logarithm in a restricted setting, and create two PostScript files with the same MD5 sum.
Ideal Matches
Cover a complete graph by Hamiltonian cycles that intersect in a fixed matching.
Jamcode 2006
Given a task and a wrong program, find an input for which the program works.
Kruskal
Find the optimal strategy for a NIM variant where creating a prime-sized heap wins the game.
Librarian
Create a sequence of page requests that would produce more page faults if cache size is increased slightly.
Matrioska
Get the correct answer out of multiple nested file formats.
Solutions: Solution.
IPSC 2006 practice session  
Santos Apples
Divide a garden into two equal parts, each containing trees of a single type.
Labyrinth
Simulate a robot in a simple maze.
Medical Research
Given a sequence of numbers, answer queries about the k-th smalest one.
IPSC 2005  
Alpha Centauri Tennis
Given a transcript of a tennis match, find out who won.
Bottom Coder
Alter code so that it creates a specific output.
Crane Operator
Given a crane and a set of boxes, compute the boxes' final positions and move them using fewest moves possible.
Dance Dance Revolution
Catch as many arrows as possible in a DDR game.
Exact? Approximate!
Given a decimal number, produce the simplest fraction that evaluates to that decimal after appropriate rounding.
Find The Right Words
Given a set of words, assign one to each letter of the alphabet so that each word contains its letter and the total length is minimal.
Gears In Action
Compute the time until a system of gears reaches a given configuration.
Hidden Messages
Decrypt two pen-and-paper ciphers.
Solutions: Solution.
Ignore the Garbage
Given an upside-down digital display, find the k-th number that makes sense.
Just for Fun
Solve logic puzzles for bonus time.
Solutions: Solution.
IPSC 2005 practice session  
Polly Wanna Cracker
Divide crackers among parrots evenly and report the exact outcome.
Quack Strikes Back
Compute Fibonacci numbers and write a backwards-quine in our queue-based scripting language.
Solutions: Solution.
Rotate And Cut
Given a string, several times cut one quarter of it off.
IPSC 2004  
Andrew's revenge
Given a program and its output, find one matching input.
Bishops
Place the maximum number of bishops on a generalized chessboard.
Calls
Given a matrix of integers, check whether it is a shortest distances matrix for some graph.
Delayed search
In real time, guess a number using yes/no questions, with each answer coming only after several questions.
Solutions: Solution.
Electrical Circuits
Count the number of perfect matchings in special graphs.
Fat Rat
Can a sphere fit through a given pipe with obstacles?
Gets and Puts
Write a sorting program and a quine in our queue-based scripting language.
Hard Question – P=NP?
Given a polygon and a set of non-intersecting rectangles, does a subset of rectangles exactly match the polygon?
IPSC 2004 practice session  
Dependency Problems
Given package dependencies and availability, install as many as possible.
Censored Smiles
Count all smiling faces in a large picture.
The Tiling Problem
Tile a given floor using 2 by 1 tiles.
IPSC 2003  
Arranging Flowers
Reconstruct the missing rows of a Latin square.
begin 4 7 add
Analyze and modify code written in PostScript.
Cinderella
Using a digital scale, interactively identify the bag with false coins.
Solutions: Solution.
Dependency Problems
Given package dependencies and availability, install as many as possible.
Enchanted Forest
Find the smallest number of flood fills necessary to recolor a 0/1 matrix to a single color.
Folding the Paper
Can a strip of paper squares be folded into the given order?
Got Root?
Find the optimal strategy for a Hackenbush variant.
Hordes of Bacteria
Simulate lots of iterations of a growing bacteria colony.
IPSC 2003 practice session  
Candies
Separate three candy flavors by moving as few of them as possible.
Colorful Cubes
Given cubes with colored sides, assemble a tower in which pairs of touching sides match.
Strange Numbers
Convert integers between binary and our ad-hoc encoding.
IPSC 2002  
Andews's Exams III
Given a program, find an input for which it terminates quickly.
Load Balancing
Find the smallest amount of rounds necessary to rebalance the load for a row of processors.
Chamber of Secrets
By observing a digital display with a counter few segments at a time, interactively determine its value.
Space Suckers
Given a graph where each vertex has a set of properties, find a Hamiltonian path such that each property is contiguous.
Expressions
Express the given number as an expression that uses as few 1s as possible.
(un)Fair Play
Given a league in progress, find out whether a given team can still win it.
Gardening
Find the smallest axes-parallel square that contains at least one half of the given points.
Equatorial Bonfire
A set of bonfires is started along the equator, find the time when all the equator is on fire.
IPSC 2002 practice session  
K-In-A-Row
Compute the score for a given game of k-in-a-row.
Candy
Redistribute candy between packets.
Ice Cream
Find one Hamiltonian path in a tournament graph.
IPSC 2001  
Andrew's Exams II
Find the integer printed by an obfuscated program outputs.
Bacteria
Interactively find a separating line between red and green points.
Solutions: Solution.
Candies
Separate three candy flavors by moving as few of them as possible.
Urvi Komu Urvi
Divide employees into two equal teams, maximizing the number of times a person plays against their boss.
A Censored Smile
Count all smiling faces in a large picture.
Pibonacci
Compute the elements of a Fibonacci-like sequence.
Gossipers
Check whether all gossipers know everything at the end of the day.
Magic
Find a suitable bijection between two sets of card decks.
IPSC 2001 practice session  
Strange Currency
Find the largest sum that cannot be paid using given banknotes.
Santo's Apples and Banto's Pears
Divide a garden into two equal parts, each containing trees of a single type.
IPSC 2000  
K-In-A-Row
Compute the score for a given game of k-in-a-row.
Cake
Given a set of lines, count into how many parts they divide the plane.
Trolls
Given a string, interactively guess its correct substring based on its number of occurrences.
Get Back!
Travel between oases using as little water as possible.
Andrew's Exams
Count the number of stars an obfuscated program outputs.
Puzzle
Transform a 0/1 rectangle from one state to another by negating rows and exchanging columns.
Windy Office
Reconstruct the page order of a program listing, knowing which pages contain which procedures.
Colorful Cubes
Given cubes with colored sides, assemble a tower in which pairs of touching sides match.
IPSC 2000 practice session  
Santo's Bottles
From a row of bottles, drink as much as possible without drinking from three consecutive bottles.
Labyrinth
Simulate a robot in a simple maze.
Coins
Find counterexamples for greedy algorithms.
IPSC 1999  
Billboard
Find a 3-coloring of the given graph.
Candy
Redistribute candy between packets.
Coins
Find counterexamples for greedy algorithms.
Factorial
Find the last non-zero digit of a factorial.
Labyrinth
Simulate a robot in a simple maze.
Panel
Switch rows and columns of bulbs to minimize the number of lit ones.
Rain
For a given sequence, find the largest k such that no k-element subsequence has a too large sum.
Romeo
Find out whether two people can meet when following shortest paths.
IPSC 1999 practice session  
Medical Research
Given a sequence of numbers, answer queries about the k-th smalest one.