Yes, I also thought that it was important in the contest, but if you carefully read and understand all the limitations in the first operation, it will become clear that you can get any situation that is described in the solution.

Your link is incorrect. This one I think you mentioned. Try this test: 100. Your output I think red, instead of cyan.

Then I have a bonus for you:

• remove the condition that vertex $$$n$$$ is reachable from every vertex
• reduce n to $$$36$$$
• answer the question whether the token will end up in $$$n$$$ or not, and if so, at what time

Here is how I thought of it it, Since we have to produce minimum magnitude and all Gcds should be distinct, I thought the gcds should be of the form 1,2,3,4,5. I didn't know of this will work, but just a trail. I tried to produce gcd = 1. This can easily be done by writing 2,3. I also noticed that 1 cannot be written anywhere as it make gcds of column and row same. So in the first row I wrote 2,3,4,5,6,....,m + 1.after this I observed that I can make gcds of each column the topmost element if each column is a multiple of the topmost element. After this, I thought that if I multiply the first row by some number and write it in the second row, the gcds of the second row will be the number it was multiplied with as I can take the number common and the gcds of remaining elements is one. It's easy to see how this works after this.

I think my solution for C plainly describes the thought process involved. here

I created two arrays(one for row and one for column) that contains the targeted minimum disjoint gcd values that can be achieved ie { 1,2...r...(r+c) }then I filled the matrix by multiplying each row array element with column array element. By analyzing output you can infer {1...r} values can be achieved by taking gcd of each row and remaining {r+1...c} can be achieved by taking gcd of each column.

Since we want to minimise GCD we may want to start with putting 1 but we can't do so because it will make the GCD of that particular row and column 1 which will not satisfy condition that GCD values must be distinct. Firstly, try a simpler case like when r = 1 and c > 1, we can have values like 2,3,4,...c-1. Similarly, for case when c = 1 and r > 1. Now, Let us consider case when r = 3 and c = 3. Then in first row we can have 4,5,6 which have GCD = 1. Now observe that for second row we can multiply the first row by 2, which gives for second row 8,10,12 which will have GCD as 2. Similarly, third row will be 12,15,18 having GCD as 3. And for the first column GCD will be 4, second column GCD will be 5 and for third column GCD will be 6. So set of distinct values of GCD = {1,2,3,4,5,6} and also we can say that r+c will always be the optimal value.

I have a similar solution to you, and the complexity is also linear: 67162965.

We notice that the number of subtrees of $$$i$$$ with depth at least $$$k$$$ is always smaller than that of $$$k - 1$$$. So, instead of looping $$$k$$$ from $$$1$$$ upwards, we loop $$$k$$$ from $$$n$$$ downwards, which will make every variable in the computation non-decreasing, so we don't have to use any data structures; straight up updating every variable using the $$$max$$$ function is enough.

Edit: Courtesy to GreymaneSilverfang for helping me with this discovery :D

We assume that the debt is already minimal, and there is a vertex triple such that ... We managed to reduce the debt, so it wasn't minimal. This means that for a minimal debt, there cannot be such triple.

         a[u] = 0;
         a[v] = a[v]+a[u];

You should swap these two lines.

"It follows that any solution in which every vertex has either outgoing or incoming edges is constructible using finite number of applications of rules." Because if there is combination of vertices like a->b->c then this combination surely results in a decreased total debt i.e. why using any number of operations we can achieve the state of graph where every vertex has either incoming or outgoing edge.

For each vertex, we assign a level as the shortest distance for the vertex N.

Core part is making function succ(l, State={position, color, time}) -> new_State: this function simulate the state while a token reach one of the vertex whose level is l(we assume the first position of token is a vertex whose level is higher than l). We can memoize this function by (l, color of vertexes whose level is higher than l).

How many states this function memoized? ... actually I don't have any proof(so, my solution is unproved, sorry). My intuition say that it is exponential, but quite small (even in the worst case).

My solution uses simulation with memoization.

Suppose that we start in some state, and the token is in vertex $$$i$$$. If we know only the state of vertex $$$i_1=i$$$, we can simulate one step (or two, if the first step moves the token to the same vertex). Then, the token lands at vertex $$$i_2\ne i_1$$$. If we know the state of vertices $$$i_1$$$ and $$$i_2$$$, we can simulate more steps until the token lands at vertex $$$i_3\ne i_1,i_2$$$. This way, it is possible to construct the following lazy DP: the state is $$$(i,k,\textrm{state of }i_1\ldots i_k)$$$, and the value is $$$(i_{k+1},\textrm{new state of }i_1\ldots i_k,\textrm{number of steps})$$$.

The simulation function (run in my solution) takes the following arguments: initial vertex, current state and a set of vertices. It runs the simulation until the current vertex is not in the set. There is also an option to limit the number of steps. It starts with $$$k=1$$$ and $$$i_1=i$$$ to compute $$$i_2$$$, $$$i_3$$$ and so on. To compute DP for some $$$k$$$, it runs the same procedure recursively with starting vertex $$$i_k$$$ and the set $$${i_1,\ldots,i_k}$$$. For $$$k=1$$$, a straightforward simulation is used (this requires at most two steps).

Your logic is half correct,your solution does produce disjoint gcd arry or diverse matrix,but it is failing to produce the diverse matrix that minimises the magnitude For eg. dry run your program for 3 3,you will get it.

1. Since the bal of all the vertices can either be positive or negative (positive for incoming edge and negative for outgoing edge), and you have to match the positive vertices with negative vertices (as the person who is in debt has to pay it to someone and it doesn't matter who pays to whom, all that matters is what one person owes has to be fulfilled by 1 or more than 1 vertices), when you take the sum of all the absolute values of the balances, you are left with 2 times the total debt, because of the fact that you are taking the sum of absolute values. It won't be wrong to say that the total sum of all the balances, after matching all the positives with negative will be zero, because, in the end, all the people in debt have to repay it. Hence, the claim in the editorial is rightfully the minimum.
2. You take each positive balance, take the absolute value of one negative vertex, take the minimum of the positive and abs(negative), add the index of negative, the index of positive and min value to your final result, and keep on greedily matching positive and negative vertices.

Hey, I was also stuck on this. However, the question states that ti < ai.

For a valid state, we take the subgraph of all active arcs.

It's easy to see that there exists exactly one vertex such that:

• The active arc starting from it ends at v.

• The path from 1 to the said vertex does not include v.

Then the only possible predecessor of v is the said vertex.

The rest is induction.

upd:

I seem to have missed the case when v=1...

Forget what I've said before.

take the directed multigraph, where each arc appears exactly the number of times it is traversed.

Given the constraints of the matrix, it's easy to see that there exists an Euler path(if it's connected, hence the condition we're checking).

Consider constructing an Euler path the following way:

Start from 1;

If the vertex we're at has been traversed odd number of times, take the blue arc; else take the red arc.

It could be checked that this Euler path is the legitimate path.

P.S.

Since all other vertices must be traversed before v, it could be checked that they should all be able to go to v using only active arcs.

This is the worst and the most unrigorous explanation I have ever seen.