USACO 2020 February Contest, Bronze Problem 3. Swapity Swap

USACO 2020 February Contest, Bronze Problem 3. Swapity Swap

Farmer John's NN cows (1≤N≤1001≤N≤100) are standing in a line. The iith cow from the left has label ii, for each 1≤i≤N1≤i≤N.

Farmer John has come up with a new morning exercise routine for the cows. He tells them to repeat the following two-step process exactly KK (1≤K≤1091≤K≤109) times:

 

1. The sequence of cows currently in positions A1…A2A1…A2 from the left reverse their order (1≤A1<A2≤N1≤A1<A2≤N).
2. Then, the sequence of cows currently in positions B1…B2B1…B2 from the left reverse their order (1≤B1<B2≤N1≤B1<B2≤N).

After the cows have repeated this process exactly KK times, please output the label of the iith cow from the left for each 1≤i≤N1≤i≤N.

 

 

 

 

SAMPLE INPUT:

7 2
2 5
3 7

SAMPLE OUTPUT:

1
2
4
3
5
7
6

Initially, the order of the cows is [1,2,3,4,5,6,7][1,2,3,4,5,6,7] from left to right. After the first step of the process, the order is [1,5,4,3,2,6,7].[1,5,4,3,2,6,7]. After the second step of the process, the order is [1,5,7,6,2,3,4][1,5,7,6,2,3,4]. Repeating both steps a second time yields the output of the sample.

 

Problem credits: Brian Dean

 USACO 2020 February Contest, Bronze Problem 3. Swapity Swap 题解(雷竞技raybet安卓版下载 提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

For full credit, we need to do better than just simulating the KK processes individually.

For each ii compute the minimum positive integer XX such that after XX repetitions of the process, the cow with label ii is again the cow that is ii-th from the left. Then, for that cow, we can consider the remainder when KK is divided by XX rather than KK itself. As the remainder is always less than NN, this runs in O(N2)O(N2). See the silver analysis for how to do it in O(N)O(N).

 

#include "bits/stdc++.h"
 
using namespace std;
 
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
 
int N,K,A1,A2,B1,B2,res[101];
 
int nex(int x) {
	if (A1 <= x && x <= A2) x = A1+A2-x;
	if (B1 <= x && x <= B2) x = B1+B2-x;
	return x;
}
 
int main() {
	setIO("swap");
	cin >> N >> K >> A1 >> A2 >> B1 >> B2;
	for (int i = 1; i <= N; ++i) {
		int p = 1, cur = nex(i);
		while (cur != i) {
			p ++;
			cur = nex(cur);
		}
		int k = K%p;
		for (int j = 0; j < k; ++j) cur = nex(cur);
		res[cur] = i; // position of cow i after k steps is cur
	}
	for (int i = 1; i <= N; ++i) cout << res[i] << "\n";
}

Alternatively, we can just hope that the permutation returns to its original state quickly. If it repeats after SS steps, then it suffices to simulate only K(modS)K(modS) steps. It can be verified (by exhaustive search) that the maximum possible value of SS for N≤100N≤100 is 2964029640 for A=(1,94)A=(1,94) and B=(2,98)B=(2,98). Thus, the bounds were small enough to allow a solution that runs in O(NS)O(NS) time to run in time.

Nick Wu's code:

 

import java.io.*;
import java.util.*;
public class Solution {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("swap.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("swap.out")));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());
    int a1 = Integer.parseInt(st.nextToken())-1;
    int a2 = Integer.parseInt(st.nextToken())-1;
    st = new StringTokenizer(br.readLine());
    int b1 = Integer.parseInt(st.nextToken())-1;
    int b2 = Integer.parseInt(st.nextToken())-1;
    int cycleSize = 0;
    int[] l = new int[n];
    for(int i = 0; i < n; i++) l[i] = i;
    boolean sorted = true;
    do {
      cycleSize++;
      reverse(l, a1, a2);
      reverse(l, b1, b2);
      sorted = true;
      for(int i = 0; sorted && i < n; i++) sorted = l[i] == i;
    }
    while(!sorted);
    k %= cycleSize;
    for(int i = 0; i < n; i++) l[i] = i+1;
    for(int i = 0; i < k; i++) {
      reverse(l, a1, a2);
      reverse(l, b1, b2);
    }
    for(int val: l) pw.println(val);
    pw.close();
  }
  private static void reverse(int[] l, int a, int b) {
    while(a < b) {
      int t = l[a];
      l[a] = l[b];
      l[b] = t;
      a++;
      b--;
    }
  }
}