📑 Qualification Round 2020

Task 1. Vestigium

📓 Variant 1. Python Only

T = int(input())
for t in range(T): 
    N = int(input())
    k, r, c = 0, 0, 0
    M = []
    for i in range(N):
        R = input()
        M.append([int(s) for s in R.split()])
        if len((set(M[i]))) < N: r += 1
        for j in range(N):
            if i == j: k += M[i][j]
            if i == N-1: 
                C = [M[i][j] for i in range(N)]
                if len((set(C))) < N: c += 1
    print('Case #%d: %d %d %d' % ((t+1, k, r, c)))

📓 Variant 1. SageMath Interactive

📓 Variant 2. Python Only

def check_list(arr):
    vis=set()
    out=0
    for x in arr:
        if x not in vis:
            vis.add(x)
        else: 
            out=1
            break 
    return out
T=int(input())
for t in range(T): 
    N=int(input())
    k,r,c=0,0,0
    M=[]
    for i in range(N):
        I=input().split()
        M.append([int(i) for i in I])
        r+=check_list(M[i])
        for j in range(N):
            if i==j:
                k+=M[i][j]
            if i==N-1: 
                c+=check_list([M[i][j] for i in range(N)])
    print('Case #%d: %d %d %d'%((t+1,k,r,c)))

📓 Variant 2. SageMath Interactive

Task 2. Nesting Depth

📓 Variant 1. Python Only

T = int(input())
for t in range(T): 
    S = str(input())
    N = [int(n) for n in S]
#    print(N)
    R = N[0] * '(' + str(N[0])
    for i in range(1,len(N)):
        if (N[i - 1] < N[i]):
            nopen = N[i] - N[i - 1]
 #           print('o'+str(nopen))
            R += nopen * '(' + str(N[i])
        elif N[i - 1] > N[i]:
            nclose = (N[i - 1] - N[i])
            R += nclose * ')' + str(N[i])
 #           print('c'+str(nclose))
        else:
            R += str(N[i])
    R += N[-1] * ')' 
    print('Case #%d: %s' % ((t + 1, R)))

📓 Variant 1. SageMath Interactive

📓 Variant 2. Python Only

def gen_str(s):
    s0=int(s[0])
    yield s0*'('+s[0]
    while s[:-1]:
        s=s[1:]
        s1=int(s[0])
        c=s1>s0
        yield c*(s1-s0)*'('+(not c)*(s0-s1)*')'+s[0]
        s0=s1
    yield s0*')'
T=int(input())
for t in range(T):
    S=input()
    print('Case #%d: %s'%((t+1,''.join(gen_str(S)))))

📓 Variant 2. SageMath Interactive

Task 3. Parenting Partnering Returns

📓 Variant 1. Python Only

T=int(input())
for t in range(T): 
    N=int(input())
    I=[input() for i in range(N)]
    ANS=N*'O'
    A=sorted([list(map(int,I[i].split()))+[i] 
              for i in range(N)])
#    print(A)
    endC,endJ=0,0
    for a in A:
 #       print(a[0],a[1],a[2])
        if endC<=a[0]:
            ANS=ANS[:a[2]]+'C'+ANS[a[2]+1:]
            endC=a[1]
        elif endJ<=a[0]:
            ANS=ANS[:a[2]]+'J'+ANS[a[2]+1:]
            endJ=a[1]
        else:
            ANS='IMPOSSIBLE'
            break
    print('Case #{}: {}'.format(t+1,ANS))

📓 Variant 1. SageMath Interactive

Task 4. ESAb ATAd

📓 Process Simulation

📓 Variant 1. Python Only

def query(string):
    print(string,flush=True)
    return input()    
def update_by_pairs(i,b,inrow,complement,reverse):
    answer1=query(str(i+1))
    answer2=query(str(b-i))
    if (complement==None and answer1==answer2):
        complement=i
    if (reverse==None and answer1!=answer2):
        reverse=i
    inrow=inrow[:i]+answer1+inrow[i+1:b-i-1]+answer2+inrow[b-i:]
    return inrow,complement,reverse
