Contest Results

Processing math: 100%

(Analysis by Richard Qi)

For $N \le 1000, T \le 10000$ , we can directly simulate the process described by the problem. Initialize an array corresponding to the current order of the cows ( $0$ to $N-1$ ). Call this array "order".

For each timestep, first update "order" by shifting according to the indices listed in $A$ (you can create a copy of "order" and change the values in the copy, or swap/change the values in place). Then, update $A$ by adding one to each element and taking modulo $N$ .

Richard's code (C++):

#include <bits/stdc++.h>
using namespace std;
 
const int mx = 200005;
int A[mx];
int ans[mx];
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int N, K, T; cin >> N >> K >> T;
    for(int i = 1; i <= K; i++){
        cin >> A[i];
    }
 
    for(int i = 0; i < N; i++){
        ans[i] = i;
    }
 
    for(int t = 1; t <= T; t++){
        //active positions rotate
        vector<int> vals;
        for(int i = 1; i <= K; i++){
            vals.push_back(ans[A[i]]);
        }
        for(int i = 0; i < K; i++){
            ans[A[i+1]] = vals[(i-1+(vals.size())) % (vals.size())];
        }
        for(int i = 1; i <= K; i++){
            A[i] = (A[i]+1) % N;
        }
    }
    for(int i = 0; i < N; i++){
        cout << ans[i];
        if(i+1 < N) cout << " ";
    }
    cout << "\n";
}

For the full solution, it helps to work out some examples of the process on paper, or use your brute force solution to list out some examples for you.

Here's the output of a brute force solution on a slightly larger test case:

INPUT
N=10 K=3 T=15
A=[0, 3, 7]
SIMULATING
Initial, T = 0: order = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], A = [0, 3, 7]
T = 1: order = [7, 1, 2, 0, 4, 5, 6, 3, 8, 9]
T = 1: A = [1, 4, 8]
T = 2: order = [7, 8, 2, 0, 1, 5, 6, 3, 4, 9]
T = 2: A = [2, 5, 9]
T = 3: order = [7, 8, 9, 0, 1, 2, 6, 3, 4, 5]
T = 3: A = [3, 6, 0]
T = 4: order = [6, 8, 9, 7, 1, 2, 0, 3, 4, 5]
T = 4: A = [4, 7, 1]
T = 5: order = [6, 3, 9, 7, 8, 2, 0, 1, 4, 5]
T = 5: A = [5, 8, 2]
T = 6: order = [6, 3, 4, 7, 8, 9, 0, 1, 2, 5]
T = 6: A = [6, 9, 3]
T = 7: order = [6, 3, 4, 5, 8, 9, 7, 1, 2, 0]
T = 7: A = [7, 0, 4]
T = 8: order = [1, 3, 4, 5, 6, 9, 7, 8, 2, 0]
T = 8: A = [8, 1, 5]
T = 9: order = [1, 2, 4, 5, 6, 3, 7, 8, 9, 0]
T = 9: A = [9, 2, 6]
T = 10: order = [1, 2, 0, 5, 6, 3, 4, 8, 9, 7]
T = 10: A = [0, 3, 7]
T = 11: order = [8, 2, 0, 1, 6, 3, 4, 5, 9, 7]
T = 11: A = [1, 4, 8]
T = 12: order = [8, 9, 0, 1, 2, 3, 4, 5, 6, 7]
T = 12: A = [2, 5, 9]
T = 13: order = [8, 9, 7, 1, 2, 0, 4, 5, 6, 3]
T = 13: A = [3, 6, 0]
T = 14: order = [4, 9, 7, 8, 2, 0, 1, 5, 6, 3]
T = 14: A = [4, 7, 1]
T = 15: order = [4, 5, 7, 8, 9, 0, 1, 2, 6, 3]

Try looking at the above output; notice any patterns? There are two similar solutions that naturally follow from patterns that can be found in the above output. The solution code for each solution is at the bottom of the page.

