Sunday, April 01, 2012

Codeforces April Fools Day Contest

What a lame contest. Everything was badly specified, one of the problem statements was corrupted or something. In another the problem didn't even know the name of the language it was using. Codeforces has somehow managed to out-fail itself*.

Problem A - Mysterious numbers
Somehow I first understood output a single integer as output any integer. Soon I learned it meant that I had to somehow find out what integer to print given an input.

I was baffled for the whole round. I switched to other problems and was solving them. Then when the only other two problems left were the one that is a harder version of the very same idea as A and the one that seemed like a brain melting challenge, I decided to return to this problem for the last 20 minutes. I was still unable to find the way to get 44 out of 3 and 13 AND 102 from 100 and 200.

So when the contest ended I opened the solutions from the first place and found the sad true. (facepalm). It is just the addition between A and a reversed B. So, a = 3, b = 14 then c = 3 + 41. This is embarrassing. I actually told myself "Try something about digits" in one of those minutes, but somehow still missed this whole thing.

Problem B - B a star
It was about counting the number of balls in a star like the one in the graphic, but of size a. Can split the problem into counting the borders for each length and then summing them out.

Note that the size determines the length of each side. Then you can multiply your side length by 12 and then subtract 12. Except for the first ball.

The result is 1 + sum(2 <= i <= a, 12 * (i - 1) )

Problem E - Unknown language The trick was just to use the custom test thing. And force a compile error to appear. Then maybe with the compile error you can find out what the compiler is.

So I gave it a c++ program and hit compile. I received compile error, a very strange-looking error code and "DO YOU REALLY EXPECT ME TO FIGURE THIS OUT". I googled for that stuff and it turns out that it is a very specific INTERCAL thing.

Unfortunately, I still had to actually print the text "INTERCAL" using the intercal programming language, which is esoteric. I have never actually read Intercal code in the past. After some research, I found a Hello world program. And it was impossible to understand, so I kept looking for tutorials about how to write hello world and actually found this link: http://divingintointercal.blogspot.com/2007/03/part-dalawa-still-trying-to-write-hello.html . It was very helpful.

Turns out that even knowing how the language works, it is still non-trivial to write even a program that prints a text constant. But I am a programmer, and as such I am lazy. So I just wrote me a python program to write the intercal program:

def bin8(x):      s=''      while x > 0:          s = s + str(x%2)          x /= 2      while len(s) < 8:          s = s + '0'      return s  def rev8(s):     x = 0     for ch in s:         x *= 2         if ch == '1':             x += 1     return x      s  = 'INTERCAL'  print "PLEASE NOTE THAT IT WAS WAY EASIER THAN I THOUGHT TO FIND OUT WHAT THE PROGRAM IS" print "DO NOT THINK THAT MEANS THE PROBLEM WAS EASY, I HAD NO IDEA HOW TO CODE IN INTERCAL BEFORE THIS"  print "DO ,1 <- #%d" % (len(s))  cur = 0 count = 1 for ch in s:     to = rev8(bin8(ord(ch)))     # cur - x = to mod 256     # x = cur - to mod 256     x = (cur - to + 256*256) % 256     print "DO ,1 SUB #%d <- #%d" % (count, x)     count += 1     cur = to print "PLEASE READ OUT ,1" print "PLEASE GIVE UP"

The bad news is that once I finished this whole thing and learned more than I ever needed to know about Intercal, I noticed I somehow wasted almost an hour doing all of this :/

Problem D - Broken checker
The next problem that was not problem A and had the most submissions was D. It turns out that this one specifies nothing. Only the constraints on the input and the output.

The trick here is to grab control of the checker and make it work for you. Since you don't even know what specific input a test number has. I just did something to force the checker to say "Runtime error" (I did some code that forces a segfault) once you find the integer in the input, try 1,2,3 until the first test is correct. Then try to figure out the input in the next test and so and so. Mid-way I noticed that you could save up on the number of attempts if, besides of luck, you made sure to keep crashing the program for a new input value in case you find the correct answer for the one you are reverse engineering in the current attempt.

Problem F - ucyhf
So, this time it seemed like the problem statement was encrypted. And indeed it was. I assumed a typical encryption scheme that replaces a letter with another. And well, it worked. Since all the problems follow the same format, it was easy to see that "ekjfkj q iydwbu dkcruh" must mean "output a single number". After that you can keep replacing letters until you find that the first text makes some sort of sense and you can complete the new unknown letters. I once again used python for this.

CODED   = 'ekjfkj q iydwbu dkcruh jxu sediyiji ev-.tn' DECODED = 'output a single number the consists of-.dx'   s1 = 'jxu ydfkj sediyiji ev q iydwbu ydjuwuh d () - jxu edu-rqiut ydtun ev jxu ucyhf je vydt.' s2 = 'ekjfkj q iydwbu dkcruh'  vec = [s1, s2]  for s in vec:     res = ''     for ch in s:         dec = '#'         for i in range(0, len(CODED)):             if CODED[i]==ch:                 dec = DECODED[i]         res = res + dec     print res

Problem H - A polyline
It was hard to notice for me because the red lines don't contrast too well with the black ones. But this problem asks you, given a, the number of times the fractal in the image is repeated. To find out the position you will end up in after moving b times in the polyline.

I am sure there is a solution. I somehow thought that it was more profitable to finally understand problem A rather than try to think of a strategy to find a solution to this fractal. I think that was a mistake.

* April fools!

PS: I cannot underline how much the new blogger interface sucks. It took me a lot longer than usual to write this post because it no longer adds line breaks for you. If it turns out I can still use adsense, I might switch to wordpress - I've been working with it for the first time in the TCO blog and it is way better than blogger (WAAY better, specially after these lame interface changes, but even without them). Heck, I might even switch to wordpress without adsense. Because it is not like this blog makes that much anyway.