It is currently Thu Mar 28, 2024 4:40 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 105 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6  Next
Author Message
Offline
 Post subject: Re: Google Code Jam
Post #21 Posted: Thu Apr 06, 2017 5:24 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #22 Posted: Fri Apr 07, 2017 8:45 am 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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!

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #23 Posted: Sat Apr 08, 2017 12:15 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #24 Posted: Sat Apr 08, 2017 4:16 am 
Lives in sente
User avatar

Posts: 1206
Liked others: 51
Was liked: 192
Rank: KGS 5d
KGS: Str1fe, Midorisuke
It is 4 AM. I can't stop thinking about D. Fashion Show. I think I've figured it out..

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #25 Posted: Sat Apr 08, 2017 5:28 am 
Tengen

Posts: 4380
Location: North Carolina
Liked others: 499
Was liked: 733
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
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.

_________________
Occupy Babel!

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #26 Posted: Sat Apr 08, 2017 9:33 am 
Lives with ko

Posts: 149
Liked others: 276
Was liked: 49
Rank: 3d
KGS: 3d
DGS: 3d
OGS: 3d
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...

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #27 Posted: Sat Apr 08, 2017 10:35 am 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
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 :)

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #28 Posted: Sat Apr 08, 2017 11:30 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #29 Posted: Sat Apr 08, 2017 12:00 pm 
Tengen

Posts: 4380
Location: North Carolina
Liked others: 499
Was liked: 733
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
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.

_________________
Occupy Babel!

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #30 Posted: Sat Apr 08, 2017 12:34 pm 
Lives in sente
User avatar

Posts: 1206
Liked others: 51
Was liked: 192
Rank: KGS 5d
KGS: Str1fe, Midorisuke
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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #31 Posted: Sat Apr 08, 2017 2:07 pm 
Tengen

Posts: 4380
Location: North Carolina
Liked others: 499
Was liked: 733
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
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.

_________________
Occupy Babel!

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #32 Posted: Sat Apr 08, 2017 2:22 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #33 Posted: Sat Apr 08, 2017 4:22 pm 
Lives with ko

Posts: 149
Liked others: 276
Was liked: 49
Rank: 3d
KGS: 3d
DGS: 3d
OGS: 3d
Pancakes is indeed the easiest because a simple strategy is easy to be proved imho

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #34 Posted: Sat Apr 08, 2017 4:32 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #35 Posted: Sat Apr 08, 2017 5:23 pm 
Lives in sente
User avatar

Posts: 1206
Liked others: 51
Was liked: 192
Rank: KGS 5d
KGS: Str1fe, Midorisuke
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

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #36 Posted: Sat Apr 08, 2017 5:51 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #37 Posted: Sat Apr 08, 2017 6:04 pm 
Lives in sente
User avatar

Posts: 1206
Liked others: 51
Was liked: 192
Rank: KGS 5d
KGS: Str1fe, Midorisuke
why doesnt c++ have hash support for tuples

i want to die

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #38 Posted: Sat Apr 08, 2017 6:25 pm 
Lives in sente
User avatar

Posts: 1206
Liked others: 51
Was liked: 192
Rank: KGS 5d
KGS: Str1fe, Midorisuke
I GOT AC ON D-SMALL

YES!!!!!


This post by Shaddy was liked by 2 people: gamesorry, Kirby
Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #39 Posted: Sat Apr 08, 2017 7:17 pm 
Lives in sente
User avatar

Posts: 1206
Liked others: 51
Was liked: 192
Rank: KGS 5d
KGS: Str1fe, Midorisuke
How'd everyone do?

I missed D-large.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #40 Posted: Sat Apr 08, 2017 7:22 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
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!

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 105 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group