ABC188 C Problem ABC Tournament

one thing

I got an incorrect answer with tle because I used remove () in the list. From the C problem, I want to be aware of the computational complexity order.

Correct code

N=int(input())
A=list(map(int,input().split()))
survive=list(range(1,2**N+1))

    
for j in range(N-1):
    winner=[]
    for k in range(0, len(survive), 2):
        first=survive[k]
        second=survive[k+1]
        if A[first-1]>A[second-1]:
            winner.append(first)
        else:
            winner.append(second)
    survive=winner
    
first=survive[0]
second=survive[1]
if A[first-1]>A[second-1]:
    print(second)
else:
    print(first)

Commentary

First, make a list that contains data for everyone. From there, you can remove the losers in the tournament from the list and output the number of the remaining two with the lower rate. There are two ways to create a list that deletes the data of the loser. You can either make a list that contains rate data or a list that contains number data.

In the former case, the data to be output is a number, but the remaining data is the rate, so it is necessary to set aside a list that stores the rates in numerical order and check the rate index, which is troublesome. In the latter case, it is only necessary to output the remaining numbers as they are, so we will create a list that stores the number data.

The way to remove the loser's number from the list is to simply use remove () to shift the index of the data by the amount of the disappearance and it is troublesome, so store the number of the remaining person. Create an empty winner list and add only the winners from the survive list to the winner list. When the process is completed, set survive = winner. Implement by repeating this.

This method works well when you want to delete an element that meets a specific condition from the list and the index is involved in the condition to be deleted.

Simple analogy

Output list A = [2,3,1,5,6,7,3] with odd-numbered elements removed.

Answer

A=[2,3,1,5,6,7,3]
ans=[]
for i in range(len(A)):
    if i%2==0:
        ans.append(A[i])
print(ans)
#The answer is[2,1,6,3]Should be.

Summary

・ When there are two possible mounting methods, simulate to some extent and select the easier one. ・ If you want to delete an element that meets a specific condition from the list and the index is involved in the condition to be deleted, prepare an empty list and put the surviving element in it.

ABC188 C problem with python3