*u*, or

*v*, or on

*u*+

*v*(where

*u*and

*v*are the nested loop variables that yield quadratic running time).

*n*). It constructed a suffix array instead of using the z-function though, so I guess the lesson learned here is that for practical purposes the O(

*n*) suffix array construction should be treated as O(

*n*log

*n*), as I assume the constraints were so high (n=10

^{7}) precisely to cut off O(

*n*log

*n*) solutions. In the end I was able to replace the suffix arrays usage with z-function.

^{5}. In one operation, you can take any segment of this array of even length, and swap the 1st and 2nd numbers in that segment, the 3rd and 4th numbers, and so on. You need to sort the array in at most 10

^{6}operations. You do not need to minimize the number of operations. Can you see a way?

*A*, each up to 10

_{i}^{9}. Your goal is to split each

*A*into two non-negative integer parts

_{i}*A*=

_{i}*B*+

_{i}*C*so that there is no way to choose exactly one of

_{i}*B*or

_{i}*C*for each

_{i}*i*such that the sum of chosen numbers is equal to exactly half of the sum of all

*A*(that sum is guaranteed to be even).

_{i}When solving this problem, the first observation I made is that it is in fact hard, likely impossible, to check in a reasonable time if a given split into *B _{i}* or

*C*satisfies the requirements or not, as it requires solving a pretty large instance of the knapsack problem. This may be the reason that the problem does not require to print a certificate, just a Yes/No answer.

_{i}This naturally leads to the following question: for which splits into *B _{i}* or

*C*we can reasonably easily prove that achieving exactly half is impossible? To make such proof easier, it makes sense to split all even numbers exactly in half such that

_{i}*B*=

_{i}*C*: then we know for sure those numbers' contribution to the sum, and there are fewer possibilities to check. However, if all numbers are even and we do this for all numbers, then it would be possible to achieve exactly half of the total sum (in fact, it would be impossible to achieve anything else :)). But then we can do this even split for all numbers except one, and for one number (say,

_{i}*A*

_{1}) we set

*B*

_{1}=0 and

*C*

_{1}=

*A*

_{1}. Then we get exactly half from all other numbers, but if we choose

*B*

_{1}then the sum is slightly less than exactly half of the total, and if we choose

*C*

_{1}it is greater. Therefore we have solved the problem for the case where all

*A*

_{i}are even (the answer is always Yes).

What can we do about odd numbers? They cannot be split exactly in half, but we can try to build on the above construction: let us split all odd numbers almost in half, such that *B _{i}*+1=

*C*, and split one number, the biggest one (assume we reorder the numbers and it is

_{i}*A*

_{1}), as

*B*

_{1}=0 and

*C*

_{1}=

*A*

_{1}. Now if the amount of odd numbers is less than

*A*

_{1}, then we still cannot achieve exactly half, because if we choose

*B*

_{1}, even taking

*C*from all odd numbers will still leave us short of half of the total, and if we choose

_{i}*C*

_{1}, we overshoot. There is a slight complication that happens when

*A*

_{1}is odd, as then we should not count it towards the amount of odd numbers we split almost in half; however, since the total amount of odd numbers is always even (because the sum is even), this does not affect our comparison and we can still compare if

*A*

_{1}is strictly greater than the total amount of odd numbers.

This criterion was my first submission, however, it got WA. As I did not have any immediate ideas for other situations where achieving exactly half is clearly impossible, I implemented a brute force solution and stress-tested it against this one. The smallest counterexample it produced was: 1, 3, 3, 3. In this case we set all *B*_{i}=0 and *C*_{i}=*A*_{i} and there is no way to achieve the required sum of 5 from some subset of 1, 3, 3, 3. The first idea after seeing this was that divisbility by 3 is somehow a factor; however, quite quickly I realized that we can slightly generalize the construction from the first submission above: we take all odd numbers, sort them, and split them into two parts of odd size. In the part containing the smaller numbers, we set *B _{i}*+1=

*C*, and in the part containing the bigger numbers, we set

_{i}*B*+

_{i}*D*=

*C*, where

_{i}*D*is the smallest of those bigger numbers. Now if the size of the part with smaller numbers is less than

*D*, then we always fall short of half of the total if we choose more

*B*'s than

_{i}*C*'s in the part with the bigger odd numbers, and we always overshoot otherwise.

_{i}This solution passed the stress-test against the brute force for small constraints, therefore I submitted it and it got accepted. I did not bother proving it formally since the stress-test was proof enough, but the intuition is somewhat clear: now we say No only if there are at least two odd numbers up to 1, at least four odd numbers up to 3, at least six odd numbers up to 5, and so on until we run out of odd numbers, and the total amount of odd numbers is at least the biggest number. I did not write down all details, but the following method likely works to achieve exactly half in this case: we first go through all even numbers, and then through all odd numbers in decreasing order. If the sum we accumulated so far is bigger than half of total of the numbers processed so far, we take the smaller one of *B _{i}* and

*C*, otherwise the bigger one. We can now prove by induction that after processing all odd numbers except the

_{i}*x*smallest ones, the current sum differs from half of all processed numbers by at most (

*x*+1)/2, which means that in the end it is exactly equal.

Thanks for reading, and check back next week!

In problem H, n = 3e5 (not 1e5).

ReplyDeleteThanks! Fixed.

Delete