Home » 国际竞赛 » Details

USACO 2021 January Contest, Gold Problem 3. Dance Mooves

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

USACO 2021 January Contest, Gold Problem 3. Dance Mooves

Farmer John’s cows are showing off their new dance mooves!

At first, all $N$ cows ( $2 \leq N \leq 10^{5}$ ) stand in a line with cow $i$ in the $i$ th position in line. The sequence of dance mooves is given by $K$ ( $1 \leq K \leq 2 \cdot 10^{5}$ ) pairs of positions $(a_{1}, b_{1}), (a_{2}, b_{2}), \dots, (a_{K}, b_{K})$ . In each minute $i = 1 \dots K$ of the dance, the cows in positions $a_{i}$ and $b_{i}$ in line swap. The same $K$ swaps happen again in minutes $K + 1 \dots 2 K$ , again in minutes $2 K + 1 \dots 3 K$ , and so on, continuing in a cyclic fashion for a total of $M$ minutes ( $1 \leq M \leq 10^{18}$ ). In other words,

In minute $1$ , the cows at positions $a_{1}$ and $b_{1}$ swap.
In minute $2$ , the cows at positions $a_{2}$ and $b_{2}$ swap.
...
In minute $K$ , the cows in positions $a_{K}$ and $b_{K}$ swap.
In minute $K + 1$ , the cows in positions $a_{1}$ and $b_{1}$ swap.
In minute $K + 2$ , the cows in positions $a_{2}$ and $b_{2}$ swap.
and so on ...

For each cow, please determine the number of unique positions in the line she will ever occupy.

Note: the time limit per test case on this problem is twice the default.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains integers $N$ , $K$ , and $M$ . Each of the next $K$ lines contains $(a_{1}, b_{1}) \dots (a_{K}, b_{K})$ ( $1 \leq a_{i} < b_{i} \leq N$ ).

OUTPUT FORMAT (print output to the terminal / stdout):

Print $N$ lines of output, where the $i$ th line contains the number of unique positions that cow $i$ reaches.

SAMPLE INPUT:

SAMPLE OUTPUT:

After $7$ minutes, the cows in increasing order of position are $[3, 4, 5, 2, 1, 6]$ .

Cow $1$ reaches positions ${1, 2, 3, 4, 5}$ .
Cow $2$ reaches positions ${1, 2, 3, 4}$ .
Cow $3$ reaches positions ${1, 2, 3}$ .
Cow $4$ reaches positions ${2, 3, 4}$ .
Cow $5$ reaches positions ${3, 4, 5}$ .
Cow $6$ never moves, so she never leaves position $6$ .

SCORING:

Test cases 1-5 satisfy $N \leq 100, K \leq 200$ .
Test cases 6-10 satisfy $M = 10^{18}$ .
Test cases 11-20 satisfy no additional constraints.

Problem credits: Chris Zhang

USACO 2021 January Contest, Gold Problem 3. Dance Mooves 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Chris Zhang)

For the first subtask, we can just simulate. At most $N K$ minutes will suffice because the sequence of positions of an individual cow will start repeating within that time. For the second subtask, see the silver analysis.

For full credit, let's again construct $s_{i}$ and $p_{i}$ as described in the Silver analysis, and consider the contribution of each disjoint cycle independently.

Let $D = ⌊ M / K ⌋$ and $R$ be the remainder when $M$ is divided by $K$ . There will first occur $D$ full iterations of $K$ swaps, followed by $R$ extra swaps. For simplicity, let’s ignore $R$ for now. To solve for the answer of cow $i$ , which is in some cycle of length $L$ : if $D$ is at least $L$ , the answer is the size of the union of all sets $s_{i}$ in this cycle (as in the silver analysis). But if $D$ is less than $L$ , it will be the size of the union of the $D$ sets $s_{i}, s_{p_{i}}, s_{p_{i}^{2}}, \dots, s_{p_{i}^{D - 1}}$ . To compute the answers for all cows in a cycle, we maintain a “sliding window” of length $D$ and keep track of the number of unique positions in an array. Specifically, to get the window for $p_{i}$ from the window for $i$ , we remove the set $s_{i}$ and add the set $s_{p_{i}^{D}}$ .

Now, returning back to $R$ . We can actually iterate across each set $s_{i}$ to account for the $R$ extra swaps. This is fast enough because we only iterate across each set at most once, the sum of the sizes of all sets $s_{i}$ is bounded by $2 K + N$ . To implement this, let the sets $s_{i}$ store pairs which include both the positions and the times at which the positions are reached.

The complexity of this solution is $O (N + K)$ .

Chris’ code:

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

int N,K;
ll M;
int A[200001],B[200001]; //input
int P[100001]; //as described in analysis
int from[100001]; //from[i] = where the cow in position i originated from
vector<pair<int,int>>S[100001]; //as described in analysis, stores {pos, time}
int cnt[100001]; //array to keep track of uniquePos
int uniquePos; //# of unique reachable positions

//adds in all reachable positions from S_node where time<=bar
void add(int node, int bar){
  for (auto x:S[node]){
    if (x.second>bar) return;
    if (cnt[x.first]==0)
      uniquePos++;
    cnt[x.first]++;
  }
}

//removes all reachable positions from S_node where time<=bar
void remove(int node, int bar){
  for (auto x:S[node]){
    if (x.second>bar) return;
    if (cnt[x.first]==1)
      uniquePos--;
    cnt[x.first]--;
  }
}

vector<int>nodes; //stores nodes currently in cycle
bool vis[100001];

void dfs(int node){
  vis[node]=true;
  nodes.push_back(node);
  if (!vis[P[node]])
    dfs(P[node]);
}

int main(){
  cin>>N>>K>>M;
  for (int i=0;i<K;i++)
    cin>>A[i]>>B[i];
  //initialize from and S
  for (int i=1;i<=N;i++){
    from[i]=i;
    S[i].push_back({i,0});
  }
  //simulate the first K swaps, keeping track of where each position can reach
  for (int i=0;i<K;i++){
    S[from[A[i]]].push_back({B[i],i+1});
    S[from[B[i]]].push_back({A[i],i+1});
    swap(from[A[i]],from[B[i]]);
  }
  //compute array P after first K swaps
  for (int i=1;i<=N;i++)
    P[from[i]]=i;
  int ans[100001];
  //run a DFS on each cycle
  for (int i=1;i<=N;i++)
    if (!vis[i]){
      dfs(i);
      ll D=M/K; //as described in the analysis
      int R=M%K; //as described in the analysis
      //"special case" if the whole cycle is included
      if (D>=(int)nodes.size()){ 
	D=nodes.size();
	R=0;
      }
      int j=D-1;
      //initialize our sliding window [0,j]
      for (int k=0;k<=j;k++)
	add(nodes[k],K);
      //we slide our window [i,j], adding and removing as we go
      for (int i=0;i<nodes.size();i++){
	int newJ=(j+1)%(int)nodes.size();
	//account for the extra R swaps
	add(nodes[newJ],R);
	//store answer for current sliding window
	ans[nodes[i]]=uniquePos;
	//undo the extra R swaps
	remove(nodes[newJ],R);
	//undo the left endpoint of sliding window
	remove(nodes[i],K);
	//add new right endpoint of sliding window
	add(nodes[newJ],K);
	j=newJ;
      }
      //reset everything from this cycle
      for (int k=0;k<=D-1;k++)
	remove(nodes[k],K);

[/hide]