Home » 国际竞赛 » Details

USACO 2021 January Contest, Silver Problem 1. Dance Mooves

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

USACO 2021 January Contest, Silver Problem 1. 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 indefinitely in a cyclic fashion. 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.

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

The first line contains integers $N$ and $K$ . 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:

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

SCORING:

Test cases 1-5 satisfy $N \leq 100, K \leq 200$ .
Test cases 6-10 satisfy $N \leq 2000, K \leq 4000$ .
Test cases 11-20 satisfy no additional constraints.

Problem credits: Chris Zhang

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

题解请注册或登录查看

[/hide]

(Analysis by Chris Zhang)

For the first two subtasks, we can just simulate. $N K$ minutes will suffice because the sequence of positions of an individual cow will start repeating within that time.

Now, onto the full solution. After the first $K$ swaps, we compute where each cow ends up. If a cow started at the $i$ -th position, let its new position be $p_{i}$ . Let’s also track the set $s_{i}$ of all positions that cow $i$ reached during the $K$ swaps. This does not take too much memory because the sum of the sizes of all sets $s_{i}$ is bounded by $2 K + N$ (every swap, at most two cows move, thus adding at most two elements to the sets).

Let’s build a directed graph on the positions that shows how the cows move every $K$ swaps. We have $N$ directed edges from all $i$ to $p_{i}$ $(1 \leq i \leq N)$ . This graph is a bunch of cycles because after $K$ swaps, there is exactly one cow in each position, so the outdegree and indegree of each node is one. Therefore, the graph is a bunch of disjoint cycles (as with Swapity Swapity Swap).

We claim that the answers for all cows in the same cycle are the same. Because everything repeats every $K$ swaps, if two cows have ever been in the same position after a multiple of $K$ swaps, they would visit the same positions eventually. After $K$ swaps, cow $i$ goes to position $p_{i}$ , so the answers for cow $i$ and cow $p_{i}$ are the same. This logic extends to every cow in the cycle (the answer for cow $p_{i}$ is equal to cow $p_{p_{i}}$ and so on).

So, what exactly is the answer for some cycle? It’s the size of the union of all the sets $s_{i}$ for each cow $i$ in the cycle. In other words, the answer is the number of unique positions in all the sets in the cycle. The complexity of this solution is $O (N + K)$ .

Chris’ code:

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

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

//add in S_node
void add(int node){
  for (int x:S[node]){
    if (cnt[x]==0)
      uniquePos++;
    cnt[x]++;
  }
}

//remove S_node
void remove(int node){
  for (int x:S[node]){
    if (cnt[x]==1)
      uniquePos--;
    cnt[x]--;
  }
}

bool vis[100001];
queue<int>q; //stores all nodes in current cycle

void dfs(int node){
  vis[node]=true;
  add(node);
  q.push(node);
  if (!vis[P[node]])
    dfs(P[node]);
}

int main(){
  cin>>N>>K;
  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);
  }
  //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]);
    S[from[B[i]]].push_back(A[i]);
    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);
      int tempAns=uniquePos; //the answer 
      //assign the answer for all nodes in the cycle, which we've stored in this queue
      while (!q.empty()){
	remove(q.front());
	ans[q.front()]=tempAns;
	q.pop();
      }
    }
  for (int i=1;i<=N;i++)
    cout<<ans[i]<<endl;
  return 0;
}

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class DanceMoovesSilver {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());
        int[] cows = new int[n + 1];
        List<Integer>[] viewed = new List[n + 1];
        for (int j = 1; j <= n; j++) {
            cows[j] = j;
            viewed[j] = new ArrayList<>();
            viewed[j].add(j);
        }
        for (long t = 1; t <= k; t++) {
            tokenizer = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            int c = cows[a];
            int d = cows[b];
            cows[a] = d;
            cows[b] = c;
            viewed[cows[a]].add(a);
            viewed[cows[b]].add(b);
        }
        int[] answer = new int[n + 1];
        for (int r = 1; r <= n; r++) {
            if (cows[r] != 0) {
                List<Integer> cycle = new ArrayList<>();
                int j = r;
                while (cows[j] != 0) {
                    cycle.add(j);
                    j = cows[j];
                    cows[cycle.get(cycle.size() - 1)] = 0;
                }
                Set<Integer> viewedHere = new HashSet<>();
                for (int cow : cycle) {
                    viewedHere.addAll(viewed[cow]);
                }
                for (int cow : cycle) {
                    answer[cow] = viewedHere.size();
                }
            }
        }
        StringBuilder out = new StringBuilder();
        for (int j = 1; j <= n; j++) {
            out.append(answer[j]).append('\n');
        }
        System.out.print(out);
    }
}

[/hide]