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

Revision en16, by 3509, 2022-03-26 05:17:03

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.

Comments

  • 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.

Tags help, algorithm proving, graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English 3509 2022-03-26 05:17:03 73
en15 English 3509 2021-04-08 18:24:48 14
en14 English 3509 2021-04-08 10:55:28 183
en13 English 3509 2021-04-08 09:29:09 26 (published)
en12 English 3509 2021-04-08 09:21:53 85
en11 English 3509 2021-04-08 08:02:51 12
en10 English 3509 2021-04-08 08:02:18 38
en9 English 3509 2021-04-08 08:01:23 33
en8 English 3509 2021-04-08 07:58:53 15
en7 English 3509 2021-04-08 07:58:16 7
en6 English 3509 2021-04-08 07:56:44 66
en5 English 3509 2021-04-08 07:53:15 1867
en4 English 3509 2021-04-08 07:15:48 130
en3 English 3509 2021-04-08 07:15:37 132
en2 English 3509 2021-04-08 07:12:25 240
en1 English 3509 2021-04-08 07:09:16 711 Initial revision (saved to drafts)