*n*(

*n*<=200000) with characters +, - and ?, and two numbers

*a*and

*b*. You can replace each ? character with either + or -. Then you need to find a

*balanced*substring of the string, which means a substring of length

*a*+

*b*that has exactly

*a*+ characters and

*b*- characters, in any order, and remove it from the string (the parts before and after the substring being removed become adjacent to each other). Then you need to find a balanced substring in the remaining string, and remove it from the string, and so on. You goal is to replace the ? characters in such a way that the number of times you can remove a balanced substring is maximum possible (this number of times will never exceed

*n*/(

*a*+

*b*) since we would run out of characters). How to find this maximum number of times?

*n*. You start with a sequence of numbers 1, 2, 3, ...,

*n*. In one step, you can take any two numbers

*x*and

*y*, and replace them with

*x*+

*y*and |

*x*-

*y*|. Your goal is to make all numbers equal, and you also need to make those equal final numbers as small as possible, and you need to do all this in at most 20

*n*steps.

I was not sure how to even approach this problem, so I started by implementing a brute force solution that found me the answers for all values of *n* up to 15. The brute force returns that for *n*=3,4 we can make all numbers equal to 4, for *n*=5,6,7,8 we can make all numbers equal to 8, and for *n*=9,10,11,12,13,14,15 we can make all numbers equal to 16. This naturally suggests that we need to target the smallest power of two that is at least *n*. I did not prove this fact during the contest, but there exists a very simple proof.

Apart from this observation, looking at the way the brute force achieved the goal helped me learn a couple of tricks that are useful for the solution. First of all, when we have a 0, then we can double any number: (0,*x*)->(*x*,*x*)->(0,2*x*). Second, the solution often makes many smaller powers of two, and then makes them all equal using this trick.

^{k}is the smallest power of two bigger than

*n*(we assume

*n*is not a power of two, as for that case we can just use the solution for

*n*-1 without touching the number

*n*at all). We can apply the operation to

*n*and 2

^{k}-

*n*,

*n*-1 and 2

^{k}-(

*n*-1), and so on, 2

^{k-1}+1 and 2

^{k-1}-1. This way, we will get many copies of 2

^{k }as sums, and from the differences we will get numbers 2

*n*-2

^{k}, 2

*n*-2

^{k}-2, ..., 6, 4, 2. And we also have the remaining numbers which we did not touch, those are 2

^{k-1}and 1, 2, ..., 2

^{k}-

*n*-1. 2

^{k }and 2

^{k-1}are already powers of two so we don't need to do anything. And for the two chains 1, 2, ..., 2

^{k}-

*n*-1 and 2, 4, 6, ..., 2

*n*-2

^{k}-2, 2

*n*-2

^{k}we can just apply the same algorithm recursively: directly for the first chain, and doing a recursive call for 1, 2, 3, ...,

*n*-2

^{k-1}and multiplying all results by two for the second chain.

This way we will convert all numbers into powers of two not exceeding 2^{k}. It turns out that for *n*>=3 at least two of those powers will be equal and less than 2^{k}, which allows us to use the (*x*,*x*)->(0,2*x*) step to get a zero, and then use this zero to keep multiplying all numbers by two until we have only one zero and many 2^{k}, and finally use the (0,*x*)->(*x*,*x*) step to get rid of the zero.

Thanks for reading, and check back next week!

## No comments:

## Post a Comment