September long challenge CHEFNSWAP

#1

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

#2

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

1 Like
#3

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

#4

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
#5

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)

Beside the compiler displayed wrong answer instead of TLE.
can’t find where am I wrong.

1 Like
#6

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

#7

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

#8

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.

#9

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

1 Like