Life In 19x19
http://lifein19x19.com/

Google Code Jam
http://lifein19x19.com/viewtopic.php?f=8&t=5819		 Page 6 of 6
Author:  bernds [ Sat Apr 06, 2019 9:54 am ]
Post subject:  Re: Google Code Jam
No Go-related content in any of the qualification round problems.

Is anyone else participating? Last year I lost interest in the real competition rounds due to the time limit, but two of the qualification problems this time are at least reasonably fun.
Author:  HermanHiddema [ Sat Apr 06, 2019 11:26 pm ]
Post subject:  Re: Google Code Jam
I joined. Problems 1 and 2 were extremely simple, took me less than 10 minutes each. Problem 3 was harder, that took me about an hour. Didn't attempt problem 4.
Author:  Tryss [ Sun Apr 07, 2019 3:45 am ]
Post subject:  Re: Google Code Jam
Yeah, problems 1 & 2 were a joke, you don't even need a computer to solve them.

For the problem 1, 165498416436549879654 = 000200200200020000002 + 165298216236529879652 , For the fisrt number, replace all non 4 by 0 and all 4 by 2, and for the 2nd number, all 4 by 2

For the problem 2, EEESSESSSEEESSSSESS -> SSSEESEEESSSEEEESEE , Invert the S and E

Third problem was more interesting, even if the easy case could be "bruteforced" (you could test all prime numbers in the range). There still possible complications if it start by something like ABABCDE.
Author:  bernds [ Sun Apr 07, 2019 4:52 am ]
Post subject:  Re: Google Code Jam
Tryss wrote:
Yeah, problems 1 & 2 were a joke, you don't even need a computer to solve them.

For the problem 1, 165498416436549879654 = 000200200200020000002 + 165298216236529879652 , For the fisrt number, replace all non 4 by 0 and all 4 by 2, and for the 2nd number, all 4 by 2

For the problem 2, EEESSESSSEEESSSSESS -> SSSEESEEESSSEEEESEE , Invert the S and E

Third problem was more interesting, even if the easy case could be "bruteforced" (you could test all prime numbers in the range). There still possible complications if it start by something like ABABCDE.


Hmm, I also thought problem 2 was trivial, but your solution is even simpler than mine.

For problem 3 the trick was to realize that if you have A*B and B*C, you can use the GCD algorithm to get B. From there you can get all the other primes just through division. It gets a little tricky beceause you might have the plaintext starting with something like "CCCCC" or "ABABABAB", so you have to look for the point in the ciphertext where you have two different numbers, do the GCD once, and work forwards and backwards. The main problem I had was that they wouldn't link my C++ program with libgmp, so I rolled my own string-based bignum division. Ugh.

For Problem 4 I only got the first set of inputs right. It's a binary search. Let's say you are testing eight bits: you send 11110000, and after the response you will know exactly how many bits are missing in the first and in the second half. So, repeat again with 11001100 and so on. That gets the job done exactly in the number of steps allowed.

I suppose you could do better: if you know that there are at most 3 bits missing, you might be able to send 11100011. Now you have three sub-regions, and would still be able to work out from the response what's going on inside them. But I couldn't quite convince myself that this would be good enough in all cases and didn't submit a solution.
Author:  Solomon [ Mon Apr 08, 2019 6:33 am ]
Post subject:  Re: Google Code Jam
Is it just me, or did they make it kinda difficult to find the analysis of the problems? Here it is in their old layout: https://codejam.withgoogle.com/2018/cha ... 000008830b

Also, agreed that A and B were much simpler than I expected, feel like the bar to reach round 1 is a low lower this year.
Page 6 of 6 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/