def is_complemented(string,complement):
    if (complement==None):
        query('1')
    else:
        if string[complement]!=query(str(complement+1)):
            string=string.replace('0','*')\
            .replace('1','0').replace('*','1')
    return string
def is_reversed(string,reverse):
    if (reverse==None):
        query('1')
    else:
        if string[reverse]!=query(str(reverse+1)):
            string=string[::-1]
    return string
t,b=map(int,input().split())
for case in range(t):
    inrow,start,complement,reverse=b*'?',5,None,None
    for i in range(start):
        inrow,complement,reverse=\
        update_by_pairs(i,b,inrow,complement,reverse)
    while ('?' in inrow and start < b//2):
        if start%4==1:
            inrow=is_complemented(inrow,complement)
            inrow=is_reversed(inrow,reverse)
        inrow,complement,reverse=\
        update_by_pairs(start,b,inrow,complement,reverse)
        start+=1
    answer=query(inrow)
    if answer!='Y':  
        exit()

📓 Variant 2. Python Only

class QuantumString:
    def __init__(self,length):
        self.B=length
        self.R=length*'?'
        self.Q=''
        self.count=0
        self.start=5
        self.complement=None
        self.reverse=None
    def query(self):
        print(self.Q,flush=True)
        self.count+=1
        return input()    
    def update_by_pairs(self,i):
        self.Q=str(i+1); b1=self.query()
        self.Q=str(self.B-i); b2=self.query()
        if (self.complement==None and b1==b2):
            self.complement=i
        if (self.reverse==None and b1!=b2):
            self.reverse=i
        self.R=self.R[:i]+b1+self.R[i+1:self.B-i-1]+\
               b2+self.R[self.B-i:]
    def is_complemented(self):
        if (self.complement==None):
            self.Q='1'; self.query()
        else:
            self.Q=str(self.complement+1)
            if self.R[self.complement]!=self.query():
                self.R=self.R.replace('0','*')\
                           .replace('1','0').replace('*','1')
    def is_reversed(self):
        if (self.reverse==None):
            self.Q='1'; self.query()
        else:
            self.Q=str(self.reverse+1)
            if self.R[self.reverse]!=self.query():
                self.R=self.R[::-1]
    def find_string(self):
        for i in range(self.start):
            self.update_by_pairs(i)
        while ('?' in self.R and self.start < self.B//2):
            if self.start%4==1:
                self.is_complemented()
                self.is_reversed()
            self.update_by_pairs(self.start)
            self.start+=1
        print(self.R,flush=True)
        if input()!='Y':
            exit()
t,b=map(int,input().split())
for case in range(t):
    QS=QuantumString(b)
    QS.find_string()

📓 Variant 1. SageMath Interactive

Task 5. Indicium

📓 Process Simulation

📓 Variant 1. Python Only

#7pts, TLE for the last ✓
def display_matrix(M):
    MS=''
    for i in range(len(M)):
        MS+=' '.join([str(r) for r in M[i]])+'\n'
    print(MS)
def trace(arr):
    arr_trace,i=0,0
    for row in arr:
        arr_trace+=row[i]
        i+=1
    return arr_trace
def gen_permutations(arr):
    if len(arr)<=1: yield arr
    else:
        for p in gen_permutations(arr[1:]):
            for i in range(len(arr)):
                yield p[:i]+arr[0:1]+p[i:]     
def find_matrix0(N,S):
    baseN=S//N
    baseR=list(range(1,N+1))
    baseR=baseR[baseN-1:]+baseR[:baseN-1]
    return [baseR[i:]+baseR[:i] for i in range(N,0,-1)]
def find_matrix_gen(N,S):
    row=list(range(1,N+1))
    row_gen=gen_permutations(row)
    flag,result=False,[]
    for row in row_gen:
        matrix=[[row[j%len(row)] 
                 for j in range(i,i+len(row))] 
                for i in range(len(row))]
        matrix_gen=gen_permutations(matrix)
        for rows in matrix_gen:
            if trace(rows)==S:
                flag=True
                result=rows
                break
        if flag:
            break
    return result
def find_matrix1(N,S):
    matrix=[]
    cols={i:list(range(1,N+1)) for i in range(N)}
    if S==N*N-2:
        base=[N,N-1]+list(range(1,N-1))
        r1=[N-1]+list(range(2,N-2))+[N,N-2,1]
        r2=[k+2 if k%2==0 else k for k in range(N-3)]+[N-2,N-1,N]
    elif S==N+2:
        base=list(range(1,N+1))
        r1=[2,4]+list(range(5,N))+[1,N,3]
        r2=[4,3]+[k+2 if k%2==0 else k for k in range(4,N-1)]+[N,2,1]
    elif S==(N-2)*3+4:
        base=[3,2,1,4]+list(range(5,N+1))
        r1=[2,4]+list(range(5,N))+[3,N,1]
        r2=[4,1]+[k+2 if k%2==0 else k for k in range(4,N-1)]+[N,2,3]
    for i in range(N-3):
        row=base[N-i:]+base[:N-i]
        matrix.append(row)
    matrix.append(r1)
    matrix.append(r2)
    for row in matrix:
        for k in range(N):
            cols[k].remove(row[k])
    matrix.append([cols[k][0] for k in range(N)])
    return matrix
def find_matrix2(N,S):
    if S==N+2:
        base=list(range(1,N+1))
    elif S==N*N-2:
        base=list(range(N,0,-1))
    elif S==(N-2)*3+4:
        base=[3,2,1,4]+list(range(5,N+1))
    matrix=[base]
    for i in range(1,N):
        if i%2==1:
            base,row=matrix[i-1],[]
            for j in range(N//2):
                row+=[base[2*j+1],base[2*j]]
            matrix.append(row)
        else:
            matrix.append(base[-2:]+base[:-2])
    return matrix[:N-2]+[matrix[N-1],matrix[N-2]]  
T=int(input())
for t in range(T): 
    N,K=map(int,input().split())
    cond2=(N==2) and (K==3)
    cond3=(N==3) and (K in [4,5,7,8])
    cond4=(N>3) and (K in [N+1,N*N-1])
    cond=cond2 or cond3 or cond4
    if cond:
        print('Case #{}: IMPOSSIBLE'.format(t+1))
    else:
        if K%N==0:
            M=find_matrix0(N,K)
        elif K not in [N+2,N*N-2,(N-2)*3+4]:
            M=find_matrix_gen(N,K)
        else:
            if K%2==1:
                M=find_matrix1(N,K)
            else:
                M=find_matrix2(N,K)
        print('Case #{}: POSSIBLE'.format(t+1))
        display_matrix(M)

📓 Variant 2. Python Only

def display_matrix(M):
    MS=''
    for i in range(len(M)):
        MS+=' '.join([str(r) for r in M[i]])+'\n'
    print(MS)
def find_matrix0(N,S):
    baseN=S//N
    baseR=list(range(1,N+1))
    baseR=baseR[baseN-1:]+baseR[:baseN-1]
    return [baseR[i:]+baseR[:i] for i in range(N,0,-1)]
def gen_xyz(N,K):
    min_x=max(1,(K-2*N)//(N-2))
    max_x=min(N,(K-2)//(N-2))
    for x in range(min_x,max_x+1):
        for y in range(1,N+1):
            for z in range(1,N+1):
                if (N-2)*x+y+z==K and (x==y) is (x==z):
                        return [x,y,z]
def find_matrix(N,K):
    X,Y,Z=gen_xyz(N,K)
    M=[i*[0]+[X]+(N-i-1)*[0] for i in range(N-2)]
    M+=[(N-2)*[0]+[Y,X]]
    M+=[(N-2)*[0]+[X,Z]]
    col_set={i:{X} for i in range(N-2)}
    col_set[N-2]={X,Y}; col_set[N-1]={X,Z}
    base=[X,Y,Z]
    base+=list(set(range(1,N+1))-set(base))
    for b in base:
        for r in range(N):
            if b not in M[r]:
                for c in [i%N for i in range(r,r+N)]:
                    if M[r][c]==0 and b not in col_set[c]:
                        M[r]=M[r][:c]+[b]+M[r][c+1:]
                        col_set[c].add(b)
                        break
    return M
T=int(input())
for t in range(T): 
    N,K=map(int,input().split())
    cond2=(N==2) and (K==3)
    cond3=(N==3) and (K in [4,5,7,8])
    cond4=(N>3) and (K in [N+1,N*N-1])
    cond=cond2 or cond3 or cond4
    if cond:
        print('Case #{}: IMPOSSIBLE'.format(t+1))
    else:
        if K%N==0:
            M=find_matrix0(N,K)
        else:
            M=find_matrix(N,K)
        print('Case #{}: POSSIBLE'.format(t+1))
        display_matrix(M)

📓 Variant 2. SageMath Interactive

📓 Variant 3. Python Only

class MGraph:
    def __init__(self,case,num,diag_sum):
        self.T=case+1
        self.N=num
        self.S=diag_sum
        self.M={i:num*[0] for i in range(num)}
        self.D=num*[0]
        self.XYZ=3*[0]
        cond1=(num==2) and (diag_sum==3)
        cond2=(num==3) and (diag_sum in [4,5,7,8])
        cond3=(num>3) and (diag_sum in [num+1,num**2-1])
        self.C=cond1 or cond2 or cond3
    def find_diagonal(self):
        if not self.C:
            if not self.S%self.N:
                self.D=self.N*[self.S//self.N]
            else:
                min_x=max(1,(self.S-2*self.N)//(self.N-2))
                max_x=min(self.N,(self.S-2)//(self.N-2))
                for x in range(min_x,max_x+1):
                    for y in range(1,self.N+1):
                        for z in range(1,self.N+1):
                            if (self.N-2)*x+y+z==self.S \
                            and (x==y) is (x==z):
                                self.D=(self.N-2)*[x]+[y,z]
                                self.XYZ=[x,y,z]
    def latin_square(self,prefix='Case #%d: '):
        if self.C: 
            print(prefix%self.T+'IMPOSSIBLE')
        else:
            if not self.S%self.N:
                base=list(range(1,self.N+1))
                base=base[self.S//self.N-1:]+base[:self.S//self.N-1]
                for i in range(self.N):
                    self.M[i]=base[self.N-i:]+base[:self.N-i]
            else:
                for i in range(self.N-2):
                    self.M[i]=i*[0]+[self.XYZ[0]]+(self.N-i-1)*[0]
                self.M[self.N-2]=(self.N-2)*[0]+[self.XYZ[1],self.XYZ[0]]
                self.M[self.N-1]=(self.N-2)*[0]+[self.XYZ[0],self.XYZ[2]]
                col_set={i:{self.XYZ[0]} for i in range(self.N-2)}
                col_set[self.N-2]={self.XYZ[0],self.XYZ[1]}
                col_set[self.N-1]={self.XYZ[0],self.XYZ[2]}
                base=self.XYZ
                base+=list(set(range(1,self.N+1))-set(base))
                for b in base:
                    for r in range(self.N):
                        if b not in self.M[r]:
                            for c in [i%self.N for i in range(r,r+self.N)]:
                                if self.M[r][c]==0 and b not in col_set[c]:
                                    self.M[r]=self.M[r][:c]+[b]+self.M[r][c+1:]
                                    col_set[c].add(b)
                                    break
            print(prefix%self.T+'POSSIBLE')
            str_matrix=''
            for i in range(self.N):
                str_row=[str(m) for m in self.M[i]]
                str_matrix+=' '.join(str_row)+'\n'
            print(str_matrix)
T=int(input())
for case in range(T): 
    num,diag_sum=map(int,input().split())
    mg=MGraph(case,num,diag_sum)
    mg.find_diagonal()
    mg.latin_square()

📓 Variant 3. SageMath Interactive