USACO 2020 February Contest, Silver Problem 1. Swapity Swapity Swap 翰林国际教育

USACO 2020 February Contest, Silver Problem 1. Swapity Swapity Swap

Farmer John's $N$ cows ( $1 \leq N \leq 10^{5}$ ) are standing in a line. The $i$ th cow from the left has label $i$ for each $1 \leq i \leq N$ .

Farmer John has come up with a new morning exercise routine for the cows. He has given the cows $M$ pairs of integers $(L_{1}, R_{1}) \dots (L_{M}, R_{M})$ , where $1 \leq M \leq 100$ . He then tells the cows to repeat the following $M$ -step process exactly $K$ ( $1 \leq K \leq 10^{9}$ ) times:

For each i from 1 to M:
- The sequence of cows currently in positions $L_{i} \dots R_{i}$ from the left reverse their order.

After the cows have repeated this process exactly $K$ times, please output the label of the $i$ th cow from the left for each $1 \leq i \leq N$ .

SCORING:

Test case 2 satisfies $N = K = 100$ .
Test cases 3-5 satisfy $K \leq 10^{3}$ .
Test cases 6-10 satisfy no additional constraints.

INPUT FORMAT (file swap.in):

The first line contains $N$ , $M$ , and $K$ . For each $1 \leq i \leq M$ , line $i + 1$ line contains $L_{i}$ and $R_{i}$ , both integers in the range $1 \dots N$ , where $L_{i} < R_{i}$ .

OUTPUT FORMAT (file swap.out):

On the $i$ th line of output, print the $i$ th element of the array after the instruction string has been executed $K$ times.

SAMPLE INPUT:

7 2 2
2 5
3 7

SAMPLE OUTPUT:

Initially, the order of the cows is $[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]$ . After the second step of the process, the order is $[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, Silver Problem 1. Swapity Swapity Swap 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

First simulate the $M$ reversals in $O (N M)$ (or $O (N + M \log N)$ with a lazy balanced binary search tree, but that is outside the scope of silver). After this, let $p [i]$ denote the $i$ -th cow from the right. It suffices to find

p K [i] = p [p [\dots p [i] \dots]]  K times

for every $i$ . To compute this expression for a single index $i$ , first find the minimum positive integer $x$ such that $p^{x} [i] = i$ . We can refer to the sequence

i, p [i], p 2 [i], \dots, p x - 1 [i]

Now it is easy to compute $p^{K} [j] = p^{K (\mod x)} [j]$ for all $j$ located on the cycle in $O (x)$ time.

As every index of the permutation lies on exactly one cycle, the sum of the cycle lengths is equal to $N$ , meaning that this part of the solution runs in $O (N)$ time.

Dhruv Rohatgi's code:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 100000
 
int N,M,K;
int l[100],r[100];
int p[MAXN];
int cc[MAXN];
int pos[MAXN];
vector<int> A[MAXN+1];
int ans[MAXN];
 
int main() {
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
	cin >> N >> M >> K;
	for(int i=0;i<M;i++) {
		cin >> l[i] >> r[i];
		l[i]--,r[i]--;
	}
	for(int i=0;i<N;i++) {
		p[i] = i;
		for(int j=0;j<M;j++)
			if(p[i] >= l[j] && p[i] <= r[j])
				p[i] = r[j] + l[j] - p[i];
	}
	int C = 1;
	for(int i=0;i<N;i++) if(!cc[i]) {
		cc[i] = C;
		A[C].push_back(i);
		int j = p[i];
		if(j != i) pos[j] = 1;
		while(j != i) {
			A[C].push_back(j);
			cc[j] = C;
			if(p[j]!=i) pos[p[j]] = 1 + pos[j];
			j = p[j];
		}
		C++;
	}
	for(int i=0;i<N;i++)
		ans[A[cc[i]][(pos[i] + K)%A[cc[i]].size()]] = i;
	for(int i=0;i<N;i++)
		cout << ans[i]+1 << '\n';
	
}

An alternative approach is to use binary exponentiation. Calculate $p^{2^{k}} [i]$ for each non-negative integer $k$ such that $2^{k} \leq K$ , and then combine the appropriate permutations together to get $p^{K} [k]$ . This approach runs in $O (N \log K)$ 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 m = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());
    int[] to = new int[n];
    {
      int[] l = new int[n];
      for(int i = 0; i < n; i++) l[i] = i;
      while(m-- > 0) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken()) - 1;
        int b = Integer.parseInt(st.nextToken()) - 1;
        while(a < b) {
          int t = l[a];
          l[a] = l[b];
          l[b] = t;
          a++;
          b--;
        }
      }
      for(int i = 0; i < n; i++) to[i] = l[i];
    }
    int[] ret = new int[n];
    for(int i = 0; i < n; i++) ret[i] = i+1;
    while(k > 0) {
      if(k%2 == 1) {
        ret = apply(ret, to);
      }
      k /= 2;
      if(k > 0) to = apply(to, to);
    }
    for(int val: ret) pw.println(val);
    pw.close();
  }
 
  public static int[] apply(int[] l, int[] op) {
    int[] ret = new int[l.length];
    for(int i = 0; i < ret.length; i++) {
      ret[i] = l[op[i]];
    }
    return ret;
  }
}

[/hide]

翰林国际教育

USACO 2020 February Contest, Silver Problem 1. Swapity Swapity Swap