1000A - Codehorses T-shirts

$$$a=1$$$ and $$$b=x-1$$$ always work.

1000B - Light It Up

Let the number of distinct elements in $$$a$$$ be called $$$d$$$. Clearly, the answer is limited by $$$d$$$. Now, you can construct your subsequence as follows: take the smallest element from the first copy, the second smallest element from the second copy, and so on. Since there are enough copies to take every element, the answer is $$$d$$$.

1000C - Covered Points Count

Notice that there will be a path that passes through the edge labeled $$$0$$$ and the edge labeled $$$1$$$ no matter how you distribute the weights, so there's always a path with $$$MEX$$$ $$$2$$$ or more. If any node has degree 3 or more, you can distribute the labels $$$0$$$, $$$1$$$, and $$$2$$$ to edges incident to this node and distribute the rest of the labels arbitrarily. Otherwise, the tree is a bamboo, and it doesn't actually matter how you distribute the labels, since there will be a path with $$$MEX$$$ $$$n-1$$$ anyway.

1000D - Yet Another Problem On a Subsequence

First, let's look at some special cases. If $$$u>v$$$ or $$$u$$$ and $$$v$$$ have different parities, there's no array. If $$$u=v=0$$$, the answer is an empty array. If $$$u=v \neq 0$$$, the answer is $$$[u]$$$. Now, the length is at least 2. Let $$$x=\frac{v-u}{2}$$$. The array $$$[u,x,x]$$$ satisfies the conditions, so the length is at most 3. We just need to figure out whether there's a pair of number $$$a$$$ and $$$b$$$. Such that $$$a \oplus b=u$$$ and $$$a+b=v$$$. Notice that $$$a+b=a \oplus b+2*(a$$$&$$$b)$$$, so we know that $$$a$$$&$$$b=\frac{v-u}{2}=x$$$ (surprise surprise.) The benefit of getting rid of $$$a+b$$$ and looking at $$$a$$$&$$$b$$$ instead is that we can look at $$$a$$$ and $$$b$$$ bit by bit. If $$$x$$$ has a one in some bit, $$$a$$$ and $$$b$$$ must both have ones, so $$$a \oplus b=u$$$ must have a 0. If $$$x$$$ has a zero, there are absolutely no limitation on $$$u$$$. So, if there's a bit where both $$$x$$$ and $$$u$$$ have a one, that is to say $$$x$$$&$$$u\neq0$$$, you can't find such $$$a$$$ and $$$b$$$, and the length will be 3. Otherwise, $$$x$$$&$$$u=0$$$ which means $$$x \oplus u=x+u$$$, so the array $$$[u+x,x]$$$ works. Can you see how this array was constructed? We took $$$[u,x,x]$$$ which more obviously works and merged the first 2 elements, benefiting from the fact that $$$u$$$&$$$x=0$$$.

1000E - We Need More Bosses

Notice that for each element in the array, if some perfect square divides it, you can divide it by that perfect square, and the problem won't change. Let's define normalizing a number as dividing it by perfect squares until it doesn't contain any. Notice than any number that has 3 different prime divisors has at least 8 divisors, so after normalizing any element in the array, it will be $$$1$$$, $$$p$$$, or $$$p*q$$$ for some primes $$$p$$$ and $$$q$$$. Let's create a graph where the vertices are the prime numbers (and $$$1$$$,) and the edges are the elements of the array. For each element, we'll connect $$$p$$$ and $$$q$$$ (or $$$p$$$ and $$$1$$$ if it's a prime after normalizing, or $$$1$$$ with $$$1$$$ if it's $$$1$$$ after normalizing.) What's the significance of this graph? Well, if you take any walk from node $$$p$$$ to node $$$q$$$, multiply the elements on the edges you took, and normalize, the product you get will be $$$p*q$$$! That's because every node in the path will be visited an even number of times, except $$$p$$$ and $$$q$$$. So the shortest subsequence whose product is a perfect square is just the shortest cycle in this graph!

To find the shortest cycle generally, you try every node as a source, bfs, and try to add every edge not present in the bfs tree. However, you don't have to try every source here. That's because no edge connects a pair of nodes with indices greater than $$$\sqrt{MaxAi}$$$, so your cycle will definitely pass across a node with index $$$\le\sqrt{MaxAi}$$$. You can only consider these nodes as sources.

Bonus task: try to prove the answer can't exceed $$$2\sqrt{MaxAi}$$$.

1000F - One Occurrence

Let $$$sq$$$ denote $$$\lceil\sqrt{n}\rceil$$$.

A solution using DFS trees

If you're not familiar with back-edges, I recommend reading this first.

Let's take the DFS tree of our graph. Assume you're currently in node $$$u$$$ in the DFS. If $$$u$$$ has $$$sq-1$$$ or more back-edges, look at the one that connects $$$u$$$ to its furthest ancestor. It forms a cycle of length at least $$$sq$$$. If $$$u$$$ doesn't have that many back-edges, you can add it to the independent set (if none of its neighbors was added.) That way, if you don't find a cycle, every node only blocks at most $$$sq-1$$$ other nodes, the ones connected to it by a back-edge, so you'll find an independent set!

A solution using degrees

There's a pretty obvious greedy algorithm for finding large independent sets: take the node with the minimal degree, add it to the independent set, remove it and all its neighbors from the graph, and repeat. If at every step the node with the minimal degree has degree $$$\le$$$ $$$sq-1$$$, that algorithm solves the first problem. Otherwise, there's a step where EVERY node has degree at least $$$sq-1$$$. For graphs where every node has degree at least $$$d$$$, you can always find a cycle with length $$$d+1$$$: take an arbitrary node as a starting point, and keep trying to extend your path. If one of this nodes' neighbors is not already in the path, extend that path with it. Otherwise, all your $$$d$$$ neighbors are on the path. Take the edge to the furthest and you'll form a cycle of length at least $$$d+1$$$!