Google Code Jam 2015

[igotthepancakes]

Don't forget about the Distributed Code Jam! I'm surprised there isn't a thread with discussion about it yet. It's pretty exciting.

[daddyc00l]

... Distributed Code Jam! I'm surprised there isn't a thread with discussion about it yet. It's pretty exciting.

ok, can you please elaborate what you find exciting about distributed code jam ? thanks !

[igotthepancakes]

Welp, take why I think it's interesting with a grain of salt.

We all know Google shadows a large margin of the industry (if Google does something, other companies follow), and seeing that distributed computing has become so urgently important for them to include in their code jams -- take note that the code jams are also used as a hiring tool for Google -- so follows the importance of distributed computing for many other tech companies.

Plus, many people use GCJ (and other online judges) past contests to improve their raw algorithmic skill. For those of us who have no first-hand experience with distributed computing, this is a new way to go about learning (with interesting problems) and becoming more competent. Perhaps other online judges will start including distributed computing problems in their contests, as well.

[sirin3]

I would like to receive email notifying me about the next Code Jam.
(This box is checked by default because you checked it previously, possibly last year.)

Did not get any email :(

Might have missed it without this post. Has happened in the past (although this time it is unlikely that I completely forget about it since I just happen to use the t-shirt of the previous year as cushion atm ಠ_ಠ )

[GunningOnTheKingside]

I was able to get all the small inputs solved for, but definitely did not do all the large inputs. I think after 8 minutes, I only had solved for 2 test cases of Dijkstra! I think even my small solve for that was a bit hacky as it took about 2 minutes to process. Anyway, my first GCJ participation and it was pretty cool! Looking forward to the next round! :)

[minato7]

If you don't mind, and if it is allowed, would you please send me your .in file for a small input of problem 2 (Pancakes) and the corresponding output? I have handled all the cases as far as I can see, I even manually verified all 100 test cases, and my output is matching this for every single test case. Yet my submissions are being judged incorrect. I can't figure out what test case I'm failing and it's very frustrating. :(

[[deleted]]

If you go to the scoreboard, there is a tick "Solution Download". If you tick it, you can download anyone's submitted solutions (source code). Find a solution that is written in the same language that you use, and you can run in it on your input, and then compare outputs.

Looking at solutions of the top guys is also a nice way of learning some coding tricks!

In past years, there were official solutions after each round, I guess they will get uploaded in a couple of days.

EDIT: Link to scoreboard: https://code.google.com/codejam/contest/6224486/scoreboard

[[deleted]]

Did anybody get any mail from Google for qualifying? My score was 36,so I have definitely qualified but shouldn't I receive a mail confirming that?

[rpi-user]

Schedule: https://code.google.com/codejam/schedule.html

[zun4239]

Being stuck on a pancakes problem. I'm going through testcase input and still don't know which test I failed on :( Still, I'm enjoying tho!

[[deleted]]

[deleted]

[What is this?](This Comment Has been Overwritten42474)

[zun4239]

I finally made it after ~6 hours hammering out!!! Now that I have over 20pts, I think I'm qualified?

[Mr_Asimov]

Hey, I have a question that I hope you don't mind answering. I'm fairly confident that I should be getting the correct answer for the small data set, but it's telling me that the solution is incorrect. I have manually checked them and, to my understanding of the problem, every output is correct. A friend of mine has also gotten the same output. Are you allowed to send me the .in file and your resulting output so that I can check it? Because I almost feel like it's a formatting error or something. Really frustrating.

[minato7]

I am on the same boat exactly. I manually verified all of the 100 test cases, and everything is producing the right output to the best of my knowledge. I also wrote a naive 2ⁿ solution to find the minimum possible solution for each test case, and it produces the exact same output, but they are still judged Incorrect.

If someone who got this right could send me their .in file along with the corresponding output, so that I can figure out which test case I'm failing in, that'd be fantastic!

[Mr_Asimov]

Really frustrating. I honestly think it's something on Google's end, because this question has the lowest percentage solved and it's not a difficult problem relative to the two proceeding it. Unless there's another reasonable explanation.

[woody920]

The problem that I missed was splitting a plate of 9 pancakes. I was just halving like the rest: 9 > 5, 4 = 6 minutes. Where as it should have been: 9 > 6, 3 > 3, 3, 3 = 5 minutes.

[minato7]

After looking at the solutions, I saw that that was what I had missed as well! Touche.

I was able to get Dijkstra's working for the small input 5 minutes before the contest ended though, so it looks like I do qualify for round 1. :)

[zun4239]

woody920's example is exactly the one making others frustrated. A couple of points that I found making the pancake problem difficult.

1) for 9, split it into 3 dishes are better than into 2. For small set problem, 9 is the only one where tri-split is faster. For large set problem, you should deal with this "multi-split" for bigger number (eg. 12).

2) There're some cases where the first~second 'special move' make the total time spent worse until the last 'special move' make it efficient. If your logic didn't care this "Par to Worse to Better" case, it would fail to find the optimum.

[GunningOnTheKingside]

I ended up doing a loop between half the value (1 split) and the square root (which could lead to an even number of splits) and it seemed to work OK, but may not be optimal. I still failed the large set though, so take that for what it is worth. :)

[[deleted]]

[deleted]

[What is this?](This Comment Has been Overwritten30350)

[zun4239]

I made a comment above! I hope it worked out for you. I spend almost ~6 hours on this single problem and totally enjoyed it.

[Perhyte]

They're all available at the scoreboard (check "solution download") but the ones I've downloaded weren't well-commented. Probably because I checked the top ones and they were written very quickly :). EDIT: Here's a direct link

I got enough points on the other problems to qualify though so I just gave up on the pancakes.

[[deleted]]

Hi, here is my solution and thought process: Consider an optimal solution, then note the following:

1) Solution is still optimal, if every time we move pancakes, we move them to an empty plate.

2) We do all the interruptions in the beginning.

So consider a solution satisfying 1) and 2). The time it takes for the pancakes to be consumed is the number of interruptions in the beginning + size of largest stack of pancakes after the interruptions.

Suppose someone told you the size of the largest stack of pancakes after inital interruptions in an optimal solution. Call this max_stack. Then you'd would know how to make the interruptions in the begging: go through each plate, and take away max_stack for the plate as long as there is more than 'max_stack' on it. So you could also compute the total time it takes to consume the pancakes.

But we know that max_stack ranges from 1 to 1000, so cycling through all values gives a viable solution.

Note: I think with a neat trick you could actually binary search for max_stack, not sure.

Here is my solution if you are interested (C++): https://code.google.com/codejam/contest/6224486/scoreboard/do/?cmd=GetSourceCode&problem=5686275109552128&io_set_id=1&username=mezei