For the first problem

For the next problem, I guess you want proof for delaying as much as possible.

Neither of them require much number theory, their observations come from elsewhere. However if you find number theory unintuitive, it could be bottleneck. You can read this.

The other problem is less number theory, and more focused on what the constraints is.

It is hard to think of globally optimal solution. But its easy to prove that certain decision locally. Let $$$C$$$ be the set of elements in cache currently. Assume $$$|C| = c$$$ and we have to add new element $$$x$$$ s.t. $$$x \notin C$$$.

We only need to think of which is the optimal element to remove. Let us assume we remove some element $$$a \in C$$$, and that $$$a$$$ appears before some other element $$$b \in C$$$ that we didn't remove. Let us show that we can make the solution not worse by removing $$$b$$$ instead. By swapping $$$a$$$ and $$$b$$$, we can have the rest of the cache behave the same until we reach $$$a$$$. Instead of removing something and adding $$$a$$$, we already have $$$a$$$. Since not having an element can only worsen the solution by at most one cache read (because we can just add it now which would make it same as optimal), the solution doesn't worsen.

Therefore removing the one that appears the latest is optimal.

The most important thing to notice is that only the set of best cards at each step matters. For step 1 its just the cards that $$$A$$$ has. The next most important thing to notice is that, for a team, the best card order is high card from team, low card from team, low card from opponent, high card from opponent. This order is justifiable, as replacing any card with a better card will not worsen the team's answer, You can prove this by simply playing the same cards as the worse case.

For when you can improve a single card and always do better, it means that for a set, if the $$$k$$$ th best in set $$$1$$$ is at least as good than the $$$k$$$ th best in set 2, set 1 is at least as good as set 2 from construction of previous claim.

Now you simply need to prove you can find solution that is "best", i.e. previous condition holds for all other sets. I think its a relatively easy exchange argument.

Note that the gcd of an array equals the gcd of its prefix sum. Thus, the problem is equivalent to selecting some prefix sums of the original array ($$$a$$$) and maximizing their gcd. Note that you must select the entire sum, i.e. $$$a_1+\cdots+a_n$$$, which we call $$$S$$$. The answer is the biggest factor of $$$S$$$ which also divides another prefix sum, thus it is $$$\max\gcd(S,a_1+\cdots+a_i)$$$ for $$$1\le i\le n-1$$$.

I don't see why this problem needs polynomial interpolation, its sufficiently simple to find the polynomial directly by looking at each index $$$i$$$, then counting the number of indices to left that are less than $$$a[i]$$$ and number of indices to right greater than $$$a[i]$$$. Its easy enough to calculate for fixed $$$a[i]$$$, and then its sum of this polynomial from $$$1$$$ to $$$k$$$. Just use Faulhauber's Formula which also proves that this sum is polynomial. The stupidest brute force way to write it is $$$O(n^5)$$$ so its fast enough.

First notice that doing the operation is commutative, and also that doing it twice undo's the previous operation. So the only thing that matters is the set of chosen rows and columns. Also notice that doing it on all rows and all columns is like doing nothing. Create variables $$$r_i$$$, whether you do operation on row $$$i$$$, and similarly define $$$c_j$$$.

So you have constraints like $$$a_{i,j} \bigoplus r_i \bigoplus c_j = b_{i, j}$$$. This tells you that $$$r_i \bigoplus c_j = a_{i, j} \bigoplus b_{i, j}$$$. These form relations in a graph of $$$r_i$$$ and $$$c_j$$$, with $$$n + m$$$ nodes, and you can easily check if there exists solution that satisifies it, since knowing one element in each component defines the rest uniquely.

All odd $$$n$$$ work, and they are the only $$$n$$$ that work. For a proof of sufficiency, take the smallest power of $$$2$$$ greater than $$$n$$$, say $$$2^k$$$. Then $$$(x, y) = (2^k - 1, 2^k + 1)$$$ works. For necessity, note that you can build $$$x$$$ bit by bit from $$$x \oplus nx$$$ if $$$n$$$ is even.

Yes, it's completely valid proof, because there no arbitrary decision or wishfulness.

This the level of confidence you should have while reasoning on all problems.

If you are downvoting then you must be expert in proving these kind of problems. Please share your knowledge.

Why is T = [0, 1, 2]?

Assume you already found the lower bound of size of a subsequence to have xor $$$x$$$ (which is $$$2$$$ except a subsequence with $$$x$$$ itself), let try to prove you can achieve this lower bound. (or upper bound on $$$k$$$)

First, you must have at least one element have $$$x$$$'s highest bit equal to $$$1$$$, let call it $$$a$$$. if you want to achieve lower bound, you must take another element $$$b$$$ s.t. $$$b = a \text{ xor } x$$$, you can notice that this kind of pairing is one to one, so different $$$a$$$ will match to different $$$b$$$, and consider comparing $$$a$$$ and $$$b$$$ from highest bit, they will have same bits until $$$x$$$'s highest bit, where $$$a$$$ have $$$1$$$ and $$$b$$$ have $$$0$$$ at that bit, so $$$a$$$ always greater than $$$b$$$, and for every $$$a \le n$$$, you can find some $$$b$$$ s.t. $$$b < a \le n$$$, so you can make #$$$[1 \le i \le n, i \text{ have x's highest bit equal to 1}]$$$ different subsequence with xor equal to $$$x$$$, which is the upper bound of $$$k$$$.

I solved this in contest :)

Consider turn $$$1$$$. A person could only know he is a part of a triple, if he does not see any triple within the other $$$n - 1$$$ people. If there was, then he could have a number that may not form a triple. If there wasn't, then that means the only remaining triples contain himself.

If they went past turn $$$1$$$, it means only that for every subset of $$$n - 1$$$ people, there is some triple with zero xor.

Consider turn $$$2$$$. Every person now knows, that within every set of $$$n - 1$$$ people, there is some triple with zero xor. Then if there exists $$$n - 2$$$ people without any such triple from the view of person $$$x$$$, then $$$x$$$ knows that if he adds himself to the $$$n - 2$$$ people, there is now a triple, and therefore it must contain him. Otherwise it's still possible for $$$x$$$ to have a value that's in no triple, and any set of $$$n - 1$$$ people that contain $$$x$$$, contain $$$n - 2$$$ people without him, and those $$$n - 2$$$ we saw had some triple with xor zero. Since it applies to all $$$x$$$, every subset of $$$n - 2$$$ elements must have some triple, and therefore its the condition for no one raising their hands on turn 2.

I'm sure its not very difficult to extend this reasoning to an arbitrary number of turns.