GCJ 2013 - round 1B, problem B

Hello guys,

I believe that someone here participated in round 1B of Google Code Jam 2013.

I’d like to find bug in my B problem solution (easy), so if someone got AC I’d like to compare results of his and mine code.

My code is available on ideone if you want to see it - http://ideone.com/oFM0iU

1 Like

I found the scoreboard with solutions to download, so I downloaded blmarket’s solution for B problem (he/she ended 3rd) and found the “problem”.

His/her solution returns for input 11 1 3 value 0.1875, but I think that correct value is 0.166666667 .
Reasoning is simple, based on brute force and one simple observations, that diamonds creates “pyramids” - when N is 1, 6, 15, 28, … no matter how the diamonds slides (right/left), the final shape is perfect pyramid.

For solutions where N = 11, the pyramid contains 6 diamonds (the blue one). When I was drawing that picture I realized, that the numbers for shapes are from Pascal’s triangle and probably this is the problem - for N = 11 the number of ways is not 32, but only 30 shown on the picture.

all possibilities for N=11

In the picture there are all possibilities for N from 7 to 11, for easier understanding (N=7 first row on the left, N=8 first row on the right, N=9 2. row, N=10 3. row and finally for N=11).

1 Like

You can download other programmers solution who participated in GCJ 2013 round 1B from here- https://code.google.com/codejam/contest/2434486/scoreboard#vt=1&vf=1

And can run and compare with your own solution.

PS:- Also you find out how quick they are. Seriously, man 7 min to solve first problem. That much time i take to read and configure it.

don’t u think round 1B was more tough than 1A?

@betlista >> then the title should say round 1B, problem B? :slight_smile:

@amitupadhyay >> when you are selecting top 1000, then it is tough/easy for all the contestants. I saw Gennady Korotkevich submitting solution A at around 50 minutes with 1 wrong try, and then just managing to submit the rest two problems in the last minutes of the contest and managed to be at rank 109.
To get in top 1000, you had to do Problem 1 short and long and either B short at any time or C short before 1.5 hrs.

@amitupadhyay I don’t think so. Me personaly I had better performance in 1B, but it’s because there was 3am for 1A a 6pm for 1B. I had to advance in 1A. I still believe there is bug in judge for 1B, problem B.

@bugkiller You are correct, thanks

and I couldn’t even read other problems properly, I was so disappointed with my code for Problem A, I gave up many times but then decided lets do it again. Last minute I submitted solution for A. I am performing poor, specially in short contests.
If you have not advanced to round 2 yet, then my best wishes to you. :slight_smile:

@bugkiller same here after 4 retries i got the bug in my program A . managed to submit it at 1 hr 51 minutes… ah morning i had an exam…then GCJ… all messed up… hope round 1C goes good for me :slight_smile:

What did you use to draw this?

Correction: 6 minutes! :smiley:

with practice they know how to use a language properly, and they get the algorithm by reading the problem, so they just implement it. and its guaranteed to be perfect; while we, beginners find problems in finding the exact algorithm, then when implemented we have to debug. :smiley:

mspaint from windows O:-)

1 Like

=> actually on 2nd thought there is a mistake in your ananswer
in the last stage when you have all those possibilities, what we are mistaking is all of them have equal probability which isn’t true
it shd be because the piece had 50% chance to go either side so it adds up to 2x more proabable in those cases where there is only one direction to go

6 10 10 6
=> 6/32 = 0.1875

2 Likes

I understand what you wanted to say, but the fact that in first case for N=10 next diamond cannot slide to the left doesn’t make the other possibility more probable, does it?

I was thinking about it and it seems, that you are right. For case N=10 and first possibility, when diamond falls in 2 attempts, both ends with N=11 first case, but for N=10 and second case, it ends ones as N=11, first and once as N=11, second. Thanks for helping :wink: