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

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

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

Farmer John has come up with a new morning exercise routine for the cows. He has given the cows MM pairs of integers (L1,R1)(LM,RM)(L1,R1)…(LM,RM), where 1M1001≤M≤100. He then tells the cows to repeat the following MM-step process exactly KK (1K1091≤K≤109) times:

 

  • For each ii from 11 to MM:
    • The sequence of cows currently in positions LiRiLi…Ri from the left reverse their order.

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

 

SCORING:

  • Test case 2 satisfies N=K=100N=K=100.
  • Test cases 3-5 satisfy K103K≤103.
  • Test cases 6-10 satisfy no additional constraints.

 

INPUT FORMAT (file swap.in):

The first line contains NNMM, and KK. For each 1iM1≤i≤M, line i+1i+1 line contains LiLi and RiRi, both integers in the range 1N1…N, where Li<RiLi<Ri.

 

OUTPUT FORMAT (file swap.out):

On the iith line of output, print the iith element of the array after the instruction string has been executed KK times.

 

SAMPLE INPUT:

7 2 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, Silver Problem 1. Swapity Swapity Swap 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Benjamin Qi)

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

pK[i]=p[p[p[i]]]K timespK[i]=p[p[⋯p[i]⋯]]⏞K times

for every ii. To compute this expression for a single index ii, first find the minimum positive integer xx such that px[i]=ipx[i]=i. We can refer to the sequence

i,p[i],p2[i],,px1[i]i,p[i],p2[i],…,px−1[i]

Now it is easy to compute pK[j]=pK(modx)[j]pK[j]=pK(modx)[j] for all jj located on the cycle in O(x)O(x) time.

As every index of the permutation lies on exactly one cycle, the sum of the cycle lengths is equal to NN, meaning that this part of the solution runs in O(N)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 p2k[i]p2k[i] for each non-negative integer kk such that 2kK2k≤K, and then combine the appropriate permutations together to get pK[k]pK[k]. This approach runs in O(NlogK)O(Nlog⁡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]

翰林国际教育资讯二维码