We consider a set of integers $$$S$$$ to be anti-closed if there do not exist elements $$$x$$$, $$$y$$$ and $$$z$$$ in $$$S$$$ where $$$x+y=z$$$ ($$$x$$$, $$$y$$$ and $$$z$$$ do not necessarily have to be distinct).

For example:

• $$$\{2, 3, 7\}$$$ is anti-closed, because no such $$$x$$$, $$$y$$$, $$$z$$$ exist
• $$$\{1, 3, 7, 10\}$$$ is not anti-closed, because $$$3$$$, $$$7$$$, and $$$10$$$ are all in the set and $$$3+7=10$$$
• $$$\{2, 4\}$$$ is also not anti-closed, because $$$2$$$ and $$$4$$$ are in the set and $$$2+2=4$$$

You are given an array $$$a$$$ of $$$n$$$ distinct integers. Partition it into at most $$$60$$$ anti-closed subsequences. Formally, find an array $$$b$$$ of size $$$n$$$ such that

• $$$1 \leq b_i \leq 60$$$ for all $$$1 \le i \le n$$$
• For each $$$1 \le x \le 60$$$, the subsequence of $$$a$$$ containing all values at indices $$$i$$$ where $$$b_i = x$$$ is anti-closed (The empty subsequence is considered anti-closed)

It can be shown that a solution always exists.

You have a hand of cards, where each card has one of $$$n$$$ types. For each $$$i$$$ from $$$1$$$ to $$$n$$$, you have $$$a_i$$$ cards with type $$$i$$$, and the bank has infinite cards with type $$$i$$$.

You can perform the following trade with the bank any number of times:

Choose any two cards with the same type from your hand, and exchange them for a single card from the bank with any type except the type of the cards you just exchanged. Note that the bank only has cards with types $$$1$$$ through $$$n$$$, so you cannot trade for cards with any other types.

For example, here is a valid sequence of trades on the first sample case:

What is the maximum number of trades you can perform?

You are given an array $$$a$$$ of $$$n$$$ integers. A sub-array $$$[a_l, a_{l+1}, \cdots a_r]$$$ is considered end-balanced if $$$l \lt r$$$ and $$$a_l + a_r = a_{l+1} + ... + a_{r-1}$$$.

For example, the subarrays $$$[4, 9, 5]$$$, $$$[-1, 3, 5, 9]$$$, and $$$[0, 0]$$$ are considered end-balanced, and the subarrays $$$[0]$$$, $$$[-2, -3, -5]$$$, and $$$[1, 1]$$$ are not.

How many subarrays of $$$a$$$ are end-balanced?

You are given a tree on $$$n$$$ nodes rooted at node $$$1$$$. A spider and a fly are in the tree. The spider has three legs which are initially on nodes $$$a$$$, $$$b$$$, and $$$c$$$. The fly is on node $$$f$$$ and does not move.

Some nodes are considered to be in the shadow of the spider. A node is in the shadow of the spider if it lies on any of the three shortest paths between its legs, $$$a$$$–$$$b$$$, $$$a$$$–$$$c$$$, and $$$b$$$–$$$c$$$.

The spider can move its legs from vertices $$$a$$$, $$$b$$$, $$$c$$$ to vertices $$$a'$$$, $$$b'$$$, $$$c'$$$ if the size of its shadow remains constant and $$$\max\{\textrm{dist}(a, a'), \textrm{dist}(b, b'), \textrm{dist}(c, c')\}\leq 1$$$. The function $$$\textrm{dist}(u,\,v)$$$ indicates the number of edges on the shortest path between nodes $$$u$$$ and $$$v$$$ in the tree.

For example, here is one possible sequence of two moves by a spider with $$$6$$$ nodes in its shadow. The vertices that have a red outline are in the shadow of the spider, and the vertices that are colored red are the spider's legs.

The spider eats through its legs. Determine whether the spider can move any of its legs to the fly's location, after any number of moves (possibly zero).

You are faced with a combination lock that consists of an $$$n$$$ by $$$m$$$ grid of dials. A $$$k$$$-dial is a dial that can display values $$$0, 1, \cdots k-1$$$. A $$$k$$$-dial currently displaying value $$$v$$$ can be incremented to make it display value $$$(v + 1)\mod k$$$.

This particular lock consists of $$$3$$$-dials and $$$5$$$-dials in a checkerboard arrangement, with the top left dial being a $$$3$$$-dial. In a single move, you can increment a dial and all of its horizontal and vertical neighbors.

For example, here is one possible sequence of moves on a grid with $$$n=3$$$, $$$m=4$$$ (where $$$3$$$-dials are gray and $$$5$$$-dials are white):

Initially, all of the dials are displaying $$$0$$$. You remember what positions the dials must be in for the lock to open, but you forgot the combination of moves to reach it. Find a sequence of moves that sets all dials to the correct positions. You do not need to minimize the number of moves, but you can use no more than $$$20nm$$$ moves.

It can be shown that such a solution always exists.

We define a bitwise triangle to be a triplet of distinct integers $$$(a,\,b,\,c)$$$ with $$$a\&b\neq0$$$, $$$a\&c\neq0$$$, and $$$b\&c\neq0$$$, where $$$\&$$$ indicates the bitwise AND operator.

You are given an integer $$$n$$$. We define a triangle packing to be a set of pairwise disjoint bitwise triangles consisting of integers from $$$1$$$ to $$$n$$$ inclusive. Find a maximal triangle packing (one with the maximum number of bitwise triangles).

Two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ are considered to be a knight-move apart if exactly one of the following conditions holds:

