2020 Feb USACO Bronze (Swapity Swap)

Problems and Contests
#1

Hi! This is my code for the Swapity Swap question with python.

import sys
sys.stdin = open('swap.in', 'r')
sys.stdout = open('swap.out', 'w')

N, K = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())

original = [j for j in range(1, N+1)]
cow_numbering = [i for i in range(1, N+1)]

same = False
count = 0
while not same:
    cow_numbering[A1 - 1: A2] = cow_numbering[A2 - 1: A1 - 2: -1]
    cow_numbering[B1 - 1: B2] = cow_numbering[B2 - 1: B1 - 2: -1]
    count += 1
    if cow_numbering == original:
        same = True

for j in range(K % count):
    cow_numbering[A1-1: A2] = cow_numbering[A2-1: A1-2: -1]
    cow_numbering[B1-1: B2] = cow_numbering[B2-1: B1-2: -1]
for i in cow_numbering:
    print(i)

Turns out that this works for 9/13 test cases (misses 5,6,9,11) due to time error. Obviously based on the constraints described in the problem, these time errors don’t occur due to the actual values being too much.

Can someone tell me the reason for this and tell me how to fix it?

#2

Could you please format your code first?

#4

Where do you change count? That might be the reason why your code’s TLE-ing.

#5

No thats a copying mistake. I fixed it

#6

Are you sure your slicing is correct? (cow_numbering[A2 - 1: A1 - 2: -1] seems a tiny bit weird to me…)

#7

Well, its working for most of the test cases. It makes sense because both A1 and A2 are inputted as one more than what the index must be. Also, since we are decrementing, it becomes A1-2 as it doesn’t include A1-2.

Maybe there are some test cases that don’t work with that? That’s what I am confused about. Which ones don’t work? And how do I fix it?

#8

What if A1 is 1?

#9

If you read the analysis you’ll see that this solution is O(NS) where S goes up to 29640. 29640 * 100 = 3e6 operations, which might be too slow for Python.

Try the other O(N^2) algorithm? Or O(N) if you use the solution from the silver version.