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

Google Code Jam
http://lifein19x19.com/viewtopic.php?f=8&t=5819		 Page 2 of 6
Author:  Kirby [ Thu Apr 06, 2017 5:24 pm ]
Post subject:  Re: Google Code Jam
hyperpape wrote:
I'm glad you posted that, because I've been mulling over participating and had not realized it started tomorrow afternoon.

How long did the qualifying round take you in previous years?


Probably most useful to take a look at last year's qualifying round, to get a better idea:

https://code.google.com/codejam/contest ... /dashboard
Author:  Solomon [ Fri Apr 07, 2017 8:45 am ]
Post subject:  Re: Google Code Jam
hyperpape wrote:
How long did the qualifying round take you in previous years?
I only participated one other time in 2015, and despite being given 27 hours, I only managed to solve 1 problem (A, the easiest one). Hoping that changes today!
Author:  Kirby [ Sat Apr 08, 2017 12:15 am ]
Post subject:  Re: Google Code Jam
I ended up doing "Tidy Numbers" small and large, along with "Bathroom Stalls" (the small set). These seemed like the easiest to do, so I worked on them first.

I think my implementation for the large set for "Tidy Numbers" is correct (looking briefly through the output file, it looked OK).

For "Bathroom Stalls", the program I wrote didn't scale. I started out with this problem wanting to represent the stalls as bits in a long, since that should have enough space to hold 10^18 "stalls". But it wasn't immediately clear to me how to quickly calculate Ls and Rs on the bitset. When it got a bit late, I decided to just make a simple brute force solution that would solve the small set (should be enough for 25 points if the large set for "Tidy Numbers" was correct).

I plan to do stuff with my kids tomorrow, so I probably won't complete the others. Just skimming the other problems, pancake flipping seemed like a dynamic programming problem, and I didn't think about the last one that much (brute force?).

It was a fun Friday activity. Hopefully my large for "Tidy Numbers" was correct so I have incentive to continue for the next round.
Author:  Shaddy [ Sat Apr 08, 2017 4:16 am ]
Post subject:  Re: Google Code Jam
It is 4 AM. I can't stop thinking about D. Fashion Show. I think I've figured it out..
Author:  hyperpape [ Sat Apr 08, 2017 5:28 am ]
Post subject:  Re: Google Code Jam
I haven't actually submitted anything yet, but I have a solution written and tested for Tidy Numbers. It took me longer than I expected, maybe an hour? Lots of ugly nested conditionals. I'm about halfway through a solution Bathroom Stalls, and I think my approach will scale to the large set.

Fashion and the Pancake Flipper, I don't really know what to do.
Author:  gamesorry [ Sat Apr 08, 2017 9:33 am ]
Post subject:  Re: Google Code Jam
I'm traveling in Boston so only had time to code up the first two problems last night. For problem 3 I figured out some properties. Will see if I could verify them tonight before the contest ends...
Author:  HermanHiddema [ Sat Apr 08, 2017 10:35 am ]
Post subject:  Re: Google Code Jam
Decided to give it a try too :)

Problem 1 (pancake flipping) was easy. Took me about 15 minutes to get a linear time solution (O(N) where N is the number of pancackes)

Problem 2 (tidy numbers) was also easy. Took me about 30 minutes for a linear time solution (O(N) where N is the number of digits)

Problem 3 (bathroom stalls) was slightly more difficult, but not hard. I had a logarithmic time solution (O(log2N) where N is the number of people) in an hour, but it took me another hour to find the off-by-one error that made my first submission incorrect. Typical case of having <= instead of < somewhere and failing on rare edge cases. Actually coded another (linear time) solution to find the error :mrgreen:

Problem 4 (fashion models) I'm probably not going to try. I have some ideas, but I have another appointment right now, and the contest closes in about 8 hours. Maybe when I get back, if I haven't drank too much for it :)
Author:  Kirby [ Sat Apr 08, 2017 11:30 am ]
Post subject:  Re: Google Code Jam
Wow, you guys are fast :-)