• $$$|x_1 - x_2| = 2$$$ and $$$|y_1 - y_2| = 1$$$
• $$$|x_1 - x_2| = 1$$$ and $$$|y_1 - y_2| = 2$$$

Notice that this definition closely matches how a knight moves in chess. For example, here are three pairs of points that are a knight-move apart:

You are given integers $$$p$$$ and $$$q$$$. Find a simple lattice polygon whose area is $$$p/q$$$, where each pair of adjacent vertices is a knight-move apart, or state that no such polygon exists.

A polygon is simple if there are exactly two edges touching each vertex, and no two edges of the polygon intersect except at its vertices. A polygon is a lattice polygon if the coordinates of each of its vertices are integers.

There are $$$n$$$ lights in a row, all initially deactivated. Some lights, when activated, will illuminate themselves and all lights to their left. The others, when activated, will illuminate themselves and all lights to their right.

This image shows the result of activating the fourth light (and nothing else) in the first sample case. The first four lights are illuminated, and everything else is not.

You have already figured out the minimum number of lights that need to be activated to illuminate everything, but now, you're wondering how many good subsets of lights exist.

A subset $$$S$$$ of the lights is considered good if when you activate the lights in $$$S$$$ (and only the lights in $$$S$$$), every light on the row is illuminated.

How many good subsets are there? Since the answer may be large, output it modulo $$$10^9+7$$$.

There is an $$$n$$$ by $$$m$$$ grid of black and white squares. In one operation, you can pick any two adjacent squares of the same color and swap the colors of both. For example, here is a valid sequence of two operations on a grid with $$$n=4$$$, $$$m=3$$$:

You are also given a target grid of $$$n$$$ by $$$m$$$ black and white squares. Perform at most $$$200nm$$$ operations on the starting grid to reach the target grid, or state that it is impossible to do so. You do not need to minimize the number of operations.

It can be shown that if there is a solution, there is one that uses at most $$$200nm$$$ operations.

You want to find two permutations $$$p$$$ and $$$q$$$ of size $$$n$$$ that satisfy $$$m$$$ restrictions of the form $$$(p_i-p_j)\cdot (q_i-q_j) \gt 0$$$.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2, 3, 1, 5, 4]$$$ is a permutation, but $$$[1, 2, 2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1, 3, 4]$$$ is also not a permutation ($$$l=3$$$ but there is $$$4$$$ in the array).

Find two distinct permutations $$$p$$$ and $$$q$$$ of size $$$n$$$ such that all restrictions are satisfied, or state that it is impossible to do so. $$$p$$$ and $$$q$$$ are considered distinct if there is at least one index $$$i$$$ where $$$p_i \neq q_i$$$.

Alice and Bob are playing a game on a tree rooted at node 1. A token is placed on the root then the players take turns making moves with Alice moving first. During a move a player must move the token from the node its on to one of that node's children. If there are no legal moves available, then the player whose turn it is will lose.

Since Alice and Bob are too good at this game they decided to play a modified version of the game. Before the game begins, Alice can add a single directed edge $$$(u, v)$$$ to the tree. Then, during the game, if the token is on vertex $$$u$$$ and the extra edge is present, the current player can choose to move the token to vertex $$$v$$$ and delete the extra edge (preventing it from being used multiple times in one game).

Of the $$$n^2$$$ possible pairs $$$(u, v)$$$ Alice can choose, how many will allow Alice to win the game assuming both players play optimally? Note that $$$u=v$$$ is allowed, as are $$$(u, v)$$$ pairs that match an existing edge in the tree (in either direction).

There is an $$$n$$$ by $$$m$$$ grid of white squares. You want to place a $$$k$$$ by $$$k$$$ red square and a $$$k$$$ by $$$k$$$ blue square on this grid such that they do not overlap. For example, here is a valid solution for $$$n=6$$$, $$$m=8$$$, $$$k=3$$$:

How many ways are there to do this? Two ways are considered different if at least one square is a different color in each.

Since the answer may be large, output it modulo $$$10^9+7$$$.

There were too many constructive problems in this contest, so we decided to set a standard data structure problem.

You are given a tree with $$$n$$$ labeled nodes. Each node also has a blank value initially.

The longest increasing tree subsequence between two nodes $$$(u, v)$$$ on the tree is computed as follows:

• Write down all the nonblank values from the nodes on the path from $$$u$$$ to $$$v$$$, in order. Compute the longest increasing subsequence$$$^\dagger$$$ of the resulting sequence.

You are given $$$n$$$ updates, $$$x_1, x_2 \dots x_n$$$. For update $$$i$$$, fill in the value $$$i$$$ at node $$$x_i$$$. After each update, compute the longest longest increasing tree subsequence among all pairs of nodes $$$(u, v)$$$ in the tree.

It is guaranteed that all $$$x_i$$$ values are distinct.

$$$^\dagger$$$ Define a sequence of integers $$$a_i...a_m$$$. A subsequence $$$a_{i_1}, a_{i_2}, ..., a_{i_k}$$$ where $$$1 \leq i_1 \lt i_2 \lt \cdots \lt i_k \leq m$$$ is called increasing if $$$a_{i_1} \lt a_{i_2} \lt a_{i_3} \lt ... \lt a_{i_k}$$$. An increasing subsequence is called longest if it has maximum length among all increasing subsequences.

You are given two strings $$$s$$$ and $$$t$$$. In one operation, you can delete all the odd-indexed characters from $$$s$$$ or all the even-indexed characters from $$$s$$$.

For example, if you perform an operation on the string abcdefg, you could choose to turn it into aceg or bdf.

After performing any number of operations on $$$s$$$ (including zero), is it possible for $$$s$$$ to equal $$$t$$$?