Think about addition in base two. Say a=10101 and b=1001. What your operation does is it modifies the bits in your numbers, so if the first bit in a is 1 and the first bit in b is 1 (as is the case above) you can make both 0 by making that bit 1 in x. This is actually the only way you can decrease the resulting sum, so x=1 is an answer above.

Noticing the hint above we now deduce x = a & b where & is bitwise and. So just printing (a^(a&b)) + (b^(a&b)) works, but there's an even nicer formula. We'll leave it up to you to prove that (a^(a&b)) + (b^(a&b)) = a ^ b :)

It's hard to use the two valuable switches somewhere in the middle of the matrix, a much wiser choice would be to somehow block the S cell or the F cell. Perhaps you can set both neighbours of S to 1 to force Roger to pick 1.

If we pick the neighbours of S to be 1 we can make the neighbours of F 0 and there would be no way to go from S to F. But this in the worst case takes 4 switches, to get down to 2 switches we can consider the other way around, making the S neighbours 0 and F neighbours 1. There must be a solution of the two with at most two switches and you won't get from S to F since you're forced to pick 1 (or 0) and can't get past the neighbours of F which are opposite.

You're not allowed to just pick the whole string and append its reversed result to the front, but what's the next best thing? We're very close to the answer if we take the whole string except for a letter (so for abcde we make dcbabcde).

The operation above which transformed abcde into dcbabcde is very close, if only we could've appended e to the left somehow. Turns out you can set that up, so from abcde first append d to the end, then you have abcded. Now apply the operation from the hint on this string and get edcbabcded. See why we added that d first? We can now append it to the front just like we wanted!. Do the operation L 2 and the job is finished. Yep, amazingly just printing

R n-1

L n

L 2

works!

Using too many edges in the solution feels wasteful, the solution surely has some neat line as straight as possible. Perhaps we can prove only two edges are required?

Indeed two edges are required in the solution, so one approach would be picking all combinations of edges and do linear algebra so see how many times each is required (or if it's impossible).

To prove that let's suppose our target is somewhere reachable by only taking C1 and C2 (the upper right sextant, a sixth division of the plane). C4 and C5 will never be used since they contribute in the wrong direction. We can now use C6, C1, C2 or C3 for our solution. If using C1 and C2 is not optimal we can choose C3 or C6, without loss of generality we choose C3. C6 cannot be used because it simply counters C3. Now we either use C1, C2 or C3, but we can further narrow down to just two edges. If we use all three this means we use C1+C3 which goes the same way as C2, and C2 also goes the same way as C1+C3. So we can just not use C2 if C1+C3 < C2, or use C2 instead of C1+C3 until either of C1 or C3 doesn't appear anymore on our solution.

The problem gives us an array and we have to come up with an achievable sequence of pluses and minuses such that summing the numbers after applying the signs we get the largest sum. Intuitively we can probably assign + to most positive numbers and — to most negative numbers somehow, but we should investigate exactly which are possible.

Before you try to find patterns you should observe that there is one case that is impossible to reach. You cannot assign alternating + and — to the array, like +-+-+-+- or -+-+-+-+. The reason is very simple, the very first thing you do is apply the operation on two consecutive numbers and make them both --, and whenever you apply further operations on the both of them they remain the same sign. In the end we decided to give this in the samples but we know from testing many would miss this case.

n = the length of the array.

m = the number of elements we multiply by -1 in the solution (put — in front of them).

p = the number of elements we do not multiply by -1 in the solution (put + in front of them).

The mysterious pattern is as follows: (n+m)%3 == 1

So yes, for n=7 for example we can put 3 minus signs anywhere, like ++--+-+, or 6 minus signs like --+---- or full plus signs +++++++. We can arrange the pluses and minuses however we want as long as there are 2 consecutive equal signs and (n+m)%3 == 1.

The solution now simply requires us to sort the array and multiply by -1 each number one by one and when (n+m)%3 == 1 update the answer with the current sum. Of course there is one point where all the elements might form the forbidden +-+-+- so you should check that in that case they do not, or if they do pick the next smallest number to turn into — instead of the last one. So for the sample [4, -5, 9, -2, 1] you sort and get [-5, -2, 1, 4, 9] and when you turn -5 into 5 instead of turning -2 into 2 you turn 1 into -1 and the array will be [5, -2, -1, 4, 9]. After that undo your modification, turn -2 into 2 and revert -1 to 1.