You yourself cheat in CodeChef contests and also help others.

Who are you calling cheater?

Getting DQ'd for cheating is worse than FST? Well I mean... first, I'd argue that it's super easy to avoid getting DQ'd; just don't copy others' code. Second, the punishment for cheating should indeed be much much more strict than for being wrong but giving it an honest try, otherwise it doesn't sufficiently discourage cheating.

Every odd number or 0 had a solution. I solved it as if we are creating from all zeros to first k 1's because it was a xor operation hence order doesn't matter. let's say ith bit is high in k and i+1 th bit is low. You can turn on 2^i places on by turning on 2^(i+1) places on and then turning off last 2^i places off.

Proof that only odd numbers are possible -

There are two possibilities — Either don't apply any operation (if k==0) or apply few operations If we are applying few operation, 1st operation will always be used. So there will be 1 high bit after first operation. Now later operations can never change the parity of number of high bits. If you are turning odd number of places on then you will be turning odd number of places off too or if you are turning even number of places on then you will be turning even number of places off.

Well, it was a constructive algorithm. So it can be hard to get to the constructive part.

Claim 1:

If $$$k$$$ is an even number other than 0, then the answer is always $$$\text{NO}$$$.

Proof: Lets consider a sequence of operations of $$$1,2,4,8,...,2^x$$$. Then we are gonna flip $$$2^{x+1}-1$$$ elements. Since there is an even number of $$$1$$$ and $$$2^{x+1}-1$$$ is odd, then an odd number of $$$1$$$ must remain.

Construction for any odd $$$k$$$:

First, find the smallest $$$2^x$$$ such that $$$1+2+...+2^x$$$(lets call such sum $$$S$$$) is bigger than or equal to $$$k$$$. Notice if we changed any element from that sum from positive to negative(lets call the element $$$a$$$), then it will contribute to a difference of $$$2a$$$. For example, if $$$a=16$$$, and we made it $$$a=-16$$$, this will make $$$S-k$$$ to decrease by 32. This gives us an insight to get $$$C$$$ such that $$$C=\frac{S-k}{2}$$$. We can then know when we need to remove $$$a$$$ ones or add $$$a$$$ ones by seeing binary representation of $$$C$$$. So we have constructed a sequence such that is made up of:

$$$1(x)2(x)4(x)8(x)...2^x$$$

where $$$x$$$ is either $$$+$$$ or $$$-$$$.

Applying construction to the problem:

This is by far, the hardest part with a lot of corner cases due to such cases like $$$K=N$$$ or close to it (at least for my construction). Notice that, if we have something like($$$N=K=9$$$) $$$1+2-4-8$$$, we can remove 1+2 one and then flip it with 4 to make it like such and finally remove 8. For example:

$$$111111111$$$

will become:

$$$111111101$$$

$$$111110001$$$

$$$111111110$$$

$$$000000000$$$

This works as you first do $$$-1-2$$$ first then flip it with the $$$4$$$ to make it $$$4-(1+2)$$$ Now, you can do that with any sequence of — and +. If you have some + operations then -, you flip at the — operation. If you have — operation without any + operations before it, you simply remove the last few 1's. The only cornercase is when $$$K=2^x-1$$$, as the last operation will be + so you won't be able to flip. You can handle this case alone.

I had a completely different approach, by making observations from the brute force solution.

Even doesn't work due to parity. For the odd case, it turns out that the direct observation that can be made is by thinking it backward since the operations are invertible, considering an initial array of $$$k$$$ zeroes, iteratively picking the maximum sized island of zeroes, and making the operation such that it fills the highest power of $$$2$$$ number of ones at the end in this island while performing this operation at most one new island of zeroes will be created due to size of the flip, we can just push them into the priority queue.

For k = 9
flip size: 8 [{0, 0, 0, 0, 0, 0, 0, 0, 0}]
flip size: 4 [{0, 1, 1, 1, 1, 1, 1, 1, 1}]
flip size: 2 [{1, 0, 0, 0, 1, 1, 1, 1, 1}]
flip size: 1 [{1, 0, 1, 1, 1, 1, 1, 1, 1}]
             [{1, 1, 1, 1, 1, 1, 1, 1, 1}]

Same here :D

Why was the time duration decided to be 2 days? It was pretty obvious this would entice cheating.

The increase of problem D submissions near the end of the contest isn't completely unbelievable. There are at least a few legitimate explanations that don't involve cheating:

• A lazy person could have foolishly assumed that solving 3 problems was just enough to advance to the next round. Then this person kept slacking off, until he/she realized that this won't work. And finally scrambled to attempt to actually solve the 4th problem in the remaining few hours.

• Busy people may just have no free time to participate seriously until the weekend. So they wake up on Saturday morning and give problem D a try for the first time. Some of them succeed. Coincidentally there's just half a day left until the contest is over, so the timing of their submissions looks suspicious.