After IPSC

IPSC has ended and ever since I found this tournament years ago I do not miss it because it is always very interesting and fun of an experience. Since no other important tournament round happened this week, let us talk about it. The solutions booklet is already out, so I won't bother explaining the problems as the booklet is well-written.

Waking up at 5.55 AM
I am more of the 7:00 AM kind, you know. I would have probably had no problem waking up early for the tournament normally but yesterday I had to stay up late writing a certain editorial that will be published soon. I woke up at 5:55 AM but went back to sleep until 6:30-ish.

Then you have to download the tar.gz that contains everything useful to solve the problem. I slowly opened all of the problems and the submission and standings pages. Emptied my contest folder so that I could place source codes there. And finally took a look at what was the problem that was solved the most. It clearly was A

A - The rock, paper, lizard, Spock one
This was very easy. Even the large input. There are always two objects that beat any of the objects, so it is always possible to pick a different one than the previous one. A quick pair of points.

M
Last year I decided that it is best to avoid these problems that just give you negative penalty time. They are not so fun to solve and they don't really help that much to your ranking. The time you spend on them could have been used solving the other problems.

B
I thought to myself : "You are a problem setter and you love maze BFS problems, if you don't solve at least B1 you are a shame!" So, I gave it a try.

After trying a program that made random mazes and then called the c++ source code until max_size was 5000, I found a maze (absurdly quick). Submitted it and ... it was wrong. For some reason, the random code was reaching max_size > 5000, but when using the same maze in another instance of the program the result was 1029. At the end I noticed it. I do not know if this was intended and the problem setters are evil geniuses, but the c++ code does not clear the queue initially, so if you try the random approach, it will begin to do funny things after the first execution. After fixing the queue bug, it seemed that any random input would yield a size of around 1200 tops. So, I tried to find a pattern in small cases that would maximize the queue size. Eventually time ran out and I could not believe I had already used over an hour in this problem , I decided to try other things...

When I opened the solutions booklet, I got really excited at the beautiful fractals that were required to solve this problem, but I have to wonder exactly how would you generate them. Oh well.

The next easiest problem seemed to be D1.

D1
I noticed that you cannot evenly divide in two a case in which both the number of rows and columns are odd. Then I noticed that this is not only a necessary condition but also sufficient. A cool problem. I tried to give some thought to D2, but decided it is better to try the other easy problems first.

I1
You had to write a program in a strange ASM-like language. Negating 7 integers using only a NOT operation is actually very easy, just put them together in a single register using shift and or operations, negate the register and then revert the shift and or operations to return to 7 numbers.

So far the contest is going well.

F1
There are 3¹² choices for the decision matrix. And for each matrix, you could try the 8 different possibilities for the coin flips to calculate the probability that matrix yields. 3¹²*8 is not that high, so a simple bruteforce through all matrixes and remembering the best one is enough.

The final result made plenty of sense. Whenever the other two players had a H, guess a tail, and if the other two players have a T, guess a head. Otherwise, pass. What happens is that whenever a guess is right, the other two players will pass (because they would see both a H and a T).

H1
Oh, that language was crazy. At first I did not get why was H2 supposed to be harder than H1 - Just type a - after the + and it would revert the effects of the + character. Anyway, I noticed that digits are allowed and that q can type the source code itself. Any digit before there is a buffer does nothing. So we could do TEAM_DISq. The q would print itself though, so we need to remove it somehow. I noticed the ! and ? commands which remove the last or first 47 characters, so I added other 45 useless characters to the source code and put a ! to the end. That was wrong, because ! is the one that removes the first 47 elements. I replaced with a ? before reading the result of the previous submission which said: Detected a ! in buffer.

It turns out the buffer cannot ever have non-alphanumeric characters. It wasn't a big deal, I just used the O command to remove the characters instead, but it removes positions that are primes or powers of two, so I placed the useless characters at those positions.

However, this condition I didn't notice at first is what explains why is H2 much harder, a + in the source code would make you unable to use q.

What now?
There was only one hour left, and it seemed that the next easiest problem was D2. I noticed that if at least one of r or c is even, it is also always possible to make a connected output. The problem was building it. After considering many cases I finally thought of something that could work. But while coding this I noticed that I forgot about how to handle cases that had r=1 or c=1. My construction rule didn't work. By then it was already 1 minute before the end of the contest, so I gave up.

The end
Final ranking position: 216. That was underwhelming. Wait, so you mean this was a team contest? Ok, what happens if I filter out the multiple-people teams? Position 39 out of at least 250, still fairy low . What? Do you mean a single Russian guy was able to get 20 points all by himself? Almost three times the amount of points I got? Oh...

The only thing that bugs me about ISPC is that there is never really time for me to try all of the problems. There is always good things that you miss even trying to solve. I guess that is because the contest is designed for three person teams. The problems are usually so interesting that it is hard to first read all the statements before starting to try to solve one, because you can't resist trying to solve the one you just read.