For the first two subtasks, we can just simulate. $NK$ 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 $2K+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 \le i \le 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 $\mathcal{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); } }