Google Code Jam

[Shaddy]

Ended up not having time to participate maybe next year

[Kirby]

Good job, Herman

[Solomon]

Congrats Herman! I tried to do 1C, but it didn't take long before I just felt too tired to keep focus and called it a night after an unsuccessful simple greedy solution. It was fun! Hope to see everyone here next year .

[djhbrown]

post removed by author

[HermanHiddema]

Looking at the scores further, there were 8 people who got 100 points, and a whopping 772 who got 72 points, same as me. So my 516th ranking was mainly lack of speed rather that lack of problem solving ability. If I want to do better, I would have to work on that speed. I must say that doing every problem within a total 44 minutes, as the winner of round 1C did, is nothing short of amazing. My hat off to them.

[djhbrown]

post removed by author

[Solomon]

Trying to derail a thread by advertising your product, especially when it's not relevant to the topic being discussed and doing so while demeaning everyone else participating in this event, is a violation of the forum rules djhbrown. Consider this a warning, next time's a ban (and I removed a link to your product due to its irrelevancy here).

[djhbrown]

i insist that i did not intend to demean anyone, nor to undermine anyone's purpose, least of all those to whom i was appealing.

there is no product; just an idea; a non-copyright idea.

since my post was capable of misinterpretation, and my sense of humour unwelcome, i have removed it.

[apetresc]

It's that time of year again - the qualification round for Google Code Jam 2019 is this weekend And interestingly, here is the header image they chose...

GCJ 2019 banner

2019-04-02-11.04.30.png (187.62 KiB) Viewed 12663 times

I have no idea if this means that some of the problem tracks will include some Go-related content, but that's not impossible given their emphasis in recent years. I guess we'll find out starting this Friday

(By the way, I wonder if anyone recognizes the position on the board? It's not, as far as I can tell, any of the AlphaGo games against Sedol or Ke Jie, though maybe it's one of the hundreds of Master games)

[Waylon]

(By the way, I wonder if anyone recognizes the position on the board? It's not, as far as I can tell, any of the AlphaGo games against Sedol or Ke Jie, though maybe it's one of the hundreds of Master games)

The position is from game 1 AlphaGo vs Fan Hui.

[bernds]

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.

[HermanHiddema]

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.

[Tryss]

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.

[bernds]

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.

[Solomon]

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.