[SOLVED] How to improve efficiency of appending to and then checking for subsequent elements in list

Issue

i’m attempting to solve:
http://orac.amt.edu.au/cgi-bin/train/problem.pl?problemid=980&set=aio17int

The algorithm exceeds the time limit for larger files. I’m fairly new to python, and can’t find a more efficient solution online for checking if an element is in a list and then appending accordingly. Please help improve the speed without using any imports. Thank you.

input file:

8 5
2 7
1 8
8 4
7 5
8 6
re = 1
bl = 1
red = [1]
blue = [2]
input_file = open("tagin.txt","r")
n, m = map(int, input_file.readline().split())
for i in range(m):
    a, b = map(int, input_file.readline().split())
    if a in red:
        red.append(b)
        re+=1
    elif a in blue:
        blue.append(b)
        bl+=1

output_file = open("tagout.txt", "w")
output_file.write(str(re) + " " + str(bl))
output_file.close()

output file:

4 3

Also please advise if stack overflow is the wrong platform to ask this question, if so what should I use?

Solution

Some things you can improve:

  • Use a set instead of a list for collecting team members. That will increase the efficiency of the in operator.

  • There is no need to keep track of the size of the team, as you can get that with the len function

  • Only collect the members of one team. We can derive the size of the other team from m, which represents how many people get tagged. If we add 2 to that, we also take into account the first two which are already tagged. Subtract from that the size of one team, and you get the size of the other.

Code:

input_file = open("tagin.txt","r")
n, m = map(int, input_file.readline().split())
red = {1}  # A set, only for the red team
for i in range(m):
    a, b = map(int, input_file.readline().split())
    if a in red:  # Better efficiency as red is now a set
        red.add(b)

output_file = open("tagout.txt", "w")
# Size of blue team can be deduced from what we already know:
output_file.write(str(len(red)) + " " + str(m + 2 - len(red)))
output_file.close()

Answered By – trincot

Answer Checked By – Terry (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *