It is currently Thu Mar 28, 2024 4:10 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
Author Message
Offline
 Post subject: Re: Google Code Jam
Post #101 Posted: Sat Apr 06, 2019 9:54 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #102 Posted: Sat Apr 06, 2019 11:26 pm 
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
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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #103 Posted: Sun Apr 07, 2019 3:45 am 
Lives in gote

Posts: 502
Liked others: 1
Was liked: 153
Rank: KGS 2k
GD Posts: 100
KGS: 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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #104 Posted: Sun Apr 07, 2019 4:52 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
Tryss wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: Google Code Jam
Post #105 Posted: Mon Apr 08, 2019 6:33 am 
Gosei
User avatar

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

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

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