This can be divided into several "cycles" i.e. smallest groups of numbers that can be rearranged among themselves to produce the correct permutation. The cycles are:
Obviously, cycles of length 1 are already solved and cycles of length 2 can be solved just by swapping the two numbers. But what would you do for the cycle of length 3 or 4? Or how about 6, like the example given by whiz? If all the numbers form a single cycle, then by the problem's constraints you might have to deal with a cycle as long as 5000.
Try solving by hand cycles of small lengths, and then you might think of a solution that works for any length.
I tried a bit of a crazy idea on this problem, it seemed to work on every "small" test case that I built. The concept was to first identify cycles. Once you have them the way of ordering each cycle is as follows: - Take the bigest and smallest value that haven't been swaped yet. - Swap them. - Reapet until the bigest and smallest values are the same. After this, one day has passed, and the array is not necesarely ordered yet, so we reapet everything including the cycle identification until all cycles are of length 1.
Here is my output for problem's example:
input: 7 2 1 3 5 6 7 4
output: 3 2-1 7-4 6-5 1 6-4
It's not the same as the sample output but it is such as valid.
Here is my output for whiz's example:
input: 6 6 1 2 3 4 5
output: 3 6-1 5-2 4-3 2 6-2 5-3
But, I am getting a nice WA. Dos anyone know what could be wrong?
TripleM is right. If the output is WA, you give the wrong answer. I won't tell the solution here, but just a hint: The number of days needed is bounded by a surprisingly low constant, not depending on cycle length, whereas the naive implementation, I also tried first, scales with O(log len). Any algorithm that is worse than O(1) days is correctly rejected as WA.
Examining the example with the 6-cycle that is solved in 2 instead of 3 days (given in this forum) pushed me to the right track. buldae_bien_'s algorithm happens to hit the optimal implementation under certain circumstances, for example in whiz's example, but does not do so in other cases, where a heuristic assumption included in it fails.
PS: I won't give any further hints to this problem. I go back squeezing more digits of SQRT(2).
Thanks twice11, you were very right. I have found the constant that is an upper bound for this problem, regardless of the cycle length. What I don't seem to find is an algorithm that can fit to this constant for every test case. My latest non-implemented idea was to just swap with backtracking every posible swap combination until we only have length 2 cycles, but this would sure give TLE. I'm a bit frustraded with this problem. :S
I think with your 'lucky' previous idea you should be able to get to a correct algorithm. Hint: you can relabel a cycle of length n to 'n 1 2 .. (n-1)'. The relabelling is easy enough, so all you need to do is work out how to solve that particular instance..
TripleM thanks for the hint, but I don't think that my first lucky guess can produce a correct algorithm. For example take this test case:
8 5 4 6 3 7 1 8 2
Even cuting the calculations with the constant upper bound, my original algorithm of swaping the biggest and smallest value would lead this test case to either run forever or write an incorrect answer.
How you can see this test case is one single 8-length cycle, I don't know if I understood correctly your hint, but this test case doesn't seem like it can be relabelled to n 1 2 ... (n-1).
The only set of optimal swaps that I found for this test case are as follows:
2 4 2-5 1-4 3-6 7-8 3 1-2 4-6 5-8
And I can't find any relation or pattern of choice that could induce to a correct algorithm.
I didn't 'expect the answer to my face', whatever that means, I was just pointing out that we cannot possibly help you when you say 'I'm right but I'm getting WA'. What did you expect us to say? That you've got an error on line 32?
Yes you are right, i just asked if there is a tricky part on this problem My method is find cycles and put them on an array and to the middle of the array swap the begining and the end
Seems like you didn't understand something. If you change 4-7, you change numbers 4 and 7, not numbers on positions 4 and 7. For example, after 4-7 you suppose that it's 2 1 3 4 6 7 5 but it's really 2 1 3 5 6 4 7
Nie cierpię pisać takich postów, ale niestety mało prawdopodobne jest, że otrzymasz tutaj pomoc dotyczącą rzadko używanych języków. Użytkownicy polskiego SPOJa rzadko używają tych mało popularnych języków, a nawet jeśli, to raczej nie wchodzą na to forum. Tak więc radziłbym Ci napisać na spoj.pl/forum, gdzie dział "Języki programowania" jest nawet podzielony na poddziały, więc osoby przeglądające dany dział znają się mniej lub więcej na danym języku i jest większe prawdopodobieństwo, że Ci odpowiedzą.
No i może pomoże Ci jeszcze przykładowy kod na ideone.com (ideone działa mniej więcej tak, jak SPOJ): http://ideone.com/samples#sample_lang_131 Jeśli nie, to na ideone jest też pozycja "Ostatnie kody", w których użytkownicy zgłaszali programy. "Wystarczy" więc znaleźć taki, który nie dostał SIGSEGV.