I wonder if anyone here managed to solve Problem D Small in the recent Google APAC Test. I implemented my approach yet it somehow failed to cope with the small test case.↵
↵
Link to problem: [https://code.google.com/codejam/contest/5264487/dashboard#s=p3](https://code.google.com/codejam/contest/5264487/dashboard#s=p3)↵
↵
My approach:↵
↵
1. Assume P=0, solve the problem for no swapping by keeping the minimum and maximum value of first n values. Divide the array into non-overlapping segments.↵
↵
2. Iterate through each segment, check the leftmost and rightmost position that could be used for dividing the segment into two. Say the segment [seg] = [a] + [b], check for all [a] and [b] where min(a[]) > max(b[]).↵
↵
3. Check for positions between the leftmost and rightmost. Say [seg] = [a] + [mid] + [b], solve [mid] for [P] = 0 for P = 0.↵
↵
4. Find the best segment to be used for further dividing for swapping. This should be the answer... Except it isn't according to judge. =[↵
↵
Link to my code: [http://pastebin.com/Sa5m7hVE](http://pastebin.com/Sa5m7hVE)↵
↵
Any help is appreciated. =]↵
↵
The problem D Large seems interesting with P = 3, and only two contestants solved it during the contest.
↵
Link to problem: [https://code.google.com/codejam/contest/5264487/dashboard#s=p3](https://code.google.com/codejam/contest/5264487/dashboard#s=p3)↵
↵
My approach:↵
↵
1. Assume P=0, solve the problem for no swapping by keeping the minimum and maximum value of first n values. Divide the array into non-overlapping segments.↵
↵
2. Iterate through each segment, check the leftmost and rightmost position that could be used for dividing the segment into two. Say the segment [seg] = [a] + [b], check for all [a] and [b] where min(a[]) > max(b[]).↵
↵
3. Check for positions between the leftmost and rightmost. Say [seg] = [a] + [mid] + [b], solve [mid] for [P] = 0 for P = 0.↵
↵
4. Find the best segment to be used for further dividing for swapping. This should be the answer... Except it isn't according to judge. =[↵
↵
Link to my code: [http://pastebin.com/Sa5m7hVE](http://pastebin.com/Sa5m7hVE)↵
↵
Any help is appreciated. =]↵
↵
The problem D Large seems interesting with P = 3, and only two contestants solved it during the contest.