Solution 1: Look at a single cow's journey over time. For example, look at cow $0$ . Cow $0$ started at position $0$ at $T = 0$ , then was at position $3$ during $1 \le T \le 3$ , then was at position $6$ during $4 \le T \le 6$ . Other than $T=0$ , cow $0$ appears to stay at a position for exactly $3$ minutes, then move $3$ positions forward, then stay at that position for exactly $3$ minutes, etc.

This is no coincidence: cow $1$ follows the same behavior! Cow $1$ starts at position $1$ for $0 \le T \le 1$ , then goes to position $4$ for $2 \le T \le 4$ , then goes to position $7$ for $5 \le T \le 7$ . In fact, if you examine further, cow $2$ also exhibits this behavior, moving $3$ positions forward every $3$ minutes. Cow $3$ moves $4$ positions forward every $4$ minutes, which is slightly different from cows $0-2$ , but still follows the pattern of moving $i$ positions every $i$ minutes.

A natural question to ask is "why is this happening?". We will prove why this is happening for cow $2$ . Because $A_1 = 0$ and $A_2 = 3$ , cow $2$ is "between" these two active positions and does not move until $T = 2$ , when $A_1 = 2, A_2 = 5$ . During this timestep, cow $2$ moves to position $5$ . So, after this timestep, cow $2$ is at position $5$ , $A_1 = 3, A_2 = 6$ . Notice that at the very beginning of timestep $T=3$ , cow $2$ is still between the active positions $A_1$ and $A_2$ . In fact, cow $2$ is exactly two positions after $A_1$ and $1$ position before $A_2$ , which was true at $T=0$ as well.

This motivates looking at cow $2$ in the following way: observe cow $2$ relative to active positions $A_1$ and $A_2$ . Cow $2$ is always between $A_1$ and $A_2$ , because cow $2$ stays in place while $A_1$ and $A_2$ increase at a rate of $1$ unit per second, and as soon as $A_1$ is equal to the position of cow $1$ , cow $1$ jumps ahead $A_2-A_1$ positions and is now just behind position $A_2$ . This also shows why cow $j$ jumps exactly $A_{i+1}-A_i$ positions every $A_{i+1}-A_i$ timesteps (if $A_i \le j < A_{i+1}$ ).

We use the above observation to solve the problem in the following way: first, define $A_{K+1} = N$ for convenience. Then, for each $i$ from $i=1$ to $i=K$ , consider all cows $j$ in the range $A_i \le j < A_{i+1}$ .

Cow $j$ first stays in place for $j-A_i$ minutes, during which $A_i$ increases to meet $j$ . Then, on the $j-A_i+1$ th minute, $j$ jumps forward $A_{i+1}-A_i$ positions.

After this point, there are $T' = T-(j-A_i+1)$ minutes left to go. From then on, every $A_{i+1}-A_i$ minutes, cow $j$ 's position increases by $A_{i+1}-A_i$ . So, during this phase, cow $j$ 's position increases $\lfloor \frac{T'}{A_{i+1}-A_i} \rfloor$ times, and each time, cow $j$ 's position increases by $A_{i+1}-A_i$ positions, for a total position increase of $\lfloor \frac{T'}{A_{i+1}-A_i} \rfloor \cdot (A_{i+1}-A_i)$ .

We can compute this quantity in $\mathcal O \left(1 \right)$ time for every position $j$ , for a total time complexity of $\mathcal O \left(N \right)$ .

Solution 2: Instead of having the active positions shift by $+1$ , which hard to think about, suppose that instead all cows shift by $-1$ , while the active positions remain constant throughout the entire process. In this way, the relative positions between the active indices and the cows remain exactly the same. So, if we simulate the process of shifting cows back by $-1$ and keeping $A$ constant, we will end up with the same final array as the original process (shifted by $T$ ).

Here's the output of this shifted order; the pattern is easier to spot now.

