### 1509's blog

By 1509, history, 9 days ago,

I have prepared this problem some time ago but recently I realized beside my Author solution, another solution works but I just couldn't prove it. I need help on proving the correctness of this unexpected solution.

### The problem

I have prepared a problem as follow: There is this secret sequence $S$ consists of $N$ distinct numbers. Given a matrix $G$ of size $N \times N$, where $G_{i,j}=$'Y' means surely $S_i>S_j$. Otherwise, $G_{i,j}=$'?', meaning we have no information about the relation of $S_i$ and $S_j$, whether they are larger or smaller. You need to output a sequence $P = \{ P_1, P_2, ..., P_n \}$, such that $S_{P_1} > S_{P_2} > ... > S_{P_n}$, or report that it is impossible to determine exactly the order.

#### Example

\begin{array}{|c|c|c|} \hline G & 1 & 2 & 3 & 4 \cr \hline 1 & ? & ? & ? & ? \cr \hline 2 & ? & ? & Y & Y \cr \hline 3 & Y & ? & ? & Y \cr \hline 4 & Y & ? & ? & ? \cr \hline \end{array} The above input yields the answer $P= \{ 2,3,4,1 \}$ which corresponds to $S_2 > S_3 > S_4 > S_1$. This is the only possible answer.

#### Constraints:

• $(1 \leq N \leq 400)$
• Time limit: 1s

### The intended solution

This problem can be solved by turn it into the All Pairs Shortest Path problem. First, I create a cost matrix $C$ of size $N \times N$. $C_{i,j} = 0$ if $G_{i,j}$ equals to 'Y', otherwise, $C_{i,j} = \infty$. Then I run Floyd-Warshall on $C$, which produces a "complete" matrix $C$. After that, if $S_i$ is the largest element then row $C_{i}$ will have exactly $N-1$ zeros, second largest will have $N-2$ zeros, and so forth.

If the above is not possible, then there is no answer for that input.

### The unexpected solution

The solution is as follow:

Code

It needs at max 2 rounds to completely fill the $G$ matrix, after that I only need to counts the number of 'Y' on each row to reconstruct the sequence $S$. I have ran this solution on multiple tests against the first solution but it seemed to always give correct results.

• For sequence $S=\{S_1 > S_2 > S_3 > ... > S_n\}$ and the its reverse sequence, it only needs 1 round.
• The above requires only 1 run maybe because I traverse all tuples in the "correct" order. For other cases, sequence $S$ is a permutation of the first case and because I go through all possible ordered tuples, there will be a moment that I go into the "correct traverse order" for the current sequence $S$, but have not finished it. So it needs another round to complete the traversing... Maybe.

I would like to see the proof for this, or how can I approach it, so any idea would be appreciated.

• +22

 » 8 days ago, # |   +34 This might be relevant: Floyd-Warshall works with any order of loops in at most 3 iterations. https://arxiv.org/pdf/1904.01210.pdf
•  » » 8 days ago, # ^ |   +17 P.S. what you probably wanna look at is Theorem 2 which is exactly what you are asking about.
•  » » » 8 days ago, # ^ |   +8 It is what I am looking for! Thanks alot!