Well, I tried them out, too ;)

Not everything needs to be aimed at you.

First refer to the editorial, but note that the DP sets could be exponential in size if stored explicitly. It doesn't give much details as to how to solve this subproblem except for a mention of "maintaining the basis".

It refers to the concept in linear algebra. In other words, we want to somehow maintain a small-enough subset $$$B \subseteq DP_i$$$ such that we can easily check that $$$x \in DP_i$$$ by xor-summing a subset of $$$B$$$.

This is possible, because if $$$a \in DP_i$$$ and $$$b \in DP_i$$$, then $$$a \oplus b \in DP_i$$$.

What if we stored $$$B$$$ as an array of $$$60 = \lfloor \log_2 \max A_i \rfloor + 1$$$ integers with the following rule:

• If there exists a number in $$$DP_i$$$ such that its $$$j$$$-th least significant bit is $$$1$$$ and all bits lower than the $$$j$$$-th are $$$0$$$, $$$B[j]$$$ should be set to one of those numbers, otherwise $$$B[j] = 0$$$.

Then we can easily check for membership in $$$DP_i$$$ by the following algorithm:

• If $$$x = 0$$$, $$$x \in DP_i$$$. (cause $$$0$$$ is always in $$$DP_i$$$ as long as we're "alive")
• Otherwise let $$$j$$$ be the index of $$$x$$$'s least-significant $$$1$$$-bit.
• If $$$B[j] = 0$$$, $$$x \notin DP_i$$$, because we cannot flip the $$$j$$$-th bit without affecting lower bits.
• Otherwise $$$x \in DP_i \iff x \oplus B[j] \in DP_i$$$, so do $$$x := x \oplus B[j]$$$. The algorithm is guaranteed to terminate because the new $$$x$$$ is either $$$0$$$ or has a greater number of trailing zeros.

Now the final step is to figure out what to do if $$$x \notin DP_i$$$. If $$$S_i = 1$$$, we report a player $$$1$$$ win. Otherwise we want to expand the set for $$$DP_{i-1}$$$; it suffices simply to set $$$B[j]$$$ to the final value of $$$x$$$.

There's a good tutorial on xor basis in https://mirror.codeforces.com/blog/entry/68953 and https://mirror.codeforces.com/blog/entry/60003.

tldr store stuff in row echelon form

It fails on this case

3

2 5 7

010

Answer is 0 only if somehow player 0 can construct every number player 1 can construct.

It is enough if player 0 can construct every number player 1 has after player 1 plays it.

So for every number belonging to player 1 (say $$$x$$$), find basis of all numbers by player 0 occurring after this position and check if $$$x$$$ belongs to the span of this basis

If you iterate in reverse, you can maintain the basis of numbers of player 0 and check this in $$$\mathcal{O}(N\log A)$$$ total.

I referred this blog for basis calculation

If the last number belongs to player 1, he wins regardless. You need to build the list iteratively starting from the end.

I have no idea how to even do the naive binary search solution :(

I think conceptually my solution is even simpler. The basic idea is to find a good lowerbound. Two obvious lower bounds are the maximum subarray sum (when we consider zeros and question marks as $$$-1$$$) and the absolute value of the minimum subarray sum (when we consider zeros as $$$-1$$$ and question marks as $$$+1$$$). It turns out that the highest of these lower bounds is nearly always attainable, except in the case when there are two places with different parity that provide the same lower bound (it is easy to see that this lower bound is not attainable in this case); in that case our answer will be exactly one higher.

So the final solution is just to run Kadane's algorithm twice, keep track of the lower bounds for each parity, and return the answer as described above (with a single if).

During the contest, my proof of the claim above was a bit shaky, so I also wrote a quick stress test to verify it, but the 'real code' is pretty short (only the solve method).

How did you taste the problems if you had idea of none?

Why not to tourist?

I don't know about "as easy" (I don't understand your solution tbh), but yes, this problem is solvable.

//	finds min k s.t. L <= (k * A) % M <= R (or -1 if it does not exist
ll solve4(ll A, ll M, ll L, ll R) {
	if (L == 0) return 0;
	A %= M;
	ll ans = 0;
	ll s1 = 1, s2 = 0;
	while(A > 0) {
		if (2 * A > M) {
			A = M - A;
			L = M - L;
			R = M - R;
			swap(L, R);
			ans += s2;
			s1 -= s2;
			s2 *= -1;
		}
		ll ff = (L + A - 1) / A;
		if (A * ff <= R) return ans + ff * s1;
		ans += (ff - 1) * s1;
		ff = (ff - 1) * A;
		L -= ff;
		R -= ff;
		ll z = (M + A - 1) / A;
		s2 = s1 * z - s2;
		swap(s1, s2);
		M = z * A - M;
		swap(A, M);
	}
	return -1;
}

It is not exactly what you wanted, but we can continue the search (with smaller right bound) after we have found minimal $$$k$$$.