Life In 19x19

Contest Link: https://open.kattis.com/contests/niy786

Start Time: 2017-08-25 17:00:00 UTC (Fri August 25 2017 10am PST, 19:00 CEST)
Duration: 168 hours
Problems: 6

Past Rounds:

• Round 9 (August 11 2017)
• Round 8 (August 4 2017)
• Round 7 (June 16 2017)
• Round 6 (June 9 2017)
• Round 5 (June 2 2017)
• Round 4 (May 19 2017)
• Round 3 (May 12 2017)
• Round 2 (May 6 2017)
• Round 1 (April 28 2017)

Ooh, I just discovered this. Might be fun.

But the problems seem quite easy, what is the catch?

And before I spend too much time:
How are contestants that have solved all problems ranked against each other? Execution time?

(Read: how do I win? )

Tapani wrote:Ooh, I just discovered this. Might be fun.

But the problems seem quite easy, what is the catch?

And before I spend too much time:
How are contestants that have solved all problems ranked against each other? Execution time?

(Read: how do I win? )

You have to solve them the fastest, although the contest is intentionally spread out over a week so people (like myself hah) can relax and do the problems slowly. I try to be consistent in when these start (Friday 10am PST), so you'd want to try to start right around then. Also, if you make a mistake in a submission, there is a time penalty as well (I think it's a function of the contest length; in a 2-hour contest, it's usually several minutes).

Congratulations to Ulrich for not only getting all 6, but for getting 5/6 in 1 try! I would be even more impressed if he passed all the test cases with Python .

This was one of my first competitions of this style, and not sure what I think of it.

These are my thoughts:

First impression: these are not really programming problems. These problems are to programming akin what tesuji puzzles are to playing go. But fair enough.

In this contest, the technique to solve most problems were pretty straightforward (A: sorting, B: set covering+exhaustive search, C: greedy+dfs, D: packing+DP, E: loops - all "tesujis" familiar to me). Hacking down the code for those took only a few minutes each.

Instead the challenges are in other areas. The lessons I learnt here are:

• Check all "silly" corner cases - the test problems seem to be geared to trip you up if you don't
• Read the spec carefully (failed D a few times because I did not print out the solution in the right order)
• Rewrite - don't debug. All of the problems I solved took less than 15-20 mins to hack down, while debugging some corner case can take significantly longer. Delete. Rewrite. That is more time efficient.

Unfortunately those are not really the "fun" part of programming.


One problem was really challenging though. F, the XOR sum. I liked it.
My initial gut feel was that this is a quite hard problem, maybe not even polynomial?
Considering the input sizes used to test, there must be a pseudo-linearish time trick to it. Tried something potentially computationally heavier, but it failed a test problem in the latter half. Tried to revisit it in the last two hours before deadline, but not sure I would have been able to solve it given a full day. Any hints?

Also giving an advantage to whoever submits first is not ideal. Better would be to judge the solution quality (like problem C - make it print a solution with as few pubs as possible (or smth) - and the fewer the better your tie-break) or give better tie break by execution time / memory usage (the faster solver the better).

Since I am in Asia, these contests start like 2am my time - which means by the time I wake up people should have solved most of the puzzles already. In 7-8h I would have solved 4 or 5 of the puzzles in this round, and I would expect nothing less from you

Let's see if I do this again.

Solomon wrote:Congratulations to Ulrich for not only getting all 6, but for getting 5/6 in 1 try! I would be even more impressed if he passed all the test cases with Python .

Thanks, Solomon, and thanks for setting up the contest! Yes, I did all of it in Python - the problems this time had a sufficiently relaxed time limit, and I am still much faster at writing code in Python than in C++.

Here is a spoiler for Problem F: My solution is based on the following two observations.

First, if all numbers have different bit length (i.e. number of bits necessary to write out the binary expression, or in other words the position of the leading 1 in the binary expression), then the xor-maximum is very easy to compute. Just sort the numbers and then, starting with the largest one, go through the list downwards and at each step compare the maximum so far with the maximum xor the next number and proceed with the larger of the two.

Second, if numbers a and b are in the list, then replacing b by a^b in the list does not change the set of numbers that can be produced by xor-ing a subset, and in particular does not change the xor-maximum. So to obtain the simple situation described above we process the numbers from the input as follows: If we haven't seen a number of the same bit length before, store the number; if we have seen a number of the same bit length before, xor the new one with the stored one, obtaining something of smaller bit length, and continue with the result.

All in all, it is just 20 lines of code in Python.


Best, Ulrich

Thanks Ulrich for the clear explanation of your insights into problem F.

Your second observation never occured to me. Instead I went down the murky road of having pools of numbers with constraints that only an odd number can be selected out of some pools, and an even out of some others.

Thanks.

This week I'll be a bit busy to set up the contest, so look forward to Round 11 next week!