Home » 国际竞赛 » Details

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

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午12:00

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 [? p [i] ?]]  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]