Archive

The long table below contains all problems ever used in an IPSC contest. Click any heading to show/hide the corresponding problem set.

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

IPSC 2012	IPSC 2012 problems and solutions booklet

Abundance of sweets	Look for all candies in a matrix of characters. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Booklet, Correct output – A1, Correct output – A2, Python program solving both data sets.
(blank)	Solve a task with no problem statement, using just the messages from the grader. Solutions: Booklet, Python program for the last step of solving B1.
Card game	Find the best strategy in a card game involving probability. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Booklet, Correct output – C1, Correct output – C2, Python program solving data set C1, C++ program solving data set C2.
Data mania	Answer queries about data from past years of IPSC. Input files: Easy input data set – D1, Hard input data set – D2, Additional data file d-members., Additional data file d-messages., Additional data file d-problems., Additional data file d-submissions., Additional data file d-teams.. Solutions: Booklet, Correct output – D1, Correct output – D2.
Evil matching	Solve a pattern matching problem in which we can add adjacent elements of text. Input files: Easy input data set – E1, The whole test data package, RAR, CR+LF newlines, The whole test data package, ZIP, CR+LF newlines, The whole test data package, TAR.GZ, LF newlines. Solutions: Booklet, Correct output – E1, Correct output – E2, Python program solving both data sets.
Fair coin toss	Try to simulate a fair coin by xor-ing biased ones. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Booklet, Correct output – F1, Correct output – F2, Python program solving both data sets.
Gems in the maze	Find the longest path in a graph with outdegree 1. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Booklet, Correct output – G1, Correct output – G2, Python program solving both data sets, C++ program solving both data sets.
Harvesting potatoes	Plan the optimal schedule for a harvester. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Booklet, One correct output – H1, One correct output – H2, C++ program solving both data sets, C++ program for output checking.
Invert the you-know-what	Recover a password from a related MD5 hash. Input files: Password file for both data sets – I1, I2. Solutions: Booklet, Decrypted passwords.
Jukebox	Convert a recording of a simple song into musical notes. Input files: The whole test data package, RAR, CR+LF newlines, The whole test data package, ZIP, CR+LF newlines, The whole test data package, TAR.GZ, LF newlines. Solutions: Booklet, Correct output – J1, Correct output – J2, Python program solving both data sets.
Keys and locks	Determine the master key for a pin tumbler lock. Solutions: Booklet, Python program solving the easy subtask, Python program solving both subtasks, Python program for processing submissions.
Light in a room	Compute the area lit by a cone of light in a room. Input files: Easy input data set – L1, Hard input data set – L2. Solutions: Booklet, Correct output – L1, Correct output – L2, C++ program solving both data sets.
Matrix nightmare	Given a polynomial, find a matrix such that its determinant is the given polynomial. Input files: Easy input data set – M1, Hard input data set – M2. Solutions: Booklet, One correct output – M1, One correct output – M2, Python program solving both data sets, Python program for output checking.
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. Input files: Easy input data set – P1, Hard input data set – P2. Solutions: Booklet.
Quaint encryption	Find one alphabet permutation consistent with a given substitution cipher. Input files: Easy input data set – Q1, Hard input data set – Q2. Solutions: Booklet.
Rebel Alliance attacks	In a sphere, find all grid points with integer distance to the center. Input files: Easy input data set – R1, Hard input data set – R2. 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. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Booklet, Program solving both data sets.
BFS killer	Find a maze for which BFS needs a long queue. Input files: Easy input data set – B1. Solutions: Booklet, Correct output – B1, Correct output – B2.
Candy for each guess	Find the optimal strategies for 'binary search' played as a game. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Booklet, Correct output – C1, Correct output – C2.
Divide the rectangle	Divide a rectangle into two equal parts, each containing one given cell. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Booklet, Correct output – D1, Correct output – D2, Output checker.
Elementary math	Compute square roots of numbers and format the output nicely. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Booklet, Correct output – E1, Correct output – E2, Program solving both data sets.
Flipping coins	Find the optimal strategy in a puzzle about guessing your coin without seeing it. Solutions: Booklet, Correct output – F1, Correct output – F2, Program solving the hard data set, Output checker.
Grid surveillance	Find a persistent data structure that supports additions and rectangle queries. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Booklet, Correct output – G1, Correct output – G2, Program solving both data sets.
HQ0-9+-INCOMPUTABLE?!	Write a program that outputs your TIS in a very unfriendly language. Solutions: Booklet, Program producing a solution for H1, Program producing a solution for H2, Interpreter of the language.
Inverting bits	Compute the negations of many bits using few NOTs. Solutions: Booklet, Correct output – I1, Correct output – I2, Interpreter of the language.
Jedi academy	Compute lots of ray-object intersections. Input files: Easy input data set – J1, Hard input data set – J2. Solutions: Booklet, Correct output – J1, Correct output – J2, Program without OpenGL, Program with OpenGL.
Keep clicking, keep flipping	Play a game on a graph in which you flip vertex colors and adjacent edges. Input files: Easy input data set – K1, Hard input data set – K2. Solutions: Booklet, Correct output – K1, Correct output – K2, Program solving both data sets, Output checker.
Lame crypto	Break a cryptographic protocol in 'real time'. Input files: Easy input data set – L1, Hard input data set – L2. 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. Input files: Easy input data set – P1, Hard input data set – P2. Solutions: Booklet, Correct output – P1, Correct output – P2.
Quality of Service	Assemble the problem statement from many sparse parts. Input files: Easy input data set – Q1, Hard input data set – Q2. Solutions: Booklet, output checker.
Rotate to divide	Find a number that gets divided by K when we rotate it. Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Booklet, Correct output – R1, Correct output – R2.
IPSC 2010	IPSC 2010 problems and solutions booklet
Antisort	Do NOT sort the input sequence. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Booklet, Python code that shuffles until OK, Python code that sorts and swaps.
Broadway	Find the shortest path in Manhattan that includes the Broadway. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Booklet, Correct output – B1, Correct output – B2, C++ code with Dijkstra along the Broadway, Python code working in constant time.
Cells	Evaluate spreadsheet cells. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Booklet, Correct output – C1, Correct output – C2, Python code that parses expressions, Bash script that changes the input into a C++ code.
Dragon Slayer	Kill a magic dragon using two magic swords. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Booklet, Correct output – D1, Correct output – D2, C code that solves equations, C++ code that runs a BFS.
Eyjafjallajökull	Find the vulcano by making online measurements of the ash cloud. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Booklet, C code implementing a good player.
Flawed Code	Find inputs for which incorrect greedy algorithms fail. Input files: Students' programs in C++, Students' programs in Pascal, Students' programs in Python. Solutions: Booklet, Correct output – F1, Correct output – F2, C++ code that computes optimal solution for a given set.
Grid is good	Draw a binary tree into a small grid. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Booklet, Correct output – G1, Correct output – G2, C++ code that makes simple drawings, C++ code that makes better drawings, C++ code of the tester.
Hash	Invert two hashes that use MD5 incorrectly. Input files: Testing program in C++, Header file for the C++ program, Testing program in Java, Example output for XOR-HASH, Example output for ADD-HASH. Solutions: Booklet, C++ header file for MD5, C++ implementation of MD5, C++ code that solves XOR-hash, C++ code that solves ADD-hash.
Inside job	For a dart thrown onto a polygon, compute the expected sum of distances from the dart to all its sides. Input files: Easy input data set – I1, Hard input data set – I2. Solutions: Booklet, Correct output – I1, Correct output – I2, Python code solving the easy data set, C++ code running in O(N^3), C++ code running in O(N^2).
Jimmy the Acting Teacher	Create a schedule of meetings where each pair meets once. Input files: Easy input data set – J1, Hard input data set – J2. Solutions: Booklet, Correct output – J1, Correct output – J2, C++ code that solves both data sets.
Klingon High Council Training	Find the optimal strategy for a game played with ships in a 3D grid. Input files: Easy input data set – K1, Hard input data set – K2. Solutions: Booklet, Correct output – K1, Correct output – K2, Python code that solves the easy data set, Python code that solves both data sets.
Lovely stamps	Compute the number of ways in which some stamps can be bought. Input files: Easy input data set – L1, Hard input data set – L2. Solutions: Booklet, Correct output – L1, Correct output – L2.
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. Input files: Easy input data set – P1, Hard input data set – P2. Solutions: Booklet, Correct output – P1, Correct output – P2, Python code that greedily solves the easy data set, Python code that works in constant time.
Quick growth	Memory is being filled by multiplying arrays, compute the sum of all elements. Input files: Easy input data set – Q1, Hard input data set – Q2. Solutions: Booklet, Correct output – Q1, Correct output – Q2, Python code that simulates the process, C++ code running in O(DN^4), C++ code running in O(DN^3), C++ code running in O(DN^2), Python code that solves even the additional challenge.
Round and round it goes	Find constants that turn the given program into the best infinite loop. Input files: Dexter's program in C++, Dexter's program in Python, Dexter's program in Java. Solutions: Booklet, Correct output – R1, Correct output – R2, C++ code that finds all primes and bruteforces the answer, Python code of the tester.
IPSC 2009	IPSC 2009 problems and solutions booklet
Arithmetics for dummies	Find the result of an expression computed on an oldschool calculator. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Booklet, Correct output – A1, Correct output – A2.
Bouncing balls	Find the state of a box full of bouncing balls. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Booklet, Correct output – B1, Correct output – B2, Python program solving both data sets.
Cryptic punchcards	Read text stored on punchcards. Input files: Easy input – card 1, Easy input – card 2, Easy input – card 3, Easy input – card 4, Hard input – card 1, Hard input – card 2, Hard input – card 3, Hard input – card 4, Hard input – card 5, Hard input – card 6, Hard input – card 7, Hard input – card 8, Hard input – card 9. Solutions: Solution, Booklet, Correct output – C1, Correct output – C2.
Don't worry about wrong answers	A weird problem in which almost any submission is accepted. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution, Booklet, C++ program "not solving" the easy data set, Python program "not solving" the hard data set.
Easy representation	Compute area of a pictorial representation of a correctly parentesized string. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Booklet, Correct output – E1, Correct output – E2, Python program solving both data sets.
Fish Fillets	Solve two new levels of the Fish Fillets puzzle. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, Booklet.
Going to the movies	Compute the probability that all girls will find a place to sit at the cinema. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Solution, Booklet, Correct output – G1, Correct output – G2, Python program solving both data sets.
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. Solutions: Solution, Booklet, Correct output – I1, Correct output – I2, An interpreter used to test your solutions.
Jumbo Airlines	Compute the number of ways of seating people in an airplane. Input files: Easy input data set – J1, Hard input data set – J2. Solutions: Solution, Booklet, Correct output – J1, Correct output – J2, C++ code of a simple dynamic programming, C++ code of a more efficient dynamic programming, C++ code using matrix multiplication.
Karl's shopping	Find the smallest amount of additional cash needed when paying by various vouchers. Input files: Easy input data set – K1, Hard input data set – K2. Solutions: Solution, Booklet, Correct output – K1, Correct output – K2, C++ program solving both data sets.
Let there be rainbows!	A tree is being colored using 7 colors, construct its final state. Input files: Easy input data set – L1, Hard input data set – L2. Solutions: Solution, Booklet, Correct output – L1, Correct output – L2, C++ program solving both data sets.
Muzidabutur	Match regular expressions that are written in verbose English. Input files: Easy input data set – M1, Hard input data set – M2. Solutions: Solution, Booklet, Correct output – M1, Correct output – M2.
IPSC 2009 (practice session)
Pathfinding	Given a maze, find a reasonably short solution. Input files: Easy input data set – P1, Hard input data set – P2. 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'. Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Solution, Booklet.
IPSC 2008
Army Strength	Find the winner in a battle of two armies where the weakest unit always gets killed. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2, Python program solving both data sets.
Breaking in	Find the server that gives you the most access when compromised. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B1, Correct output – B2, C program solving both data sets.
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. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution, Correct output – D1, Correct output – D2, C++ program solving both data sets.
Expected Cost	Compute the expected cost of a minimum spanning tree for a graph with random edge weights. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2, C++ program to split input into biconnected components, Python program solving processed data sets.
Find the Meaning	A message is somehow hidden in the input file, find it. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, Correct output – F1, Correct output – F2.
Game on Words	In real time, play against us a game where the players extend a string until it becomes a word. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Solution, C++ program that plays the game optimally.
Hidden Text	Show that blurred text can be recovered if you know the font. Input files: Easy input data set - H1, Difficult input data set - H2. Solutions: Solution, Correct output – H1, Correct output – H2.
Inventing Test Data	Given a weighted tree T, find the lightest complete graph for which T is the only MST. Input files: Easy input data set – I1, Hard input data set – I2. Solutions: Solution, Correct output – I1, Correct output – I2, C++ program solving both data sets.
Just a Single Lie	Find the optimal strategy in a number guessing game where you may receive a single lie. Input files: Easy input data set – J1, Hard input data set – J2. Solutions: Solution, Correct output – J1, Correct output – J2, Python program solving both data sets.
K Equal Digits	Find the largest number with all digits equal that matches a set of criteria. Input files: Easy input data set – K1, Hard input data set – K2. Solutions: Solution, Correct output – K1, Correct output – K2, C++ program solving both data sets.
Large party	Count the ways in which men and women can sit at a table if large clusters of women are forbidden. Input files: Easy input data set – L1, Hard input data set – L2. Solutions: Solution, Correct output – L1, Correct output – L2, C++ program solving both data sets.
IPSC 2008 (practice session)
Perfect Rhyme	Given a word, find another word that is the best rhyme. Input files: Easy input data set – P1, Hard input data set – P2. Solutions: Solution, Correct output – P1, Correct output – P2.
Quiz	Answer all trivia questions about the history of IPSC correctly. Input files: Easy input data set – Q1, Hard input data set – Q2. Solutions: Solution, Correct output – Q1, Correct output – Q2.
Railroad Map	Given a graph, replace all non-branching paths by direct edges. Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Solution, Correct output – R1, Correct output – R2.
IPSC 2007
Anti-Blot System	Fix a simple equation that has a ink blot covering part of a number. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2, C++ program that solves both data sets, bash script that solves both data sets.
Bus Story	Check whether a story about passengers boarding and leaving a bus may be true. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B1, Correct output – B2, bash script that solves both data sets, C++ program that solves both data sets.
Calling Me Calling You	Purchase enough free numbers to allow a group of friends call each other for free. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Solution, C program that solves both data sets.
Delicious Cake	Count the ways of cutting a rectangular cake into pieces. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution, Correct output – D1, Correct output – D2, C++ program that solves both data sets.
Enhancing IPSC Rules	Given a rock-paper-scissors game as a set of pictures, compute who won. Input files: Easy input - compressed by TAR and GZIP, Easy input - compressed by ZIP, Hard input - compressed by TAR and GZIP, Hard input - compressed by ZIP. Solutions: Solution, Correct output – E1, Correct output – E2.
Finally some Sudoku	Solve several Sudoku instances that share some of their values. Input files: Easy input, Hard input. Solutions: Solution, Correct output – F1, Correct output – F2, C++ code that solves both data sets, Logic program solving both data sets.
Guess the Numbers	In real time, guess a sequence by choosing another and getting their scalar product. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Solution.
Here-There	Find the shortest path on a fractal board. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Solution, Correct output – H1, Correct output – H2, C code that solves easy data set.
Internet is Faulty	Minimize the expected transfer time via a network with faulty links. Input files: Easy input data set – I1, Hard input data set – I2. Solutions: Solution, Correct output – I1, Correct output – I2, C++ program to solve both data sets.
jPix	Draw lines and compute area reached by a flood fill on a huge grid. Input files: Easy input data set – J1, Hard input data set – J2. Solutions: Solution, Correct output – J1, Correct output – J2, C++ program to solve both data sets.
Know Your Crypto	Solve a simple cipher and reverse a seemingly random one. Input files: Easy input data set – K1, Hard input data set – K2. Solutions: Solution, Correct output – K1, Correct output – K2.
Little Peter's Tower	Maximize the expected height of a tower built from randomly drawn blocks. Input files: Easy input data set – L1, Hard input data set – L2. Solutions: Solution, Correct output – L1, Correct output – L2, C program to solve both data sets.
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. Input files: Easy input data set – P1, Hard input data set – P2. Solutions: Solution, Correct output – P1, Correct output – P2, C++ program to solve both data sets.
QuackQuack	Factorize and duplicate the queue in our special queue-based scripting language. Solutions: Solution, Correct output – Q1, Correct output – Q2.
Rasterized Lines	Given N, in how many ways can one draw a rasterized line segment with N black pixels? Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Solution, Correct output – R1, Correct output – R2, C++ program to solve both data sets.
IPSC 2006
Another Candies	Kids brought candies, divide them evenly. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2, C++ program that solves both data sets.
Biased Standings	Given the teams' wishes, produce a ranklist that matches them as closely as possible. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B1, Correct output – B2, python script that solves both data sets.
Counting Subsequences	Count all contiguous subsequences with sum equal to 47. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Solution, Correct output – C1, Correct output – C2, C++ program solving both data sets, Another C++ program solving both data sets.
Digital Calculator	Compute the first few and the last few digits of a factorial. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution, Correct output – D1, Correct output – D2, BC script that solves both data sets.
Encoded Messages	Decrypt a permutation cipher and a substitution cipher. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2.
Fractal Plants	Find the center of mass of a fractal plant. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, Correct output – F1, Correct output – F2, C code that solves both data sets.
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. Solutions: Solution, Correct output – G1, Correct output – G2, C code that solves easy data set, C code that solves hard data set.
h4x0r t3h c0d3	Compute a discrete logarithm in a restricted setting, and create two PostScript files with the same MD5 sum. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Solution, First PostScript file, Second PostScript file, A helper program for hard problem.
Ideal Matches	Cover a complete graph by Hamiltonian cycles that intersect in a fixed matching. Input files: Easy input data set – I1, Hard input data set – I2. Solutions: Solution, A C++ program to solve both data sets.
Jamcode 2006	Given a task and a wrong program, find an input for which the program works. Input files: Easy input data set – J1, Hard input data set – J2. Solutions: Solution, Correct output – J1, Correct output – J2.
Kruskal	Find the optimal strategy for a NIM variant where creating a prime-sized heap wins the game. Input files: Easy input data set – K1, Hard input data set – K2. Solutions: Solution, Correct output – K1, Correct output – K2, C program solving both data sets.
Librarian	Create a sequence of page requests that would produce more page faults if cache size is increased slightly. Solutions: Solution, Correct output – L1, Correct output – L2.
Matrioska	Get the correct answer out of multiple nested file formats. Input files: Easy input data set – M1, Hard input data set – M2. Solutions: Solution.
IPSC 2006 (practice session)
Santos Apples	Divide a garden into two equal parts, each containing trees of a single type. Input files: Easy input data set – P1, Hard input data set – P2.
Labyrinth	Simulate a robot in a simple maze. Input files: Easy input data set – Q1, Hard input data set – Q2.
Medical Research	Given a sequence of numbers, answer queries about the k-th smalest one. Input files: Easy input data set – R1, Hard input data set – R2.
IPSC 2005
Alpha Centauri Tennis	Given a transcript of a tennis match, find out who won. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2, A simple shell script that solves both data sets.
Bottom Coder	Alter code so that it creates a specific output. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B2, A faster version of the B2 program.
Crane Operator	Given a crane and a set of boxes, compute the boxes' final positions and move them using fewest moves possible. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Solution, Correct output – C1, Correct output – C2, C code that solves both data sets.
Dance Dance Revolution	Catch as many arrows as possible in a DDR game. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution, Correct output – D1, Correct output – D2, C++ code that solves both data sets.
Exact? Approximate!	Given a decimal number, produce the simplest fraction that evaluates to that decimal after appropriate rounding. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2, A bc script that solves both data sets.
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. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, C++ code that solves both data sets.
Gears In Action	Compute the time until a system of gears reaches a given configuration. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Solution, Correct output – G1, Correct output – G2, C++ code that solves both data sets.
Hidden Messages	Decrypt two pen-and-paper ciphers. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Solution.
Ignore the Garbage	Given an upside-down digital display, find the k-th number that makes sense. Input files: Easy input data set – I1, Hard input data set – I2. Solutions: Solution, Correct output – I1, Correct output – I2, A shell script that calls bc to solve both data sets.
Just for Fun	Solve logic puzzles for bonus time. Input files: Easy input data set – J1, Hard input data set – J2. Solutions: Solution.
IPSC 2005 (practice session)
Polly Wanna Cracker	Divide crackers among parrots evenly and report the exact outcome. Input files: Easy input data set – P1, Hard input data set – P2. Solutions: Solution, A shell script that calls bc to solve both data sets.
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. Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Solution, C code that solves both data sets.
IPSC 2004
Andrew's revenge	Given a program and its output, find one matching input. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2.
Bishops	Place the maximum number of bishops on a generalized chessboard. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B1, Correct output – B2.
Calls	Given a matrix of integers, check whether it is a shortest distances matrix for some graph. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Solution, Correct output – C1, Correct output – C2, C program solving both data sets.
Delayed search	In real time, guess a number using yes/no questions, with each answer coming only after several questions. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution.
Electrical Circuits	Count the number of perfect matchings in special graphs. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2, C program solving easy data set.
Fat Rat	Can a sphere fit through a given pipe with obstacles? Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, Correct output – F1, Correct output – F2, C program solving easy data set, C program solving difficult data set.
Gets and Puts	Write a sorting program and a quine in our queue-based scripting language. Solutions: Solution, Correct output – G1, Correct output – G2.
Hard Question – P=NP?	Given a polygon and a set of non-intersecting rectangles, does a subset of rectangles exactly match the polygon? Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Solution, Correct output – H1, Correct output – H2, C program solving both data sets.
IPSC 2004 (practice session)
Dependency Problems	Given package dependencies and availability, install as many as possible. Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Solution, Correct output – R1, Correct output – R2.
Censored Smiles	Count all smiling faces in a large picture. Input files: Easy input data set – S1, Hard input data set – S2. Solutions: Solution, Correct output – S1, Correct output – S2.
The Tiling Problem	Tile a given floor using 2 by 1 tiles. Input files: Easy input data set – T1, Hard input data set – T2. Solutions: Solution, Correct output – T1, Correct output – T2, Program solving both data sets.
IPSC 2003
Arranging Flowers	Reconstruct the missing rows of a Latin square. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2, C program solving both data sets.
begin 4 7 add	Analyze and modify code written in PostScript. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B1, Correct output – B2.
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. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution, Correct output – D1, Correct output – D2.
Enchanted Forest	Find the smallest number of flood fills necessary to recolor a 0/1 matrix to a single color. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2, C program solving both data sets.
Folding the Paper	Can a strip of paper squares be folded into the given order? Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, Correct output – F1, Correct output – F2, C program solving both data sets.
Got Root?	Find the optimal strategy for a Hackenbush variant. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Solution, Correct output – G1, Correct output – G2, C++ program solving both data sets.
Hordes of Bacteria	Simulate lots of iterations of a growing bacteria colony. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Solution, Correct output – H1, Correct output – H2, C++ program solving both data sets, bc program solving both data sets.
IPSC 2003 (practice session)
Candies	Separate three candy flavors by moving as few of them as possible. Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Correct output – R1, Correct output – R2.
Colorful Cubes	Given cubes with colored sides, assemble a tower in which pairs of touching sides match. Input files: Easy input data set – S1, Hard input data set – S2. Solutions: Correct output – S1, Correct output – S2.
Strange Numbers	Convert integers between binary and our ad-hoc encoding. Input files: Easy input data set – T1, Hard input data set – T2. Solutions: Correct output – T1, Correct output – T2.
IPSC 2002
Andews's Exams III	Given a program, find an input for which it terminates quickly. Input files: Easy input data set – A1, Hard input data set – A2.
Load Balancing	Find the smallest amount of rounds necessary to rebalance the load for a row of processors. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B1, Correct output – B2, C program solving both data sets.
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. Input files: Easy input data set – D1, Hard input data set – D2.
Expressions	Express the given number as an expression that uses as few 1s as possible. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2, Program solving the easy input data set, Program solving the difficult input data set.
(un)Fair Play	Given a league in progress, find out whether a given team can still win it. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, Correct output – F1, Correct output – F2.
Gardening	Find the smallest axes-parallel square that contains at least one half of the given points. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Solution, Correct output – G1, Correct output – G2, Program solving both data sets.
Equatorial Bonfire	A set of bonfires is started along the equator, find the time when all the equator is on fire. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Correct output – H1, Correct output – H2.
IPSC 2002 (practice session)
K-In-A-Row	Compute the score for a given game of k-in-a-row. Input files: Easy input data set – R1, Hard input data set – R2.
Candy	Redistribute candy between packets. Input files: Easy input data set – S1, Hard input data set – S2.
Ice Cream	Find one Hamiltonian path in a tournament graph. Input files: Easy input data set – T1, Hard input data set – T2. Solutions: Solution, Correct output – T1, Correct output – T2.
IPSC 2001
Andrew's Exams II	Find the integer printed by an obfuscated program outputs. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2.
Bacteria	Interactively find a separating line between red and green points. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution.
Candies	Separate three candy flavors by moving as few of them as possible. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Solution, Correct output – C1, Correct output – C2.
Urvi Komu Urvi	Divide employees into two equal teams, maximizing the number of times a person plays against their boss. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution, Correct output – D1, Correct output – D2, Program solving both data sets.
A Censored Smile	Count all smiling faces in a large picture. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2, Program solving both data sets.
Pibonacci	Compute the elements of a Fibonacci-like sequence. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Correct output – F1, Correct output – F2.
Gossipers	Check whether all gossipers know everything at the end of the day. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Solution, Correct output – G1, Correct output – G2, Program solving both data sets.
Magic	Find a suitable bijection between two sets of card decks. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Solution, Correct output – H1, Correct output – H2, Program solving both data sets.
IPSC 2001 (practice session)
Strange Currency	Find the largest sum that cannot be paid using given banknotes. Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Correct output – R1, Correct output – R2.
Santo's Apples and Banto's Pears	Divide a garden into two equal parts, each containing trees of a single type. Input files: Easy input data set – S1, Hard input data set – S2. Solutions: Correct output – S1, Correct output – S2.
IPSC 2000
K-In-A-Row	Compute the score for a given game of k-in-a-row. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2, Program solving both data sets.
Cake	Given a set of lines, count into how many parts they divide the plane. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B1, Correct output – B2, Program solving both data sets.
Trolls	Given a string, interactively guess its correct substring based on its number of occurrences. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Solution, Correct output – C1, Correct output – C2, Program solving both data sets.
Get Back!	Travel between oases using as little water as possible. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Correct output – D1, Correct output – D2.
Andrew's Exams	Count the number of stars an obfuscated program outputs. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2, Program solving easy input data set, Program solving difficult input data set.
Puzzle	Transform a 0/1 rectangle from one state to another by negating rows and exchanging columns. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, Correct output – F1, Correct output – F2, Program solving both data sets.
Windy Office	Reconstruct the page order of a program listing, knowing which pages contain which procedures. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Correct output – G1, Correct output – G2.
Colorful Cubes	Given cubes with colored sides, assemble a tower in which pairs of touching sides match. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Correct output – H1, Correct output – H2.
IPSC 2000 (practice session)
Santo's Bottles	From a row of bottles, drink as much as possible without drinking from three consecutive bottles. Input files: Easy input data set – R1, Hard input data set – R2. Solutions: Solution, Program solving both data sets.
Labyrinth	Simulate a robot in a simple maze. Input files: Easy input data set – S1, Hard input data set – S2.
Coins	Find counterexamples for greedy algorithms. Input files: Easy input data set – T1, Hard input data set – T2.
IPSC 1999
Billboard	Find a 3-coloring of the given graph. Input files: Easy input data set – A1, Hard input data set – A2. Solutions: Solution, Correct output – A1, Correct output – A2, C program solving both data sets.
Candy	Redistribute candy between packets. Input files: Easy input data set – B1, Hard input data set – B2. Solutions: Solution, Correct output – B1, Correct output – B2, C program solving both data sets.
Coins	Find counterexamples for greedy algorithms. Input files: Easy input data set – C1, Hard input data set – C2. Solutions: Solution, Correct output – C1, Correct output – C2, C program solving the problem of little John.
Factorial	Find the last non-zero digit of a factorial. Input files: Easy input data set – D1, Hard input data set – D2. Solutions: Solution, Correct output – D1, Correct output – D2, C program solving the easy data set, Less efficient program solving the difficult data set, More efficient program solving the difficult data set.
Labyrinth	Simulate a robot in a simple maze. Input files: Easy input data set – E1, Hard input data set – E2. Solutions: Solution, Correct output – E1, Correct output – E2, Pascal program solving both data sets.
Panel	Switch rows and columns of bulbs to minimize the number of lit ones. Input files: Easy input data set – F1, Hard input data set – F2. Solutions: Solution, Correct output – F1, Correct output – F2.
Rain	For a given sequence, find the largest k such that no k-element subsequence has a too large sum. Input files: Easy input data set – G1, Hard input data set – G2. Solutions: Solution, Correct output – G1, Correct output – G2, C program solving both data sets.
Romeo	Find out whether two people can meet when following shortest paths. Input files: Easy input data set – H1, Hard input data set – H2. Solutions: Solution, Correct output – H1, Correct output – H2, C program solving both data sets.
IPSC 1999 (practice session)
Medical Research	Given a sequence of numbers, answer queries about the k-th smalest one. Input files: Easy input data set – R1, Hard input data set – R2.

Internet Problem Solving Contest