Try to solve the problem assuming we may light/extinguish the central torch for each operation, then try to execute the same sequence by only lighting. While there are operations we can make, make them. In the end the remaining operations form consecutive groups, each of size 2. If there's an unlit torch next to such group, we can light it, do both operations in the group, then light it again, to the same effect. If all 2-groups are 1 apart, don't do anything as everything if fixed already.

Note that if you enumerate the mode x, you only care about x and x-k in the end. So enumerate all possible x and it becomes finding a maximum value for a prefix sum formula.

I also got WA 7 at first because I mishandled the case k=0, you should check if your solution works in that case

Apply the solution of ABC231 Problem E on the divisibility graph of the factors of b-a.

You will find the TL is even tighter in ECFinal 2020 G. We actually set a TL for those code which has no optimization in 4*4 matrix multiplication to pass while the std code runs within 500ms.

It is trivial to halve the constant since you only need to compute the upper diagonal. And you may further find that you only need to compute C(4,2)=6 in the end.

UPD: Not sure why it is 3s in gym for that problem now. When I was testing that one, it was set in 1s and you have to expand the multiplication to pass.

I use the sqrt decomposition also fit the time during the contest.

this round

H: Observe that if you enter a vertex $$$u$$$ for the first time, it can have at most two children from where you can collect the points. If it has some child $$$v$$$ with $$$t_v = 3$$$, you may go to some other child $$$w$$$, collect its points, come back to $$$u$$$ and then go to $$$v$$$. Alternatively, you may just go to some child and collect its points.

Equivalently, we want to color the tree in three colors: white (did not collect points), black (did collect points) and red (did collect points but "in passing" like from $$$w$$$ above, without chance to collect points from its children). The coloring must satisfy the following constraints:

• A red vertex may have only white children.
• Any vertex must have at most one black and one red child.
• A vertex can only have a red child if it also has a black child with $$$t_i = 3$$$

and must maximize the sum of points in red and black vertices. This can now be solved using a classical tree dp, where $$$\mathrm{dp}[u][k]$$$ is the maximum number of points you can get from the subtree of $$$u$$$ given that $$$u$$$ has the color $$$k$$$.

D: This sorting algorithm can be reformulated as follows: construct an increasing subsequence greedily (start from the first element, each time take the next element strictly bigger then the current maximum), cycle shift it by one, then perform an insertion sort. And you need to print the length of the increasing subsequence + the number of swaps performed by an insertion sort. For one array this is easily done in $$$O(n\log n)$$$: find the increasing subsequence in $$$O(n)$$$, cycle shift it, then for each element add the number of distinct values on the prefix, that are bigger than this element.

Now we need to recalculate the answer after adding an element to the array. If this element is not a maximal one, this is pretty easy, since it does not affect any of the previous steps. If this element is a new maximum, the length of the increasing subsequence increases by one, and also one more swap is needed for some iterations of the insertion sort. It is not hard to understand that this swap is needed for the elements that are positioned after the second occurrence of the previous maximum (hard to explain, but easy to understand from some examples). After that everything can be easily recalculated.

E: I'm pretty sure all solutions would be pretty much equivalent to matrix multiplications. The key here is that the operations (a += k and history += a^2) are linear operations on history, a^2, a, and 1, which lets us compose them succinctly. Matrices and matrix multiplication are just notations for linear operators, but I think all solutions probably rely on this linearity.

F: There are 2 cases, either one polygon contains the other, or there's a separating line through the origin. In the first case, the outer polygon must exactly be the convex hull of all points, so we can check this solution. In the second case, we can sort the points by the angle to the origin, and then sweep the angle of the dividing line. Note that within each convex polygon, the points must be sorted by angle to the origin, so we can precompute whether each triple of neighboring points is actually convex. This lets us efficiently check the validity of any solution, so we can just take the max of all valid ones.

K: This problem asks for the number of sets of 4 points which form and independent set, minus the number of sets which form a clique. Let's focus on counting the number of independent sets. We can count this using PIE: we want the number of sets of 4 points, minus the number of sets of 4 points and 1 edge among them, plus the number of sets of 4 points and 2 edges among them, etc. In particular, we need to add the number of sets of 4 points with 6 edges among them, i.e. cliques. Thus, we only need to count the number of each configuration of 4 points with up to 5 edges. These are:

1. Four points with zero edges
2. Single edge and 2 points
3. Two edges with a common vertex and a point
4. Two parallel edges
5. Three edges sharing a common vertex (a claw)
6. Three edges forming a triangle and a point
7. Three edges forming a path
8. Four edges forming a triangle with an extra edge attached
9. Four edges forming a square
10. Five edges forming two triangles glued together

