# 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 2018 Input data packages, Problems and solutions booklet Armed bandit Find any output + the lex. min. output of a slot machine. Input files: Easy input data set – A1, Hard input data set – A2. Brain fold Fold paper many times, cut it once, count pieces. Input files: Easy input data set – B1, Hard input data set – B2. Counting rectangles Count sets of n rectangles that differ after coordinate compression. Delightful Write programs in ternary assembler. Encrypted romance Count sparse collisions for a collection of hash functions. Input files: Easy input data set – E1, Hard input data set – E2. Farmer's code Decipher the way apple tree crossing works. Input files: Dashboard. Solutions: Solution, Booklet, Zip file with server implementation. Git gud List all files in a git repository. Solutions: Solution, Booklet, Zip file with solution scripts. Hats of various colors Write programs that play a hat puzzle in parallel. Input files: Helper program for testing. Incorrect expression Find all possible values after one character is changed in an expression. Input files: Easy input data set – I1, Hard input data set – I2. Jumping over walls Construct the smallest maze in which you need to use all directions of jumps. Kids draw the darndest things Compute exact values of a weird continuous function. Input files: Easy input data set – K1, Hard input data set – K2. Lethargic foe Quickly win games of symmetric chess. McDroid's Run a restaurant for robots. Input files: Dashboard. Solutions: Solution, Booklet, Zip file with server implementation. Partitioning a square Find the smallest square that can be divided into n equal regions. Input files: Easy input data set – P1, Hard input data set – P2. Qizz Quzz Check validity of generalized Fizz Buzz sequences. Input files: Easy input data set – Q1, Hard input data set – Q2. Raw data Make a POST request to our webserver. Solutions: Solution, Booklet. Automated flooding Input files: Easy input data set – A1, Hard input data set – A2. Bishopian paths Input files: Easy input data set – B1, Hard input data set – B2. Collector's dilemma Input files: Easy input data set – C1, Hard input data set – C2. Dazzling digits Input files: Easy input data set – D1, Hard input data set – D2. Elevation alteration Flipping and cutting Input files: Easy input data set – F1, Hard input data set – F2. Gunfight Holy cow, Vim! Internet problem Input files: Easy input data set – I1, Hard input data set – I2. Judicious cuts Input files: Easy input data set – J1, Hard input data set – J2. Kirk or Picard? Input files: Input data set – K. Lucky draws Matching pairs Input files: Input data set – M. Queue skipping Russian roulette Input files: Easy input data set – R1, Hard input data set – R2. St. Ives Input files: Easy input data set – S1, Hard input data set – S2. Avoiding accidents Overlap and concatenate a few strings. Input files: Easy input data set – A1, Hard input data set – A2. Bounding box Place a given set of balls into a 3D box. Input files: Easy input data set – B1, Hard input data set – B2. Counting swaps Count the ways of sorting a sequence using fewest swaps. Input files: Easy input data set – C1, Hard input data set – C2. Dumb clicking Win a simple browser-based clicking game. Input files: Easy game – D1, Hard game – D2. Evil minesweeper Write an evil backend for a minesweeper game. Input files: Easy input data set – E1, Hard input data set – E2. Ferries Get an object from position x to position y using given permutations. Input files: Easy input data set – F1, Hard input data set – F2. Greatest number Remove symbols from a simple expression to maximize its value. Input files: Easy input data set – G1, Hard input data set – G2. Heavy snowfall Simulate snowfall and snow plowing on a tree. Intelligence report Recover passwords from images. Input files: Easy input data set – I1, Hard input data set – I2. 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. Input files: A zip file with test data for both L1 and L2. Mana troubles Tap Magic the Gathering lands for mana. Subsequence Check whether one string is a subsequence of another. Turning gears Given a machine with many linked gears, how will they rotate? Input files: Easy input data set – T1, Hard input data set – T2. Ultimate magic rectangles Compute the number of generalized magic squares. Input files: Easy input data set – U1, Hard input data set – U2. A+B Build the largest sum A+B from given digits. Input files: Easy input data set – A1, Hard input data set – A2. Bawdy Boil-brained Bugbear Build a three-word insult with the given strength. Input files: Easy input data set – B1, Hard input data set – B2. 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. Enclosure 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. Input files: Easy input data set – H1, Hard input data set – H2. Inexpensive Travel Find all shortest paths for cyclists with various distance/ascent preferences. Juicy Dot Coms Crack an old 16-bit .COM file. Input files: File for subproblem J1, File for subproblem J2. Klingelt das Glockenspiel Listen to bells on a wall and determine their locations. Input files: File for subproblem K1, File for subproblem K2. Lunchtime! Make sense of a foreign-language menu by ordering food in a smart way. Input files: Easy input data set – L1, Hard input data set – L2. Make*me-an+[integer!] Write programs in a restricted subset of JavaScript. Solitaire Compute the number of rounds of a simple game of solitaire. Town Given a box of digits, number as many houses as you can. Input files: Easy input data set – T1, Hard input data set – T2. Unusual Game Show Monty Hall problem with a twist. Input files: Easy input data set – U1, Hard input data set – U2. Adjusting passwords Check whether using backspace pays off. Input files: Easy input data set – A1, Hard input data set – A2. Beating the game Play a one-dimensional version of the game 2048. Input files: Easy input data set – B1, Hard input data set – B2. Copier Reverse an operation that copies a part of a string. Input files: Easy input data set – C1, Hard input data set – C2. Disk space eater Unzip one exabyte of zeros. Input files: Easy input data set – D1, Hard input data set – D2. 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. Input files: Easy input data set – G1, Hard input data set – G2. Hashsets Find hard inputs for standard hashsets in C++ and Java. Input files: C++ program – h.cc, Java program – h.java. Intrepid cave explorer Label all vertices of a tree optimally. Input files: Easy input data set – I1, Hard input data set – I2. Judging programs Discover which programs do solve a given problem and which ones don't. Input files: Easy input data set – J1, Easy input data set – J2. Knowledge test Solve a crossword. Input files: Easy input data set – K1, Hard input data set – K2. Let there be sound Decode a sound file... and more. Input files: Easy input data set – L1, Easy input data set – L2. Maximum enjoyment Solve a maximum flow problem with a path length limit. Input files: Easy input data set – M1, Hard input data set – M2. Say it loudly! Find the *LOUDEST* sentence. Input files: Easy input data set – S1, Hard input data set – S2. Two covers Which parts of a sequence are covered twice? Input files: Easy input data set – T1, Hard input data set – T2. Urban planning Find the smallest road network with the same transitive closure. Input files: Easy input data set – U1, Hard input data set – U2. Advice for Olivia Pay a sum using sufficiently few coins and banknotes. Input files: Easy input data set – A1, Hard input data set – A2. Boredom buster Find the best way of breaking a number into ones. Input files: Easy input data set – B1, Hard input data set – B2. Code Inception Analyze programs that output instructions how to modify them. Solutions: Booklet, Correct output for C1, Correct output for C2. Do the grading Write a grader for the practice task R. Input files: Easy input data set – D1, Hard input data set – D2. Exploring the cave Find a NFA with n states such that the corresponding DFA has d states. Input files: Easy input data set – E1, Hard input data set – E2. 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. Input files: Easy input data set – G1, Hard input data set – G2. Histiaeus Locate a hidden message carried by a slave. Solutions: Booklet, Correct output for H1, Correct output for H2. Invisible cats Descramble a collection of images and find all cats. Solutions: Booklet, Correct output for I1, Correct output for I2. Just a single gate Find all universal ternary gates. Knee problems Count the ways of walking up and down the stairs. Input files: Easy input data set – K1, Hard input data set – K2. Labyrinth Find your way through a seemingly simple labyrinth with buttons. Input files: JavaScript game – L1, L2. Morning hassle Find the fastest way to drive your car over railroad crossings. Input files: Easy input data set – M1, Hard input data set – M2. Plus one Increment the given number by 1... with a twist! Input files: Easy input data set – P1, Hard input data set – P2. Solutions: Booklet, Correct output for P1, Correct output for P2. Quite the cheater! Find a sequence with a given mean and a given variance. Input files: Easy input data set – Q1, Hard input data set – Q2. Rearranged alphabet Find a short string that contains each permutation as a subsequence. Abundance of sweets Look for all candies in a matrix of characters. Input files: Easy input data set – A1, Hard input data set – A2. (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. Input files: Easy input data set – C1, Hard input data set – C2. Data mania Answer queries about data from past years of IPSC. Solutions: Booklet, Correct output – D1, Correct output – D2. 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. Input files: Easy input data set – F1, Hard input data set – F2. 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. Harvesting potatoes Plan the optimal schedule for a harvester. Input files: Easy input data set – H1, Hard input data set – H2. 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. 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. Input files: Easy input data set – L1, Hard input data set – L2. 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. 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. 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. Elementary math Compute square roots of numbers and format the output nicely. Input files: Easy input data set – E1, Hard input data set – E2. 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. Input files: Easy input data set – G1, Hard input data set – G2. 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. Input files: Easy input data set – J1, Hard input data set – J2. 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. 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. 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. Antisort Do NOT sort the input sequence. Input files: Easy input data set – A1, Hard input data set – A2. Broadway Find the shortest path in Manhattan that includes the Broadway. Input files: Easy input data set – B1, Hard input data set – B2. Cells Evaluate spreadsheet cells. Input files: Easy input data set – C1, Hard input data set – C2. Dragon Slayer Kill a magic dragon using two magic swords. Input files: Easy input data set – D1, Hard input data set – D2. 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. Grid is good Draw a binary tree into a small grid. Input files: Easy input data set – G1, Hard input data set – G2. 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. Input files: Easy input data set – I1, Hard input data set – I2. 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. 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. 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. 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. 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. Round and round it goes Find constants that turn the given program into the best infinite loop. 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. Cryptic punchcards Read text stored on punchcards. 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. 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. 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. 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. Input files: Easy input data set – J1, Hard input data set – J2. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. Enhancing IPSC Rules Given a rock-paper-scissors game as a set of pictures, compute who won. 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. 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. 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. 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. 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. 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. 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. Another Candies Kids brought candies, divide them evenly. Input files: Easy input data set – A1, Hard input data set – A2. 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. Counting Subsequences Count all contiguous subsequences with sum equal to 47. Input files: Easy input data set – C1, Hard input data set – C2. 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. 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. 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. Input files: Easy input data set – H1, Hard input data set – H2. 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. 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. 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. 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. Bottom Coder Alter code so that it creates a specific output. Input files: Easy input data set – B1, Hard input data set – B2. 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. 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. 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. 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. 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. Just for Fun Solve logic puzzles for bonus time. Input files: Easy input data set – J1, Hard input data set – J2. Solutions: Solution. 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. 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. 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. 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. Fat Rat Can a sphere fit through a given pipe with obstacles? Input files: Easy input data set – F1, Hard input data set – F2. 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. 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. Arranging Flowers Reconstruct the missing rows of a Latin square. Input files: Easy input data set – A1, Hard input data set – A2. 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. 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. Got Root? Find the optimal strategy for a Hackenbush variant. Input files: Easy input data set – G1, Hard input data set – G2. Hordes of Bacteria Simulate lots of iterations of a growing bacteria colony. Input files: Easy input data set – H1, Hard input data set – H2. 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. 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. 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. (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. 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. 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. 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. A Censored Smile Count all smiling faces in a large picture. Input files: Easy input data set – E1, Hard input data set – E2. 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. Magic Find a suitable bijection between two sets of card decks. Input files: Easy input data set – H1, Hard input data set – H2. 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. 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. 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. 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. 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. 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. 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. 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. Billboard Find a 3-coloring of the given graph. Input files: Easy input data set – A1, Hard input data set – A2. Candy Redistribute candy between packets. Input files: Easy input data set – B1, Hard input data set – B2. Coins Find counterexamples for greedy algorithms. Input files: Easy input data set – C1, Hard input data set – C2. Factorial Find the last non-zero digit of a factorial. Input files: Easy input data set – D1, Hard input data set – D2. Labyrinth Simulate a robot in a simple maze. Input files: Easy input data set – E1, Hard input data set – E2. 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. Romeo Find out whether two people can meet when following shortest paths. Input files: Easy input data set – H1, Hard input data set – H2. Medical Research Given a sequence of numbers, answer queries about the k-th smalest one. Input files: Easy input data set – J1, Hard input data set – J2.