# Mexican TST Editorial

## Xor Tree

### Subtask 1

Just code the brute force

### Subtask 2

Let $p[v]$ be the xor-sum of all the edges on the path from vertex $v$ to the root of the tree.

If $u$ is an ancestor of $v$, the weight of the path $u \leftrightarrow v$ is $p[u] \oplus p[v]$.

Generally, if $u$ and $v$ do not have an ancestor-descendant relationship, then the weight of the path $u \leftrightarrow v$ is $(p[u] \oplus p[lca(u,v)]) \oplus (p[v] \oplus p[lca(u,v)]) = p[u] \oplus p[v]$.

That is, for any path $u \leftrightarrow v$, the weight is $p[u]\oplus p[v]$.

Now, given the array $p$, our job is to find $\sum\limits_{1\leq u<v\leq n} p[u] \oplus p[v]$.

In this subtask, $p[u]$ is $0$ or $1$. So our answer is just $(\text{number of 0s}) \times (\text{number of 1s})$

### Subtask 3

In this subtask you don't need the LCA observation, since the tree is a line, just take the prefix xor and do the same thing. However, we need to deal with the larger values.

A common trick to tackle such that bitwise summations is to consider each bit position seperately, cause different bit positions do not affect each other.

As a concrete example, $abc_2 \oplus def_2 = (a00_2 \oplus d00_2) + (b0_2 \oplus e0_2) + (c_2 \oplus f_2)$.

If we consider only the least significant bit, we will ask our self this: If $p$ had only $0$ and $1$ as elements, what is $\sum\limits_{1\leq u<v\leq n} p[u] \oplus p[v]$? It is $(\text{number of 0s}) \times (\text{number of 1s})$. So you just use this formula for each bit position.

### Subtask 4

For the full solution, you combine the above two subtasks.

## JP's Students

### Subtask 1

Brute force search

### Subtask 2

Notice that the parity of the value depends on the parity of the position. If $\frac{N}{2}$ is odd, then $a_i$ and $a_{i+\frac{N}{2}}$ have different parities and is definitely not possible.

### Subtask 3

The sequence looks something like `0 1 2 3 4 3 2 1`, and then we can binary search for the maximum point.

### Subtask 4

Since we are looking at two opposite points which are the same, we can consider $b_i = a_i - a_{i+\frac{N}{2}}$, and analyze what to do with $b$.

Anyways, notice $b_0 = -b_{\frac{N}{2}}$, and also that $b_{i+1} - b_i$ is either $2$,$0$ or $-2$. Since the value goes from positive to negative, and changes only in steps of 2, we will surely find some $b_i$ along $b_0$ and $b_{\frac{N}{2}}$ that is $0$. (Discrete Intermediate Value Theorem).

How to find it quickly? Binary search on $b_i$.

Suppose we know that $b_i > 0$ and $b_j < 0$, then there must exist a $b$ in between $i$ and $j$ that is exactly $0$. If we query the midpoint $m = \frac{i+j}{2}$, if $b_m > 0$, then we can query the $m$ to $j$ half. otherwise, we can query the $i$ to $m$ half.

Since obtaining a single $b_i$ needs $2$ queries, we will use $2 \log N$ queries.

Tangentially related https://www.youtube.com/shorts/mHA-emoi2PI.

## The name of this problem makes no sense.

### Subtask 1

For every $l$, try every $r$, you will need to maintain a set of occurences, and then you can check if the largest two elements are the same or not. The most straightforward way is as follows:

- use a count array to store the number of occurences of each element
- a multiset to store the set of occurences

Then check the multiset largest 2 elements.

### Subtask 2

Make a $1$ be $1$ and a $2$ be $-1$. Then we're looking for a subarray with sum of $0$.

Use prefix sums + a map for this.

### Full sollution

Let $x$ be the element in the entire array that appears the maximal number of times. If $x$ is not unique, the answer is $n$. So assume that $x$ is unique.

Observation 1: if $x$ does not have the maximum occurance in our answer subarray $[l,r]$, our answer is not optimal.

Proof:

- define $A$: occurences of $x$
- define $B$: maximum occurences of any other element than $x$

When we remove some element from the subarray, $A$ and $B$ will either decreasing by one or stay the same respectively.

Now, when the subarray is $[1,n]$, we have $A>B$, however, when the subarray is $[l,r]$ we have $A < B$. Therefore, if we slowly remove elements from $[1,n]$ to $[l,r]$, there has to be some point in time where $A=B$. Therefore, we have found a more optimal answer.

Observation 2: either $l=1$ or $a[l-1]=x$. Similarly $r=n$ or $a[r+1]=x$.

