USACO 2020 February Contest Bronze Division - Swapity Swap

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The period (the amount of moves required until we return to the same state) of the algorithm is pretty small so we can simulate the moves and find the position of the current move on this period.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ifstream cin("swap.in");
    ofstream cout("swap.out");

    int n, k;
    cin >> n >> k;

    int L1, L2, R1, R2;
    cin >> L1 >> R1;
    cin >> L2 >> R2;

    L1--, R1--, L2--, R2--;

    vector<int> v(n);
    for(int i = 0; i < n; i++)
        v[i] = i+1;

    vector<int> v2 = v;

    // here i kept the vectors
    vector<vector<int> > states;

    states.push_back(v2);

    // while i didn't get back to the original state
    while(1)
    {
        // do the operations, the period is small
        reverse(v2.begin() + L1, v2.begin() + R1 + 1);
        reverse(v2.begin() + L2, v2.begin() + R2 + 1);
        if(v2 == states[0])
            break;
        else
            states.push_back(v2);
    }

    int len = states.size();

    // print the right vector
    vector<int> ans = states[k % len];
    for(auto x : ans)
        cout << x << '\n';
    return 0;
}

with open("swap.in", "r") as fin:
    tokens = fin.read().split()
n = int(tokens[0])
k = int(tokens[1])
L1 = int(tokens[2]) - 1
R1 = int(tokens[3]) - 1
L2 = int(tokens[4]) - 1
R2 = int(tokens[5]) - 1
v = list(range(1, n+1))
v2 = v[:]
states = [v2[:]]
while True:
    v2[L1:R1+1] = list(reversed(v2[L1:R1+1]))
    v2[L2:R2+1] = list(reversed(v2[L2:R2+1]))
    if v2 == states[0]:
        break
    else:
        states.append(v2[:])
length = len(states)
ans = states[k % length]
with open("swap.out", "w") as fout:
    for x in ans:
        fout.write(str(x) + "\n")