Load Balancing TLE

Problems and Contests
#1

Hello,

I was doing this problem called load balancing. Here was my original code:

#Note that a and b need to be less than the max y and x coord and greater than the min y and x coords.

infile = open('balancing.in', 'r')
lines = infile.readlines()
lines.pop(0)
xCoords = []
yCoords = []
coords = []
for line in lines:
    line = line.split()
    xCoords.append(int(line[0]))
    yCoords.append(int(line[1]))
    coords.append([int(line[0]), int(line[1])])

minXVal = min(xCoords) + 1
maxXVal = max(xCoords) - 1
minYVal = min(yCoords) + 1
maxYVal = max(yCoords) - 1

minList = []
for yCoord in range(minYVal, maxYVal+1, 2): #We loop through all the x lines
    for xCoord in range(minXVal, maxXVal+1, 2): #And the y lines
        quadrants = [0,0,0,0] #Smaller smaller = 0, smaller larger = 1, larger smaller = 2, larger larger = 3
        for coord in coords:
            if coord[0] < xCoord: #Then we just find the corresponding square.
                if coord[1] < yCoord:
                    quadrants[0] += 1
                else:
                    quadrants[1] += 1
            else:
                if coord[1] < yCoord:
                    quadrants[2] += 1
                else:
                    quadrants[3] += 1
        minList.append(max(quadrants))
infile.close()
outFile = open('balancing.out', 'w')
outFile.write(str(min(minList)))
outFile.close()

But then I got TLEs for the last 4 test cases. So I looked at the solution, and coded it like so:

#Note that a and b need to be less than the max y and x coord and greater than the min y and x coords

infile = open('balancing.in', 'r')

lines = infile.readlines()
lines.pop(0)
xCoords = []
yCoords = []
coords = []
for line in lines:
    line = line.split()
    xCoords.append(int(line[0]))
    yCoords.append(int(line[1]))
    coords.append([int(line[0]), int(line[1])])

minXVal = min(xCoords) + 1
maxXVal = max(xCoords) - 1
minYVal = min(yCoords) + 1
maxYVal = max(yCoords) - 1
minList = []
for yCoord in range(maxYVal, minYVal-1, -2): #We loop through all possible x lines
    if yCoord - 1 not in yCoords:
        continue
    for xCoord in range(maxXVal, minXVal+1, -2):
        if xCoord - 1 not in xCoords:
           continue
        quadrants = [0,0,0,0] #Smaller smaller = 0, smaller larger = 1, larger smaller = 2, larger larger = 3
        for coord in coords:
            if coord[0] < xCoord:
                if coord[1] < yCoord:
                    quadrants[0] += 1
                else:
                    quadrants[1] += 1
            else:
                if coord[1] < yCoord:
                    quadrants[2] += 1
                else:
                    quadrants[3] += 1
        minList.append(max(quadrants))
infile.close()
outFile = open('balancing.out', 'w')
outFile.write(str(min(minList)))
outFile.close()

.
But I still got TLEs for the last 3 cases. Am I doing something wrong?

Thanks,
~Zanderman

#2

Yeah… the constant factor for Python is really, really large. It might do you well to switch to another language like Java or C++. (It’s a pain, I know, but it’ll do you well in the long run)

#3

Ah, so there’s no better way :(. I plan to swtich to cpp (because so many resources for cp are in it), but I won’t do it until after bronze feb (so this weekend) because I want to be comfortable in the language I’m using.

Well, thanks anyway!

1 Like
#4

Don’t worry. I think the majority of silver problems are still solvable using Python.

#5

You are looping through all possible x and y coordinates for the fences, but you only need to check the ones right next to a cow. As the solution says,

This means that we only need to place vertical fences where x=a and there is a cow with x-coordinate a−1, and we only need to place vertical fences where y=b and there is a cow with y-coordinate b−1.

If you do this instead of checking all possible coordinates, your code shouldn’t TLE.

#6

But isn’t that what my second code is doing? Unless I misunderstood the official solution’s algorithm…

#7

Yeah… on second though, your solution is actually too slow. You’re going through all the possible y-values, which can be up to 10^9, so instead of doing that, just go through all the cows instead.

#8

You are looping through all the possible x-coordinates and y-coordinates (every even coordinate from maxYVal to minYVal-1 and same for the x-coordinates). Instead, you should be going through the coordinates of the cows (xCoords and yCoords).