Google CodeJam 2011 GoroSort!!! 55pts on to next round.

• Tweet

• Tweet

GORO!!!

All I had to do was find the number of elements out of place!! I actually thought I tried that!  GCJ

Well, I got 3/4 problems correct. On one of them I didn’t get the Long data set because I didn’t realize I could only try once so I had not yet optimized my code (I thought I could gauge how much optimization I would require by trying a large data set first). So only 55pts out of 100pts. But I only needed 30pts to advance. I was hoping to do better, but – not bad for about a month of coding in Python.

I’ll have to get a bit quicker for the next round because my lack of experience requires too much time to implement solving strategies at the moment . Although, I would have achieved the same score this round whether I had 2.5hrs or 24hrs – I just wouldn’t have worked so hard on beating Goro!

It was fun though (fun like I wanted to find Goro and crush him for eating up so much of my time in futile attempts).

Second Edit: ADDED

Wouldn’t you know it, I was being sloppy when I coded the simulation below! I just had time to take it a look at it. Fixed an error. And then when I run the numbers a cycle of 3 takes 3 hits on average, a cycle of 4 takes 4 hits…  Even I would have noticed that pattern Argg.  I should have gotten this!

Edit: ADDED

Here was a description of one attempt of my failed logic I guess:

I haven’t spent the time to understand the proof, but during the comp, at one point, I tried simulating the situation for different ‘cycles’. Randomly generated a permutation for a cycle of 2 [2,1]. Did it 100000 times and divided to get the average. It was roughly 2.

So I tried a cycle of 3 [2,3,1]. Random permutation, check for correct positions, freeze them, random permute remaining (or on larger cycles I just added previous simulation’s cycle results – ie for cycle of 2 added 2.00 at that point).

I was trying alot of stuff during the compy, so may have been sloppy, but my simulations were giving different numbers than that proof sould suggest.

cycle 3 – 3.5 (as opposed to 3)
cycle 4 – 5.25 (as opposed to 4)
cycle 5 – 6.4… (as opposed to 5)

???

Is that weird? Then with those numbers I found all cycle’s in the set and added the numbers I found. Obviously that was incorrect like my other tries.