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.
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.
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 .
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.
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
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
