September 19, 2018 Single Round Match 737 Editorials

Make737Easy

The problem has a straightforward solution: with the constraints being so low, we can afford an O(n^3) solution that simply enumerates and checks all triples of indices.

def count(S):
	answer = 0
	for i in range( len(S) ):
    	for j in range( i+1, len(S) ):
        	for k in range( j+1, len(S) ):
            	if S[i]=='7' and S[j]=='3' and S[k] == '7':
                	answer += 1
	return answer

More efficient solutions exist as well. In fact, the problem is solvable in linear time. The main idea of one such algorithm: For each ‘3’ we can count the number of 737-triples that contain it by multiplying the number of ‘7’s to its left and the number of ‘7’s to its right.

def count_linear(S):
	# compute the following:
	# prefix[i] is the number of '7's in the first i characters of S
	# suffix[i] is the number of '7's in the last i characters of S
	N = len(S)
	prefix, suffix = [0], [0]
	for n in range(N):
prefix.append( prefix[-1] + (1 if S[n]=='7' else 0) )
	for n in range(N-1,-1,-1):
suffix.append( suffix[-1] + (1 if S[n]=='7' else 0) )
	# use the precomputed values to calculate the number of 737-triples
	return sum( prefix[n] * suffix[N-n-1] for n in range(N) if S[n]=='3' )

AliceAndBobMedium

A winning move for Alice is a move that will get Bob into a losing position. And as we know from the problem statement, losing positions are those in which the bitwise xor of all pile sizes is zero.
The pile sizes in the input are quite large, so we cannot afford to enumerate all possible moves Alice can make. In order to solve this task, we need to make one observation: for each pile there is at most one winning move.
Why is that the case? Consider the following example. Suppose the current pile sizes are {7, 5, 3, 4}.
What happens if Alice chooses the pile with 7 stones? By removing some of them, she will create a new state in which the pile sizes are {x, 5, 4, 3} for some x < 7. In order for this to be a winning move, we are looking for a value x such that (x xor 5 xor 4 xor 3) = 0.
Now we can easily see that there is exactly one such x: x = (5 xor 4 xor 3) = 2. In other words, Alice’s winning move is to go from {7, 5, 3, 4} to {2, 5, 3, 4}.
In the same example, suppose Alice chooses the pile with 3 stones. Using the same math as above, we can compute that the desired new pile size is x = (7 xor 5 xor 4) = 6. However, this is not a valid move for Alice: she cannot go from 3 stones to 6, as she can only remove stones.
This observation can easily be generalized. In order to count the winning moves for Alice, we just do the following: For each pile p, compute x = the bitwise xor of all other piles. If x < p, Alice has a winning move on this pile, otherwise she doesn’t.

def count(A):
xorall = 0
for a in A: xorall = xorall ^ a
winning = 0
for a in A:
needed = xorall ^ a
if needed < a: winning += 1
return winning

SimpleMathProblem

There are multiple ways to tackle this problem. I tried to choose one that has a small number of special cases.
Our goal is to compute a^(b^c) modulo m. The two main tools for such jobs are:
https://en.wikipedia.org/wiki/Euler%27s_theorem that can be used if a and m are coprime
https://en.wikipedia.org/wiki/Chinese_remainder_theorem that can be used to split the computation “modulo m” into computations using other smaller moduli.
Our plan of attack will be as follows. We’ll start by finding the prime factorization of m. For each p^k that is a factor of m:
If a is not divisible by p, we can use Euler’s theorem to compute a^(b^c) mod p^k.
If a is divisible by p and b^c >= k, we know that a^(b^c) mod p^k = 0.
If a is divisible by p and b^c < k, we can compute a^(b^c) mod p^k directly.
Finally, we just use the Chinese remainder theorem to merge all partial results into one. In my code, instead of using the actual CRT I use a simple implementation that runs in O(min(modulus1,modulus2)), which is fast enough in our case.

def gcd(a,b):
	if b == 0: return a
	return gcd(b,a%b)
def factor(n):
	answer = []
	d = 2
	while True:
    	if d*d > n: break
    	while n % d == 0:
        	answer.append(d)
        	n //= d
    	d += 1
	if n > 1:
    	answer.append(n)
	return answer
def phi(n):
	answer = n
	for p in set(factor(n)): answer = (answer * (p-1)) // p
	return answer
