It is currently Mon Apr 22, 2019 7:17 am

 All times are UTC - 8 hours [ DST ]

 Page 6 of 6 [ 105 posts ] Go to page Previous  1, 2, 3, 4, 5, 6
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: Google Code Jam #101 Posted: Sat Apr 06, 2019 9:54 am
 Lives with ko

Posts: 149
Liked others: 19
Was liked: 47
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

 Post subject: Re: Google Code Jam #102 Posted: Sat Apr 06, 2019 11:26 pm
 Gosei

Posts: 1964
Location: Groningen, NL
Liked others: 196
Was liked: 1062
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

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

Posts: 366
Liked others: 0
Was liked: 86
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

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

Posts: 149
Liked others: 19
Was liked: 47
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

 Post subject: Re: Google Code Jam #105 Posted: Mon Apr 08, 2019 6:33 am
 Gosei

Posts: 1840
Location: Bellevue, WA
Liked others: 89
Was liked: 835
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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 6 of 6 [ 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 forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Life In 19x19.com General Topics    Introductions and Guidelines    Off Topic    Announcements    General Go Chat    Beginners    Amateurs    Professionals       Lee Sedol vs Gu Li    Go Rules    Forum/Site Suggestions and Bugs    Creative writing    Tournaments       Ride share to tournaments Improve Your Game    Game Analysis    Study Group    Teachers/Club Leaders       Teacher advertisements    Study Journals L19²GO (Malkovich)    1-on-1 Malkovich games    Big Brother Malkovich games    Rengo Games    Other versions of turn-based games Go Gear    Go Books    Go Book Reviews    Computer Go    Gobans and other equipment    Trading Post    New Products/Upgrades/Sales Go Club Forums    Go Club Discussions       Honinbo Go League    American Go Association Forum       Go Congress 2011 volunteers       AGA volunteers ( non-congress)    Australian Go Association    European Go Federation Forum    Singapore Weiqi Association    KGS    ASR League    IGS    OGS    Tygem    WBaduk    Turn Based Servers    Insei League Events    Kaya.gs       King of the Hill