GCJ 2011 experience

Here is my Google Code Jam 2011  experience. I thought i would blog about it .Below is what was going through my mind during whole contest.

Candy Spliting : (Click to view problem statement)

Not getting any slick approach.One coming to my mind is to go through all the possible subsets using recursion and check which yields maximum answer.But would it fit time constraints ? Small test case N=15 so total number of subsets to be scanned 2^15-1=32767 ,so this would definitely work ..cool lets work this out.Implemented the whole code .Didn't get accepted .What i am doing wrong?.Ah..missed to add string "Case #X:" ,did this change. So finally passed and made my first submission.

Well for long test data N=1000 this mean total number of subsets is equal to the number with ceil(log(2^1000))-1 digits, (assuming the acm style scenario ,10^8 operations per sec this means tx=(60*60*24*365*(10^8)) ..['^' is used for power operation], operations per year ,total time in years to solve candy splitting with this approach would be (2^1000-1)/tx years that too assuming a subset can be generated in 1 operation :O ,probably that would take many many code jams if my math isn't wrong) and this is for single case there will be 100 testcases .This wont gonna work for long test data.But didnt getting any other approach.I'll leave this now.Would come back to this prob later.

GoroSort: (Click to view problem statement)

Somewhat similar to Bogosort.But not  able to reach any solution.Well i would go for this one once i complete rest three.I guess this is tougher than previous one .

Magicka : (Click to view problem statement)

Some sort of simulation.I think if I implement the code in the way exactly mentioned in the statement it would be able to pass for both large and small.Two grids each of size 26x26 could be used to store the combine and oppose relationships .Need to take care of the fact that relationships are symmetrical .So if com[i][j]=1then com[j][i]=1 ,com is the name of grid where i am storing combine relationship same for oppose grid.After this i just need to add element to the list and check the rest of the list for further oppose or combine relations.Implemented the code .Submitted for both small and large test data.Passed for small.Result for large would be available at the end of the contest.

Bot Trust : (Click to view problem statement)

I guess this is the easiest one .Just need to go through the sequence in which both the robots move.And take care of the fact that both the bots can move in parallel.For example in sequence list present move is of blue bot and it moves net distance of 5 units and the next orange bot move require to move next distance of 2 unit so we can move the orange bot to 2 units .Incase the orange bot requires to move 8 units then it would move only 5 units since at present the Blue but is under consideration and it can move only 5 units.Implemented the code but didnt got accepted .Did some mistake in implementation part in calculating net distances ,corrected it and passed for small.Large's statues unknown.

Back To Candy Splitting:

Hmm...What should i try some sought of 0-1 knapsack ,what i am thinking ?aint gonna work.There is something in XOR operation.Should i count the number of times a specific value occured but what i would do with this information.One thing is for sure the solution would only exist if XOR of all the values is zero.Oh my god....I just need to check if XOR of all values is zero and subtract the minimum value of all given values from the sum of all values.Cant believe my code for large data is much small and faster than my code for small data. WOW that feels really nice.

Should I go for Gorosort again ?Have no specific ideas .Plus don't want to work more on this.

Finally all of them passed .70 points out of 100 this year and rank 4509 .Not bad in comparison with my last performance (stood somewhere around 9900 and scored 10 points only).For the First time qualified for   round 1.

Participated in all sub rounds of Round 1 .But missed all time ,mostly due to late submissions for the problem I need to code fast. More precisely get with the correct approach fast. And frame more good solutions.

Was able to solve 1 problem (for both small and large test data) in all sub rounds of round 1 and one more for small test data which was good but not good enough. Well let’s see what happens next time :-).

EDIT: GCJ 2012 was relatively easy .Attempted only few problems to get eligible during  quals
 Did well in round 1 this time (rank 1918)  as compared to last year rank (2000 something)  .But still wasnt eligible for round 2 as it takes top 1000 coders. Hope i can make it next year (or not ?)|:D

SECOND CHANCE

I haven't blogged for long.Actually i was unable to figure out what to blog about.Few weeks ago i watched a show on NGC (national geographic channel) on a true incident.Its about how life gives you second chances(which is very very rare) and how you use them.

There was a guy(i would call him X as i don't remember his name) who was in bad company from his early teens Later at age of 19-20 he started robbery at the stores in Dallas . All this became his habit, like he don't know anything else
Also there was no one around him to tell him that what he is doing is wrong. He was caught by cops in his
early 20s.As mentioned in the show ,there were very strict laws for offenses like robbery during those
days in US by strict mean term of 80 years of imprisonment,which was the punishment of that guy.
According to him life was bit unfair to him as he wasn't aware that he could be jailed for such a long time
and he had no one around him to stop him from doing all the bad stuff and he never intended to kill anyone one
and he never did that.

After spending few weeks in a maximum security prison that guy decided to escape from the prison.Which was a very difficult task but he was fully determined that would to do that.He started analyzing the prison parameter,modeling it with cards,coffee cups ,chess pieces. He managed to find a cutter which he could use to cut the fences but the handles of the cutter were small by which he cant get the grip to cut the fences so he added two pipes to the handles of cutter which provide him sufficient grip he later hide that tool in cold storage .


He involved 2 more convicts in his plan.They managed to arrange a rough map about the area from which they get the idea about the whole geography of the area and how much effort would be needed to get out from the jail.They observed that even if they somehow manage to cross all the fences they'll need to run a distance of minimum 5 miles in a very small time so that they can get out of the reach of cops.For that they decided that they'll do some running every morning .But X was the only one who actually did the running the other two guys didn't.Just few days back before the escape the observed that they need to sabotage the jail power supply both the main supply and backup so that their escape become easy and safe.At the night of escape all three of them assembled during dinner .The generator room was near the mess so a member of team managed to get in the generator room15 minutes passed but there was no power cut so X decided to go to generator room.There he saw his team member was still talking to the guy at generator room.He quickly rushed and hit the guy at generator room and tied him with the shirt and warned him not to make noise.He first sabotaged the backup and later the main supply.After that all of them started to cut the first fence . When they came to second fence X realize this may take some more time so he suggested that they should climb the fence while the other two said its risky and X should cut the fence .X replied if that cutter is making them think that they should cut the fence then he'll throw the cutter on the other side of fence and he actually did that X then said to both of them now we don't have any option .So all three of them started climbing X and one more guy did that in very less time while the trousers of third member of the gang was facing some problems in crossing the fence X get back to him and helped him to get out of fence
Both of them were sighted by a cop and he started shooting at them But they managed to escape
Now they needed to run as fast as they can to get out of the jail parameter.Here the training of running really helped X as he was the only one who managed to run such a long distance in less time while the other two guys struggled and that is why both of them were caught with in next 24 hours.But X finally made it.

Now in my opinion he realized that he did a bad stuff and wanted to live a good and clean life So that is why he get succeeded in this.But there was a twist .

As soon as he get out of the prison he first robbed an old man later bought a toy pistol which looked almost same as real one
and robbed a store. Once he got decent amount of money he started doing the robbery frequently .The cops were smart as usual
and reached the conclusion that X would go to his hometown first .And he actually did that and also started frequent robberies there so this led the cops to reach him and very soon they caught him at a night club.

After watching the show i thought That what would have happened if X had started living a good and a clean life?I don't mean that his prison escape was a right thing.But if he didn't had started the bad stuff there was a small possibility that he could have led a better life. In my opinion super power above showed some mercy on him but he totally wasted it.