A better way to see the swapping is: (2, 1, 1, 0) <--- The only element that can be put at the first position is the 0, so move it (3 swaps needed). (2, 1, 0, 1) (2, 0, 1, 1) (0, 2, 1, 1) --------------- (0, 2, 1, 1) <--- The 2 cannot be there so move the closest one to it (1 swap needed). (0, 1, 2, 1) --------------- (0, 1, 2, 1) <--- The 2 can be there, so don't move anything (0 swaps). --------------- (0, 1, 2, 1) <--- The rightmost 1 can be there, so don't move anything (0 swaps).
Total swaps: 4 swaps. Hope this helps :). On Sep 26, 3:11 pm, Asmaa Magdi <[email protected]> wrote: > For the third test case you have originally: (2, 1, 1, 0) > You do the following swaps: > (2, 1, 0, 1) > (1, 2, 0, 1) > (1, 0, 2, 1) > (0, 1, 2, 1) > > > > > > On Sat, Sep 26, 2009 at 8:45 PM, Ken Corbin <[email protected]> wrote: > > > So much for my dreams of honor and glory. Looks like in the bottom third > > of > > contestants who are going to score a big fat zero. Spent too much time > > working out a perfectly good solution to problem A that didn't solve even > > the > > sample input. How in the world can the solve the last test case in 4 > > swaps > > instead of 5? And was still working on problem B when time ran out. > > > It was a well run contest, and I in special awe of the twisted minds that > > make > > up these problems. Will probably be back next year, but right now I'm > > going > > to spend the rest of my weekend trying to solve these things. > > > Thanks Google > > -Ken > > -- > Asmaa Magdi (Also known as ACMaa :P) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
