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.pop(0)
xCoords = []
yCoords = []
coords = []
for line in lines:
line = line.split()
xCoords.append(int(line))
yCoords.append(int(line))
coords.append([int(line), int(line)])

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 < xCoord: #Then we just find the corresponding square.
if coord < yCoord:
else:
else:
if coord < yCoord:
else:
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.pop(0)
xCoords = []
yCoords = []
coords = []
for line in lines:
line = line.split()
xCoords.append(int(line))
yCoords.append(int(line))
coords.append([int(line), int(line)])

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 < xCoord:
if coord < yCoord:
else:
else:
if coord < yCoord:
else:
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

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)

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

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

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.

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

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.

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`).