Dance Mooves USACO 2021 January Contest

Dance Mooves USACO Solution

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

At first, all NN cows (2≤N≤1052≤N≤105) stand in a line with cow ii in the iith position in line. The sequence of dance mooves is given by KK (1≤K≤2⋅1051≤K≤2⋅105) pairs of positions (a1,b1),(a2,b2),…,(aK,bK)(a1,b1),(a2,b2),…,(aK,bK). In each minute i=1…Ki=1…K of the dance, the cows in positions aiai and bibi in line swap. The same KK swaps happen again in minutes K+1…2KK+1…2K, again in minutes 2K+1…3K2K+1…3K, and so on, continuing in a cyclic fashion for a total of MM minutes (1≤M≤10181≤M≤1018). In other words,

  • In minute 11, the cows at positions a1a1 and b1b1 swap.
  • In minute 22, the cows at positions a2a2 and b2b2 swap.
  • In minute KK, the cows in positions aKaK and bKbK swap.
  • In minute K+1K+1, the cows in positions a1a1 and b1b1 swap.
  • In minute K+2K+2, the cows in positions a2a2 and b2b2 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.

See Also: USACO 2021 January Contest

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

The first line contains integers NN, KK, and MM. Each of the next KK lines contains (a1,b1)…(aK,bK)(a1,b1)…(aK,bK) (1≤ai<bi≤N1≤ai<bi≤N).

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

Print NN lines of output, where the iith line contains the number of unique positions that cow ii reaches.

SAMPLE INPUT:

6 4 7
1 2
2 3
3 4
4 5

SAMPLE OUTPUT:

5
4
3
3
3
1

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

  • Cow 11 reaches positions {1,2,3,4,5}{1,2,3,4,5}.
  • Cow 22 reaches positions {1,2,3,4}{1,2,3,4}.
  • Cow 33 reaches positions {1,2,3}{1,2,3}.
  • Cow 44 reaches positions {2,3,4}{2,3,4}.
  • Cow 55 reaches positions {3,4,5}{3,4,5}.
  • Cow 66 never moves, so she never leaves position 66.

SCORING:

  • Test cases 1-5 satisfy N≤100,K≤200N≤100,K≤200.
  • Test cases 6-10 satisfy M=1018M=1018.
  • Test cases 11-20 satisfy no additional constraints.

Problem credits: Chris Zhang

Solution

For the first subtask, we can just simulate. At most NKNK 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 sisi and pipi as described in the Silver analysis, and consider the contribution of each disjoint cycle independently.

Let D=⌊M/K⌋D=⌊M/K⌋ and RR be the remainder when MM is divided by KK. There will first occur DD full iterations of KK swaps, followed by RR extra swaps. For simplicity, let’s ignore RR for now. To solve for the answer of cow ii, which is in some cycle of length LL: if DD is at least LL, the answer is the size of the union of all sets sisi in this cycle (as in the silver analysis). But if DD is less than LL, it will be the size of the union of the DD sets si,spi,sp2i,⋯,spD−1isi,spi,spi2,⋯,spiD−1. To compute the answers for all cows in a cycle, we maintain a “sliding window” of length DD and keep track of the number of unique positions in an array. Specifically, to get the window for pipi from the window for ii, we remove the set sisi and add the set spDispiD.

Now, returning back to RR. We can actually iterate across each set sisi to account for the RR extra swaps. This is fast enough because we only iterate across each set at most once, the sum of the sizes of all sets sisi is bounded by 2K+N2K+N. To implement this, let the sets sisi 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)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);
      nodes.clear();
    }
  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 DanceMooves {
 
    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());
        long k = Integer.parseInt(tokenizer.nextToken());
        long m = Long.parseLong(tokenizer.nextToken());
        int[] cows = new int[n + 1];
        List<View>[] views = new List[n + 1];
        for (int j = 1; j <= n; j++) {
            cows[j] = j;
            views[j] = new ArrayList<>();
            views[j].add(new View(j, 0));
        }
        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;
            views[cows[a]].add(new View(a, t));
            views[cows[b]].add(new View(b, t));
        }
        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;
                }
                Map<Integer, List<Interval>> intervalMap = new HashMap<>();
                for (j = 0; j < cycle.size(); j++) {
                    for (View view : views[cycle.get(j)]) {
                        if (m >= view.time) {
                            int covered = (int) Math.min((long) cycle.size(), ((m - view.time) / k) + 1L);
                            if (!intervalMap.containsKey(view.position)) {
                                intervalMap.put(view.position, new ArrayList<>());
                            }
                            intervalMap.get(view.position).add(new Interval(j, Math.min(cycle.size(), j + covered)));
                            if (j + covered > cycle.size()) {
                                intervalMap.get(view.position).add(new Interval(0, (j + covered) % cycle.size()));
                            }
                        }
                    }
                }
                int[] amts = new int[cycle.size() + 1];
                for (List<Interval> intervals : intervalMap.values()) {
                    intervals.sort(Comparator.comparingInt(interval -> interval.from));
                    int prev = 0;
                    for (Interval interval : intervals) {
                        amts[Math.max(prev, interval.from)]++;
                        prev = Math.max(prev, interval.until);
                        amts[prev]--;
                    }
                }
                for (j = 0; j < cycle.size(); j++) {
                    answer[cycle.get(j)] = amts[j];
                    amts[j + 1] += amts[j];
                }
            }
        }
        StringBuilder out = new StringBuilder();
        for (int j = 1; j <= n; j++) {
            out.append(answer[j]).append('\n');
        }
        System.out.print(out);
    }
 
    static class View {
        final int position;
        final long time;
 
        View(int position, long time) {
            this.position = position;
            this.time = time;
        }
    }
 
    static class Interval {
        final int from;
        final int until;
 
        Interval(int from, int until) {
            this.from = from;
            this.until = until;
        }
    }
}

USACO 2021 January Contest Solution

Leave a Comment