Hello,
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?
Thanks in advace.