Codeforces Round 967 (DIV 2.) C, code debugging

Revision en1, by logankeede, 2024-08-20 21:38:02

I have already seen the tutorial and solved this question 2001C - Guess The Tree but I am still curious about what I did wrong in my original approach 277413780 because I feel that approach is correct, so if you can let me know my fault in approach or implementation, I will be grateful.

Thank You.

import sys
print = sys.stdout.write


t = int(input())
for i in range(t):
    n = int(input())
    child = []
    stack = []
    dic= [[0]*(n+1) for i in range(n+1)]
    for i in range(2,n+1):
        print(f"? {1} {i}\n")
        sys.stdout.flush()
        ans = int(input())
        if ans ==1:
            child.append((1,i))
        else:
            stack.append((1,ans,i))
        dic[i][1] = 1
        dic[1][i] = 1
    while stack:
        k = stack.pop()
        if dic[k[0]][k[1]] == 0 :
            print(f"? {k[0]} {k[1]}\n")
            sys.stdout.flush()
            ans = int(input())
            if ans == k[0]:
                child.append((k[0], k[1]))
            else:
                stack.append((k[0], ans, k[1]))
            dic[k[0]][k[1]] = 1
            dic[k[1]][k[0]] = 1
        if dic[k[2]][k[1]] == 0:
            print(f"? {k[1]} {k[2]}\n")
            sys.stdout.flush()
            ans = int(input())
            if ans == k[1]:
                child.append((k[1], k[2]))
            else:
                stack.append((k[1], ans, k[2]))
            dic[k[2]][k[1]] = 1
            dic[k[1]][k[2]] = 1
    print("! ")
    sys.stdout.flush()
    for a,b in child:
        print(f"{a} {b} ")
        sys.stdout.flush()
    print("\n")
    sys.stdout.flush()

Explaination:

dic matrix keeps track of what queries have already been made.

child keeps track of edges that have been found (some what misleading I know *_*).

stack keeps track of what queries have been made and their answer in format (a, answer, b) (if a and b are queries) and in turn what new queries need to be made.

the key difference from tutorial is after initial queries from 1 to {2 3 .... n} nodes I explore both sides of an answered query until I get an edge and keep track of it using dic and stack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English logankeede 2024-08-20 21:38:02 2257 Initial revision (published)