It is currently Sun Jul 23, 2017 3:51 pm

All times are UTC - 8 hours [ DST ]




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

Posts: 7442
Liked others: 1353
Was liked: 1146
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

_________________
Discipline is remembering what you want. -David Campbell

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

Posts: 1820
Location: Bellevue, WA
Liked others: 89
Was liked: 814
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 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
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.

_________________
Discipline is remembering what you want. -David Campbell

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: 1153
Liked others: 51
Was liked: 165
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 
Oza

Posts: 3990
Location: North Carolina
Liked others: 395
Was liked: 657
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 
Dies with sente

Posts: 124
Liked others: 157
Was liked: 41
Rank: Chinese 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: 1895
Location: Groningen, NL
Liked others: 188
Was liked: 1011
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 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
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.

_________________
Discipline is remembering what you want. -David Campbell

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

Posts: 3990
Location: North Carolina
Liked others: 395
Was liked: 657
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: 1153
Liked others: 51
Was liked: 165
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 
Oza

Posts: 3990
Location: North Carolina
Liked others: 395
Was liked: 657
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 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
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.

_________________
Discipline is remembering what you want. -David Campbell

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

Posts: 124
Liked others: 157
Was liked: 41
Rank: Chinese 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 
Judan

Posts: 7442
Liked others: 1353
Was liked: 1146
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.

_________________
Discipline is remembering what you want. -David Campbell

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: 1153
Liked others: 51
Was liked: 165
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: 1820
Location: Bellevue, WA
Liked others: 89
Was liked: 814
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: 1153
Liked others: 51
Was liked: 165
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: 1153
Liked others: 51
Was liked: 165
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: 1153
Liked others: 51
Was liked: 165
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: 1820
Location: Bellevue, WA
Liked others: 89
Was liked: 814
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  [ 98 posts ]  Go to page Previous  1, 2, 3, 4, 5  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 2 guests


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