Of these values, numbers 1 through 5 are trivial, numbers 6, 7, 8, and 10 can be counted by enumerating all triangles, and number 9 requires counting 4-cycles. We do both of these in $$$O(E \sqrt{E})$$$ time. There are a few ways to do this, here's a pretty nice one.

Sort all vertices of the graph by degree, and then direct each edge from the earlier (smaller) vertex to the later one. Then, we claim that each vertex has outdegree at most $$$\sqrt{2E}$$$. This is because all later vertices must have degree at least equal to your outdegree, but the total degree is $$$2E$$$, so there can be at most $$$\sqrt{2E}$$$ out-neighbors.

Now, to enumerate triangles, we can casework on the edge between two smallest vertices; fixing this, there are at most $$$\sqrt{2E}$$$ choices for the outedge from the middle to the largest vertex, so we can enumerate all triangles in $$$O(E \sqrt{E})$$$ time.

To enumerate 4-cycles, we will casework on the diagonal containing the largest vertex; let's denote that vertex by $$$z$$$ and the opposite vertex by $$$x$$$. Fix $$$x$$$, and consider every $$$y$$$ adjacent to $$$x$$$; then, $$$z$$$ must be an out-neighbor of $$$y$$$. Thus, we can enumerate them naively and count the number of times each $$$z$$$ is 2 away from $$$x$$$; taking those counts choose 2 gives the number of squares. The total runtime is also $$$O(E \sqrt{E})$$$, since each (undirected) edge is used twice as the edge between $$$x$$$ and $$$y$$$, and $$$y$$$ has at most $$$O(\sqrt{E})$$$ out-neighbors.

We had this code in our ICPC book from before: https://github.com/ecnerwala/icpc-book/blob/master/content/graph/cycle-counting.cpp.

G: Instead of diameter, we can maximize the length of some path instead (and don't care about any other paths). We can use $$$dp[p][x][y]$$$, meaning the maximum path length from node $$$x$$$ to node $$$y$$$, and that we are about to place $$$a_p$$$.

For each path $$$(x,y)$$$, we additionally need to store the number of "free" edges we can use without extending $$$(x,y)$$$.

For a fast transition, we add two more states: $$$dx$$$ is a boolean meaning we have not assigned some cost to the edge $$$(x', x)$$$ ($$$x'$$$ is the previous $$$x$$$), and $$$dy$$$ the same thing but for $$$y$$$. Then the transition depends on $$$dx$$$ and $$$dy$$$: in particular, if $$$dx=1$$$ we can either use a current "free" edge or iterate on vertices adjacent to $$$x$$$ for extending the path. If $$$dx=0$$$ we can either use a "free" edge or assign $$$a_p$$$ to the last edge of $$$x$$$ (so increase the value of $$$dp$$$ by $$$a_p$$$). Same for $$$dy$$$.

Total complexity is $$$O(n^3)$$$.

Can you explain, what is matrix idea to solve E?

B: we will try to reduce both graphs to canonical form. If canonical forms coincide, we perform the reduction for $$$A$$$, and undo the reduction for $$$B$$$ after that.

If you make operations $$$(a, b, c, d, x)$$$ and $$$(b, a, c, d, x)$$$, weight of $$$ab$$$ edge will increase by $$$2x$$$, and weight of $$$cd$$$ will decrease by $$$2x$$$. This allows to change weights pretty much arbitrarily, preserving the total sum, as well as parity of each individual weight. We will "canonize" parity first, and then do some even steps.

If $$$n$$$ is small (say, at most $$$5$$$), we can look for the lex. smallest reachable parity configuration with BFS. If $$$n = 4$$$, sum of opposite edge weights is always preserved, thus after parity fixing we can make all edges not adjacent to vertex $$$1$$$ to be $$$0$$$ or $$$1$$$, and that's canonical form. If $$$n = 5$$$, we can make all edges other than $$$(1, 2)$$$ to be $$$0$$$ or $$$1$$$ by transferring their weights to $$$(1, 2)$$$ with the $$$2x$$$ gadget above, possibly with an intermediate step.

If $$$n \geq 6$$$, we can always make at most one edge have odd weight. If edges $$$ab$$$ and $$$cd$$$ are odd, and $$$e, f$$$ are any other two vertices, then applying operations to $$$acef, adef, bcef, bdef, abcd$$$ (all with $$$x = 1$$$) makes $$$ab$$$ and $$$cd$$$ even while preserving all other parities. Doing this repeatedly (possibly with intermediate steps, like above) we can make all edges, except possibly $$$(1, 2)$$$, have even weights. After that we can gather all even weights into $$$(1, 2)$$$ similar to the above.

UPD: also I'm stupid and we just need to reduce the difference of $$$A$$$ and $$$B$$$ to all zeros lol.

Maybe you should try submitting with 32-bit compiler. I've seen this on others submission attempts to this problem.