def modexp(a,b,c):
	if b == 0: return 1 % c
	t = modexp(a,b//2,c)
	answer = t*t*(a if b%2 else 1)
	return answer % c
def crt_combine(a1,m1,a2,m2):
	if m1 < m2: a1, m1, a2, m2 = a2, m2, a1, m1 for k in range(m2): if (a1 + k*m1) % m2 == a2: return a1 + k*m1, m1*m2 def calculate(a,b,c,m): answer, modulo = 0, 1 for p in set(factor(m)): curmod = 1 while m % p == 0: curmod, m = curmod*p, m//p if a%p == 0: if b == 1: newexp = 1 elif b > 1 and c <= 10: newexp = min(50,b**c)
            	else: newexp = 50
            	curans = modexp(a,newexp,curmod)
        	else:
            	newexp = modexp(b,c,phi(curmod))
            	curans = modexp(a,newexp,curmod)
        	answer, modulo = crt_combine(answer,modulo,curans,curmod)
    	return answer

AliceAndBobEasy

The winning strategy for NIM is well-known: a position is losing if and only if the bitwise xor of all pile sizes is zero.
If we are in a losing position, there are no winning moves. If we are in a winning position, a winning move puts our opponent into a losing position. Thus, we want to make the bitwise xor of all piles be equal to zero. In other words, we need to choose one pile and make its size equal to the bitwise xor of all other piles.
Hence, in any given winning position there is at most one winning move on each pile. Note the “at most”. This is because sometimes the size we need is bigger than the size we have, which is not a valid move. For example, in the winning position {7, 5, 3, 4} there is no winning move on the pile with 3 stones because we would need to go to {7, 5, 6, 4} and we are not allowed to add stones.
Thus, for any n we see that a winning position with n piles has at most n distinct winning moves. If we can find such positions, we can be sure that they are optimal.
For odd n such positions are easy to find. For example, consider the position { 2^x + 1, 2^x + 2, …, 2^x + n } for some x such that 2^x > n. We can easily verify that there is a winning move on each pile. This is because the bitwise xor of any n-1 piles will not have the 2^x bit set (as n-1 is even), and therefore it will certainly be smaller than the current number of stones on the remaining one pile.
For even n the best we can do are positions with n-1 winning moves, for example { 1, 2^x + 1, 2^x + 2, …, 2^x + n-1 }. Using the same reasoning as above we can show that there is a winning move on each pile other than the “1” pile. All that remains is to show that we cannot do better.
Suppose n is even and we are in a winning position. As the bitwise xor of pile size is non-zero, let x be the largest exponent of two that appears in said bitwise xor. As the total number of piles is even and the number of piles that have the x-th bit set is odd, there has to be a pile P that doesn’t have the x-th bit set. We now claim that there is no winning move on pile P.
Why is that? Because the bitwise xor of all other piles will match P on all bits bigger than x, and it will have the x-th bit set while P doesn’t. Thus, the bitwise xor of piles other than P is greater than P.

GroupTheNumbers

Here are some observations we can make:
There is an optimal solution with at most one group that has a nonpositive value. (Otherwise we can combine two such groups into one.)
In any optimal solution there is only one group with value > 1. (Same argument.)
Let’s call x big if abs(x) > 1. In any optimal solution, all big elements are in the same group, except for at most one negative big element. (The only other place they can be is the nonpositive group, if any. It is always better to bring all positive big elements, and any pair of negative big elements from the nonpositive group into the big positive group.)
Each “1” should optimally be a separate group. (If we have it anywhere else it’s better to take it out.)
Pairs of “-1”s should never be together in a group with other numbers, each such pair should be a separate group. (Same argument.)
This leaves us with a small finite number of cases, and we can find the optimal solution by examining all of them and picking the best one. (It is possible to make further observations, e.g., which negative number to choose as the one that is not in the “big” group, but it’s not necessary.)
Thus, the outline of my final solution looks as follows:
Write a brute force solution that works for any small constant number of elements. (We will never use it on more than 4 elements. I did it this way because to me it was simpler than the additional casework.)
Merge all 0s into a single 0.
Make each 1 a separate group.
Make each pair of -1s a separate group, as long as you have some -1s left over.
If the product of all big elements is positive, make them into a group.
If you now have no big elements, use brute force.
If the product of all big elements is negative and you have a -1, try making a group of all big elements + the -1, then use brute force.
If the product of all big elements is negative, also try all possibilities of making a group of them that is missing one negative element, and then use brute force.

Make737Hard

We already made a useful observation in the linear solution for Make737Easy: given any string of 7s and 3s, the number of 737-triples can be counted as sum( (7s to my left) times (7s to my right) for each 3 in the string ).
We can now imagine building the desired string in two steps: first we choose the number of 7s in the string, then we choose where to insert the 3s. Once we chose the number of 7s, each gap between them comes with some specific number of 737-triples each 3 inserted into that gap will produce. For example, each 3 inserted at the marked location in 777|77 will produce 3*2 = 6 triples.
This can now be treated as a knapsack problem: we need to choose the right number of “items” so that their sum becomes exactly the given X.
My alternate solution for this problem feels a little like cheating. The number of strings in {3,7}^373 is huge, the number of triples in each of them is always small, and the “item sizes” in the knapsack are reasonably distributed. Thus the set of correct answers should always be large and fairly dense. Hence, all I did was a clever random walk that oscillates around the desired number of triples until it hits exactly.

string make(int X) {
    if (X <= 371) return '7' + string(X, '3') + '7';
    string curr = "";
    while (int(curr.size()) < 373 && eval(curr) < X + 20000)
        curr += ((rand() & 1) ? '7' : '3');
    int currval = eval(curr);
    while (true) {
        string cand = curr;
        cand[rand() % cand.size()] = ((rand() & 1) ? '7' : '3');
        int candval = eval(cand);
        if (candval <= currval && currval < X) continue; if (candval >= currval && currval > X) continue;
        curr = cand;
        currval = candval;
        if (currval == X) return curr;
    }
}