INPUT
N=10 K=3 T=15
A=[0, 3, 7]
SIMULATING
Initial, T = 0: order = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], A = [0, 3, 7]
T = 1: order_shifted = [1, 2, 0, 4, 5, 6, 3, 8, 9, 7]
T = 2: order_shifted = [2, 0, 1, 5, 6, 3, 4, 9, 7, 8]
T = 3: order_shifted = [0, 1, 2, 6, 3, 4, 5, 7, 8, 9]
T = 4: order_shifted = [1, 2, 0, 3, 4, 5, 6, 8, 9, 7]
T = 5: order_shifted = [2, 0, 1, 4, 5, 6, 3, 9, 7, 8]
T = 6: order_shifted = [0, 1, 2, 5, 6, 3, 4, 7, 8, 9]
T = 7: order_shifted = [1, 2, 0, 6, 3, 4, 5, 8, 9, 7]
T = 8: order_shifted = [2, 0, 1, 3, 4, 5, 6, 9, 7, 8]
T = 9: order_shifted = [0, 1, 2, 4, 5, 6, 3, 7, 8, 9]
T = 10: order_shifted = [1, 2, 0, 5, 6, 3, 4, 8, 9, 7]
T = 11: order_shifted = [2, 0, 1, 6, 3, 4, 5, 9, 7, 8]
T = 12: order_shifted = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
T = 13: order_shifted = [1, 2, 0, 4, 5, 6, 3, 8, 9, 7]
T = 14: order_shifted = [2, 0, 1, 5, 6, 3, 4, 9, 7, 8]
T = 15: order_shifted = [0, 1, 2, 6, 3, 4, 5, 7, 8, 9]

The pattern is the following: for every $i$ , the values in the range $A_i \le j < A_{i+1}$ always stay in the positions which are in the range $A_i \le j < A_{i+1}$ . If we consider these values, the values cyclically shift left by $1$ every minute.

For example, look at the indices $3, 4, 5, 6$ in the above output. The values at those indices start as $3, 4, 5, 6$ at $T = 0$ , then $4, 5, 6, 3$ at $T=1$ , then $5, 6, 3, 4$ at $T=2$ , then $6, 3, 4, 5$ at $T=3$ , then $3, 4, 5, 6$ at $T=4$ (and keeps repeating in this cycle forever).

So, for each $j$ such that $A_i \le j < A_{i+1}$ , we cyclically shift it to the left $T$ times modulo $A_{i+1}-A_i$ within the subarray with left endpoint $A_i$ and right endpoint $A_{i+1}-1$ . Finally, at the end, we add back $T$ to the final position to get back the original indices.

Richard's code (Solution 1, Python):

# Read in the input
N, K, T = map(int, input().split())
A = list(map(int, input().split())) + [N] # append the value N to the sequence

ans = [-1] * N # declare an empty final array

for i in range(K):
    for j in range(A[i], A[i+1]):
    	T_prime = T-(j-A[i]+1)

    	if T_prime >= 0:
    		increase_times = 1 + T_prime // (A[i+1]-A[i]) # integer division is // in python
    		ending_position = (j + increase_times * (A[i+1]-A[i])) % N
    	else:
    		# doesn't move at all
    		ending_position = j

    	ans[ending_position] = j

# Print the output
print(" ".join(map(str, ans)))

Richard's code (Solution 2, C++):

#include <bits/stdc++.h>
using namespace std;
 
const int mx = 200005;
int A[mx];
int ans[mx];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int N, K, T; cin >> N >> K >> T;
    for(int i = 1; i <= K; i++){
        cin >> A[i];
    }
    A[K+1] = N;
    for(int i = 1; i <= K; i++){
        for(int j = A[i]; j < A[i+1]; j++){
            //where is j relative to A[i]
            int current_shift = j-A[i];
            //j moves backwards T times
            int new_shift = current_shift-T;
            int diff = A[i+1]-A[i];
            new_shift = (new_shift % diff + diff) % diff; //take mods to get it back in the range [0, diff-1].
            
            //A[i] moves new_shift times, then we shift our perspective by T.
            ans[(A[i]+new_shift+T) % N] = j;
        }
    }
    for(int i = 0; i < N; i++){
        cout << ans[i];
        if(i+1 < N) cout << " ";
    }
    cout << "\n";
}