Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    N = II()
    from collections import deque
    A = [deque(map(int,input().split())) for _ in range(N)]
    days = 0

    while True:
        #print(A)
        firstgame = True
        # desired = [ A[i][idxs[i]] for i in range(N)]
        desired = [ A[i][0] for i in range(N)]
        # desired = []
        # for i in range(N):
        #     idx = idxs[i]
        #     l = A[i]
        #     #print(N,idx)
        #     desired.append(l[idx])
        # print(desired)

        if desired.count(-1) == N:
            print(days)
            return

        for i in range(N):
            
            a = desired[i]
            if a < 0:
                continue
            b = desired[a-1]
            # a = A[i][0]
            # if a < 0:
            #     continue
            # b = A[a-1][0]
            # if b < 0:
            #     continue
            # matched
            if b == i+1:
                if len(A[a-1]) == 1:
                    A[a-1][0] = -1
                else:
                    A[a-1].popleft()
                
                if len(A[i]) == 1:
                    A[i][0] = -1
                else:
                    A[i].popleft()
                    
                desired[a-1] = -1

                # idxs[i] += 1
                # if idxs[i] == N-1:
                #     idxs[i] = N-2
                #     A[i][-1] = -1

                # desired[a-1] = -1
                # A[a-1][idxs[a-1]] = -1

                # idxs[a-1] += 1
                # if idxs[a-1] == N-1:
                #     idxs[a-1] = N-2
                #     A[a-1][-1] = -1
                
                if firstgame:
                    firstgame = False
                    days += 1
        if firstgame:
            print(-1)
            return 
            


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def getlist():
	return list(map(int, input().split()))

X = []
N = int(input())
for i in range(N):
	A = getlist()
	A.reverse()
	X.append([0] + A)

day = 0
while True:
	j = "No"
	check = [0] * N
	for i in range(N):
		x = X[i][-1] - 1
		if x != -1:
			if check[i] == 0 and check[x] == 0 and X[x][-1] == i + 1:
				check[i], check[x] = 1, 1
				X[x].pop(-1)
				X[i].pop(-1)
				j = "Yes"
	day += 1
	if j == "No":
		break

cc = "Yes"
for i in range(N):
	if X[i] != [0]:
		cc = "No"
		break

if cc == "No":
	print(-1)
else:
	print(day - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(sys.stdin.readline())
a_dict = {}
for i in range(N):
  a_dict[i] = [int(a) -1 for a in sys.stdin.readline().split()]

ans = 0
while len(a_dict) > 0:
  flag = False
  entried = []
  for i  in range(N):
    if i in entried or len(entried) == N:continue
    if i in a_dict:
      i2 = a_dict[i][0]
      if a_dict[i2][0] == i and i not in entried and i2 not in entried:
        entried.extend([i,i2])
        del a_dict[i2][0], a_dict[i][0]
        if len(a_dict[i]) == 0: del a_dict[i]
        if len(a_dict[i2]) == 0: del a_dict[i2]
        flag = True
  if flag is False:break
  ans += 1
print(ans if len(a_dict) == 0 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [[0] * (N-1)]+[list(map(int,input().split())) for _ in range(N)]

idx = [0] * (N+1)
cnt = 0
day = 0
flag_max = [False] * (N+1)
while cnt != N:
    
    error = True
    flag =[False] * (N+1)
    looplist = [i for i in range(1,N+1) if not(flag_max[i])]
    
    for i in looplist:
        if (flag[i]):continue
        tmp = A[i][idx[i]]
        if (flag[tmp]):continue
    
        if A[tmp][idx[tmp]] == i:
            idx[tmp] = idx[tmp] + 1
            idx[i] = idx[i] + 1
            if idx[tmp] == N-1:
                flag_max[tmp] = True
                cnt += 1
            if idx[i] == N-1:
                flag_max[i] = True
                cnt += 1
            flag[i] = True
            flag[tmp] = True
            error = False
    if error:
        print(-1)
        sys.exit()
    
    day += 1
            

    if day > 5000:
        print(N*(N-1)//2)
    
    
print(day)