Proof: If the optimal range is $[l,r]$, we can achieve this range by shrinking $[1,n]$ while maintaining $A \geq B$. The final shrink which leads to $A=B$ will be when $a[l-1] = x$ or $a[r+1] = x$ (or $l=1$ or $r=n$).

Now, let us solve the problem with our observation. Suppose the array only contains elements $x$ and $y$. Let $S$ be an array which is $1$ if there is $x$ and $-1$ if there is $y$. Our goal is to find the longest subarray whose sum is $0$. If we can do this in $O(\text{number of y elements})$.

Briefly, we will figure out the relative positions of the elements of $y$ with respect to the elements of $x$. Consider the prefix sum of $S$. We will want to skip elements that appear only once.


In the above image, we only care about those elements that appear in the red box. It should be clear that if there are very little $y$ elements, the number of elements we care about is very little. Indeed, the number of elements we care about can be bounded by $3 \cdot \text{number of y elements}$. Because for each $y$ element, just account the $x$ elements on the same level that is nearest on the left and on the right. Then, all important $x$ elements would be accounted for.


So just code the brute force smartly and it should pass.

## Niccoriˆˆ Survey Team

https://artofproblemsolving.com/community/c6h2522661p21410015

See CSJL's solution. Note that the proof that the size of $N_a$ is at least $\lfloor \frac{k-1}{2} \rfloor+1$ that given by CSJL is wrong, that there is a vertex distance $0,1,\ldots,\lfloor\frac{k-1}{2}\rfloor$ away from vertex $a$ (consider a star graph). But his condition is correct if we assume that $N_a$ does not cover all vertices in it's connected component in $G$.

Also, the bound of $\frac{2n}{k}$ distinct vertices is tight. Let $k=2q$, then we can construct a star graph with $p+1$ vertices, where we replace each leaf with a path of length $q$ to obtain a new graph of size $pq+1$. We can choose all the leaf vertices to get $p$ leaf vertices fulfilling the property. And $\frac{2n}{k} = \frac{2pq+2}{2q} = p + \frac{1}{q}$.

<hr>

However, this is IO and not MO. There is no way the judge can force us into the worst case. What is the average size of $|S|$ if we randomize?

To make $S$ as large as possible when $G$ is connected, $G$ must be a tree.

Claim: $E(|S|)$ is maximized when $G$ is a line.

Proof: idk, it seems legit

When $G$ is a line, $E(|S|) \approx \frac{n}{2k-1}$, by linearity of expectation. Note that I never analyzed the variance. But for $100$ attempts of $n=10^4$ and $k=50$, the maximum $|S|$ was $110$, so the variance is not super big.

Is there a solution that can also recovery a certification for a disconnected pair?

## The N Lives of Raichu

https://qoj.ac/contest/760/problem/4912

The problem basically needs us to create a counter that counts up to $n = 2^{l}$, and we can only update and query at most 6 bits in one iteration.

Let's consider the sequence of all $l$ bit numbers in binary.

000
001
010
011
100
101
110
111

Let $S$ be an integer written, and $S$ needs to change according to the above sequence. Now, we want to make the transitions between them has as few bits changes as possible. Hence, we use the following algo:
- start from $ps=0$ and if $S[ps]==1$, set to $S[ps]=0$ and increment $ps$.
- else, set to $S[ps]=1$ and reset $ps$ back to 0

The way $S$ changes will look like:

000*
001*
000
010*
011*
010
000
100*
101*
100
110*
111*
110
100
000

The asteriks are the key points where things are set to 1, and $ps$ is returned back to $0$.

The sequence has length $2^{l}-1$. If we observe the index which is changed at each step, it looks like this:

`(0) (0 1) (0) (0 1 2) (0) (0 1) (0) (0 1 2 3)`

The idea is we use $5$ bits to store $ps$. On iteration $i$, retrieve the current value of $ps$. We also store $S$ in a series of bits after the first $5$ bits.

In each iteration we

1. retrieve the value of $ps$
2. Check the value of $S[ps]$
a. If it's 1, set $S[ps]$ to 0, and increment $ps$
b. If it's 0, set $S[ps]$ to 1, and set $ps$ to 0
3. Write the new value of $ps$

This will work for the first $2^{l}-1$ steps, and the last step can be handled seperately with an additional statement (in the code below, it is the `ps!=l-1` part).

int l=__builtin_ctz(n),ps=0;
for (int i=1;i<=5;++i) ps=(ps<<1)|query(i);
if (l==ps) return 1;
if (!query(6+ps)&&ps!=l-1) modify(6+ps,1),ps=0;
else modify(6+ps,0),ps++;
for (int i=1;i<=5;++i) modify(i,(ps>>(5-i))&1);
return 0;

Actually this is just the main body of the code lol