Internet Problem Solving Contest

IPSC 2018

Problem H – Hats of various colors

You and your fellow revolutionaries have been captured by the evil archduke, and now you’re all waiting for execution in the archduke’s dungeons. Fortunately, a thousand year old tradition states that all prisoners must be given a last chance to go free if they can solve a logic puzzle.

The warden explains what will happen:

In both subproblems, there are N = 13 prisoners. In the easy subproblem H1, the hats are of C = 2 different colors (red and blue). In the hard subproblem H2, there are C = 4000 available hat colors.

Problem specification

Write a program that describes the prisoners’ strategy.

This problem is special. Usually, you can write a program in any programming language, and you only submit the computed output data, not your source code. This task is the exact opposite. You only submit source code – specifically, a program written in the Lua 5.3 language. (See below for an introduction.)

We will run N copies of your program and allow them to communicate according to the rules. If all N programs answer correctly, you win.

Your program can use these variables:


These functions won’t exist: debug.debug, io.*, loadfile, math.random, math.randomseed, os.*, package.*, print, require.

We will run 300 test cases. (In total, your program will run 300 × N times.) The memory limit is 256 MB (for the sum of your N programs). The time limit is 10 seconds (for the sum of your 300 × N runs).

Testing your program

If you’d like, you can test your solution with our testing program: lua h-test.lua solution.lua .

Introduction to Lua

If you don’t know the Lua language, here’s a quick introduction:

For more details, refer to the Lua manual and the language grammar, or other on-line resources – though you probably won’t need most parts.


my_bool = colors[1] == 1 or myself > 6

hands = raise(my_bool)

if hands[1] or not hands[2] then
  answer = 1
  answer = C