Theoretically, why the sequence of positions of an individual cow will start repeating within NK minutes? Is it possible to be over NK mins?
You can define the state of a cow as (position, previous swap). Then, there’s at most NK states since there’s N positions and K possible last swaps.
One way to think about it is viewing each state as a node in a graph and moves as edges (for example, if a cow at position u moves to position v using swap k, then you can consider an edge that goes from (u, k - 1) to (v, k)).
Then simulating the moves for an individual cow would just be walking along the edges of a graph, and since there’s at most NK nodes, the maximum size of a cycle would be NK so a cows movements have to repeat after at most NK minutes.
1 Like
Got it. Thx.
Here, I have a follow up question about this problem. Please help me interpret it from theoretical point of view, although this code looks work based on test.
let us still take the first first data set as one example.
T0: 1 2 3 4 5
T1: 3 2 1 4 5
T2: 2 3 1 4 5
T3: 2 1 3 4 5
T4: 2 4 3 1 5
Based on this K swap, cow1 will be located to 1,3,2, and 4. However, if using the USACO reference code, the cows within the “while” loop(let us assume r==1 in below code), only cows (1,2,4) will be went through and added into the cycle. That means cow 3 is skipped in this “while” loop.
I believe these code works for all cases. However, I am not convinced from theoretical point of view. Maybe some people will argue that the set from cow3 will be covered by other cow members within this cycle. Still, how can we know it will be covered by other cow members. Could anyone explain why this while loop works as expected? Thank you so much.
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();
}
}
}