Internet Problem Solving Contest


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 2016 Input data packages, Problems and solutions booklet
Avoiding accidents
Overlap and concatenate a few strings.
Bounding box
Place a given set of balls into a 3D box.
Counting swaps
Count the ways of sorting a sequence using fewest swaps.
Dumb clicking
Win a simple browser-based clicking game.
Evil minesweeper
Write an evil backend for a minesweeper game.
Get an object from position x to position y using given permutations.
Greatest number
Remove symbols from a simple expression to maximize its value.
Heavy snowfall
Simulate snowfall and snow plowing on a tree.
Intelligence report
Recover passwords from images.
Jumping queues
Choose the best checkout line in a fairly complicated setting.
Kill switch
Given a 'sorting' algorithm, find the shortest input it does not sort.
Luxor Catch-ya!
Solve a captcha that uses hieroglyphics.
Mana troubles
Tap Magic the Gathering lands for mana.
IPSC 2016 practice session
Check whether one string is a subsequence of another.
Turning gears
Given a machine with many linked gears, how will they rotate?
Ultimate magic rectangles
Compute the number of generalized magic squares.
IPSC 2015 Input data packages, Problems and solutions booklet
Build the largest sum A+B from given digits.
Bawdy Boil-brained Bugbear
Build a three-word insult with the given strength.
Chess Pieces
Play a game of chess and create many identical pieces.
Dijkstra's Nightmare
Show that Dijkstra's algorithm can be exponential when negative edges are allowed.
Catch the cat!
Familiar Couples
Disjoint set union "in two dimensions".
Generating Synergy
Coloring a rooted tree up to a given depth.
Humble Captains
Dividing kids into teams and optimizing stuff about pairs of friends.
Inexpensive Travel
Find all shortest paths for cyclists with various distance/ascent preferences.
Juicy Dot Coms
Crack an old 16-bit .COM file.
Klingelt das Glockenspiel
Listen to bells on a wall and determine their locations.
Make sense of a foreign-language menu by ordering food in a smart way.
Write programs in a restricted subset of JavaScript.
IPSC 2015 practice session
Compute the number of rounds of a simple game of solitaire.
Given a box of digits, number as many houses as you can.
Unusual Game Show
Monty Hall problem with a twist.
IPSC 2014 Input data packages, Problems and solutions booklet
Adjusting passwords
Check whether using backspace pays off.
Beating the game
Play a one-dimensional version of the game 2048.
Reverse an operation that copies a part of a string.
Disk space eater
Unzip one exabyte of zeros.
Empathy system
Recognize four different emotions in photos.
Input files: Input data set – E.
Find a sudoku in π
Find nine matching rows of a sudoku in π.
Game on a conveyor belt
Play a surprisingly complicated game of NIM on a conveyor belt.
Find hard inputs for standard hashsets in C++ and Java.
Intrepid cave explorer
Label all vertices of a tree optimally.
Judging programs
Discover which programs do solve a given problem and which ones don't.
Knowledge test
Solve a crossword.
Let there be sound
Decode a sound file... and more.
Maximum enjoyment
Solve a maximum flow problem with a path length limit.
IPSC 2014 practice session
Say it loudly!
Find the *LOUDEST* sentence.
Two covers
Which parts of a sequence are covered twice?
Urban planning
Find the smallest road network with the same transitive closure.
IPSC 2013 Input data packages, 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.
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.
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 Input data packages, Problems and solutions booklet
Abundance of sweets
Look for all candies in a matrix of characters.
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.
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 Input data packages, 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.
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
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 Input data packages, Problems and solutions booklet
Do NOT sort the input sequence.
Find the shortest path in Manhattan that includes the Broadway.
Evaluate spreadsheet cells.
Dragon Slayer
Kill a magic dragon using two magic swords.
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.
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 Input data packages, 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.
Direct wolves to hunt sheep in real time.
Solutions: Solution, Booklet.
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.
Match regular expressions that are written in verbose English.
IPSC 2009 practice session
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 Input data packages
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.
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 Input data packages
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.
Find the shortest path on a fractal board.
Internet is Faulty
Minimize the expected transfer time via a network with faulty links.
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.
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 Input data packages
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.
Find the optimal strategy for a NIM variant where creating a prime-sized heap wins the game.
Create a sequence of page requests that would produce more page faults if cache size is increased slightly.
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.
Simulate a robot in a simple maze.
Medical Research
Given a sequence of numbers, answer queries about the k-th smalest one.
IPSC 2005 Input data packages
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 Input data packages
Andrew's revenge
Given a program and its output, find one matching input.
Place the maximum number of bishops on a generalized chessboard.
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 Input data packages
Arranging Flowers
Reconstruct the missing rows of a Latin square.
begin 4 7 add
Analyze and modify code written in PostScript.
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
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.
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.
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
Compute the score for a given game of k-in-a-row.
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.
Interactively find a separating line between red and green points.
Solutions: Solution.
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.
Compute the elements of a Fibonacci-like sequence.
Check whether all gossipers know everything at the end of the day.
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
Compute the score for a given game of k-in-a-row.
Given a set of lines, count into how many parts they divide the plane.
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.
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.
Simulate a robot in a simple maze.
Find counterexamples for greedy algorithms.
IPSC 1999
Find a 3-coloring of the given graph.
Redistribute candy between packets.
Find counterexamples for greedy algorithms.
Find the last non-zero digit of a factorial.
Simulate a robot in a simple maze.
Switch rows and columns of bulbs to minimize the number of lit ones.
For a given sequence, find the largest k such that no k-element subsequence has a too large sum.
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.