At the zoo with my kids now so I won't be able to get more points before the 27 hours, but I feel compelled to finish the rest now.
Author:  hyperpape [ Sat Apr 08, 2017 12:00 pm ]
Post subject:  Re: Google Code Jam
Herman is not only fast, but also weird! Pancakes are obviously harder than Tidy Numbers or Bathroom Stalls. At least he agrees the fashion show one was harder than the other three.
Author:  Shaddy [ Sat Apr 08, 2017 12:34 pm ]
Post subject:  Re: Google Code Jam
hyperpape wrote:
Herman is not only fast, but also weird! Pancakes are obviously harder than Tidy Numbers or Bathroom Stalls. At least he agrees the fashion show one was harder than the other three.

I also thought pancakes was the easiest.
Author:  hyperpape [ Sat Apr 08, 2017 2:07 pm ]
Post subject:  Re: Google Code Jam
I'm just gonna sit here and keep pounding the table and saying it's obviously harder.

In all seriousness, I'm not completely surprised. Pancakes looks like the sort of combinatorial problem that has a quick and clever solution that I can never see, whereas Tidy is a straightforward programming exercise.
Author:  Kirby [ Sat Apr 08, 2017 2:22 pm ]
Post subject:  Re: Google Code Jam
I haven't given pancakes a shot yet, so maybe I'll start on that one tonight. I got a bit hung up on making a scalable bathroom stalls solution, but maybe I'll come back to that later. There might be a property I'm missing to identify spacing between stalls quickly.

I'll think about it some more after trying pancakes.

Pretty sure pancakes can be solved with dynamic programming, but I don't have the full picture in my head, yet.

Probably something like finding minimal number of flips for K pancakes, store it, then look to see if you can do better by flipping K+1. Not quite sure yet, but I'll think about it tonight.
Author:  gamesorry [ Sat Apr 08, 2017 4:22 pm ]
Post subject:  Re: Google Code Jam
Pancakes is indeed the easiest because a simple strategy is easy to be proved imho
Author:  Kirby [ Sat Apr 08, 2017 4:32 pm ]
Post subject:  Re: Google Code Jam
Back from the zoo now, and the kids are playing... So I'll give the pancake problem another shot.

I thought about it more, and I may be making things too complicated.

I think I'm just going to try to do a simpler way to see if that works.
Author:  Shaddy [ Sat Apr 08, 2017 5:23 pm ]
Post subject:  Re: Google Code Jam
I've written 200 lines of code for Fashion Show and I'm so unhappy

I'm probably going to be angry after I see what the answer is supposed to be
Author:  Solomon [ Sat Apr 08, 2017 5:51 pm ]
Post subject:  Re: Google Code Jam
Shaddy wrote:
I've written 200 lines of code for Fashion Show and I'm so unhappy

I'm probably going to be angry after I see what the answer is supposed to be
tfw you look at a top user's code for Fashion Show and it's less than 30 lines of code.
Author:  Shaddy [ Sat Apr 08, 2017 6:04 pm ]
Post subject:  Re: Google Code Jam
why doesnt c++ have hash support for tuples

i want to die
Author:  Shaddy [ Sat Apr 08, 2017 6:25 pm ]
Post subject:  Re: Google Code Jam
I GOT AC ON D-SMALL

YES!!!!!
Author:  Shaddy [ Sat Apr 08, 2017 7:17 pm ]
Post subject:  Re: Google Code Jam
How'd everyone do?

I missed D-large.
Author:  Solomon [ Sat Apr 08, 2017 7:22 pm ]
Post subject:  Re: Google Code Jam
Failed on 2 larges unfortunately, but still managed to advance to R1 w/ 35 points. It was fun! Hopefully I can advance to Round 2 through Round 1C, which I heard is the easiest since 2000 of the 3000 who would have advanced already go through, and it's at a weird time for anyone outside the US (2am PST). Good job on getting half of D Shaddy!
Page 2 of 6 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/