PATH3 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N, generate any boolean N\times N grid such that there are exactly three right-down paths from (1, 1) to (N, N) consisting of all ones.

EXPLANATION:

From the sample tests, we know no solution exists for N = 2.
The sample also gives us a solution for N = 3.

One possible solution now is to extend the solution for N = 3 to a larger grid.
That is,

  • Make the top-left 3\times 3 grid equal to the answer for N = 3.
    This gives us exactly three paths from (1, 1) to (3, 3).
  • Now, simply generate any single valid path from (3, 3) to (N, N).
    A simple construction is for example to keep going right till you no longer can, then keep going down till you reach (N, N).
    This corresponds to placing 1's at cells (3, 4), (3, 5), \ldots, (3, N) and then (4, N), (5, N), \ldots, (N, N).

For instance, if N = 6, the generated grid will look like

\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}

Of course, this is only one possible construction - there are many.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    if n <= 2: print(-1)
    else:
        ans = [ [0 for _ in range(n)] for _ in range(n) ]
        ans[0][0] = ans[0][1] = ans[0][2] = 1
        ans[1][1] = ans[1][2] = 1
        ans[2][1] = ans[2][2] = 1
        
        for i in range(3, n):
            ans[2][i] = ans[i][n-1] = 1
        
        for row in ans:
            print(*row)
2

I believe my solution is correct as well, can someone find the issue with this? This is also generating precisely 3 unique paths. @iceknight1093

# cook your dish here
def test():
    arr = []
    l = int(input())
    if l <3:
        return -1
    else:
        for i in range(1, l-2):
            temp = []
            temp.append("1")
            k = "0"*(l-1)
            temp.extend(list(k))
            arr.append(temp)
        for j in range(2):
            temp = []
            temp.extend(['1', '1'])
            k = '0'*(l-2)
            temp.extend(list(k))
            arr.append(temp)
        k = ('1'*l)
        arr.append(list(k))
    for i in arr:
        print(*i, sep=' ')        
    pass


for i in range(int(input())):
    test()
3

You are not printing -1