Firm

that confused me too

Ahhh...I'm pretty new to all this, so I'm not sure if this is what you're looking for, so...ignore me if I'm missing your question. =D

Consider a four-dealer layout: 3 1 4 2
If you had a greedy that strictly tried to make 1 happy, then 2, then 3, then 4, your program would function like this...
3 1 4 2
Make 1 happy...
1 3 4 2
Wait a day, then make 2 happy...
1 2 4 3
Wait a day, then make 3 and 4 happy...
1 2 3 4
So your program would claim that it would take three days (unless I'm misinterpreting what you mean, which is very possible).

But the real solution does this:
3 1 4 2
Make 1 and 4 happy on the first day (the transactions do not overlap).
1 3 2 4
Make 2 and 3 happy.
1 2 3 4
So the real solution takes only two days.

Still, not sure if greedy works even after taking that into account--I haven't attempted that problem yet.

for 3 1 42 a greedy method should make maximize swaps without over lap.

day1 1-3 and 4-2 => 1 3 2 4
day2 2-3 => 1 2 3 4.

with this logic I tried to check the answer generated byfor all permutations of 1 2 3 4 5 and seems to give correct answer, but the judge gives a WA.

Not sure how the judge checks for 1 of the many solutions that can exist.

Any test-case where this might fail ?

That's my approach too. it also gave me WA. Still, I think the greedy is good.

my friend gave me this counter example.

6 1 2 3 4 5 ... the algorithm dicussed above gives the following 3 steps

3
3 1-6 3-2 5-4
1 2-6
1 4-6

but the correct answer should be

2
2 6-2 3-5
3 2-1 6-3 5-4

Interestingly the number of swaps remains same => the swaps needed to resolve the cycle of length N is still N-1; the only thing that changes is the order of the swaps.

i also found the optimal solution, it gives the "optimal solution" on randomly generated N=5000 inputs and all inputs i try but when i submit it i always get WA
are there multiple test cases on one problem, or is there anything that i can miss or do wrong
my solution always does it with "optimal days"

I always find it funny how people say 'My answer is right, why am I getting WA?'. You are getting WA because your answer is wrong. So no, you haven't found the optimal solution, and your solution doesn't do it with optimal days. And of course we can't help with anything, since you haven't told us the wrong way you have tried to solve the problem.

Anybody can giveme some idea about this problem, general method or somethink.

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.

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

Hello,

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

I am getting [color=red]runtime error (other)[/color] in this one.
Any idea of what does 'other' mean?

Y.

In most cases this means "memory limit exceeded".

Thanks Turbo, got AC now