[Answered] Looping a wrongly formulated FloydWarshall gives correct results?

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 SS consists of NN distinct numbers. Given a matrix GG of size N×NN×N, where Gi,j=Gi,j='Y' means surely Si>SjSi>Sj. Otherwise, Gi,j=Gi,j='?', meaning we have no information about the relation of SiSi and SjSj, whether they are larger or smaller. You need to output a sequence P={P1,P2,...,Pn}P={P1,P2,...,Pn}, such that SP1>SP2>...>SPnSP1>SP2>...>SPn, or report that it is impossible to determine exactly the order.

Example

The above input yields the answer P={2,3,4,1}P={2,3,4,1} which corresponds to S2>S3>S4>S1S2>S3>S4>S1. This is the only possible answer.

Constraints:

• (1≤N≤400)(1≤N≤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 CC of size N×NN×N. Ci,j=0Ci,j=0 if Gi,jGi,j equals to 'Y', otherwise, Ci,j=∞Ci,j=∞. Then I run Floyd-Warshall on CC, which produces a "complete" matrix CC. After that, if SiSi is the largest element then row CiCi will have exactly N−1N−1 zeros, second largest will have N−2N−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:

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

Comments

• For sequence S={S1>S2>S3>...>Sn}S={S1>S2>S3>...>Sn} 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 SS 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 SS, 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.