# September long challenge CHEFNSWAP

here is the link to my solution:
https://www.codechef.com/viewsolution/37549925

need help to find where am I wrong,

My logic is:
if n<3 no swap possible
next we know that it is possible only when n is of form 4k+3 of 4k
in that case i calculated “i” such that the sum 1+2+3+…+i is just greater than half of sum 1+2+3…+n (which is k)
and if sum of first i terms is equal to last n-i terms we may do any swap(between first i numbers or between least n-i numbers so for that cases will be iC2* (n-i)C2 (however later i realised that it is possible only when n=3),
and if sums aren’t equal it can do (n-i) swap.

Thanks

possible only for 3? did you proved or guessed? It`s possible for n=20 also.

1 Like

i thought it would be for 3 only but for safer side I took it for all cases, please check line15.

as far as I can see, you are iterating through all the values from end to start. I don’t know where the error is but this will result in TLE. you have to optimize it.

1 Like

it would barely go to midway , that is n/2 because the condition given in while loop(line 12) would be valid till then only(in higher values of n). (though I am just a beginner and wasn’t able to optimize the code, you may give suggestions)

can’t find where am I wrong.

1 Like

yup, still, it would result in TLE as O(N/4) or even O(N/6) would be equal to O(N).

My approach is quite similar to yours you can check
https://www.codechef.com/viewsolution/37608823

I used quadratic to find the number for which swap can be done, then travelled in reverse order so as to find the first number for which swap can be done.

thanks @anon40522502 for your solution, and @blank_kami to point out TLE problem(although it went above my head, no knowledge of time complexities), but still I need help tp find where my logic was wrong.

Compiler said WA again and again and I spent the ten days working on same problem and even after that not able to find mistake.

1 Like