Subtask 1: $N \le 2000$.
We can directly simulate the process according to the problem statement. We can keep track of the amount of milk that each cow has and update in $\mathcal{O}(N)$ each minute leading to an $\mathcal{O}(N^2)$ solution.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<int> cap(n), cur(n);
for (int i = 0; i < n; i++){
cin >> cap[i];
cur[i] = cap[i];
}
for (int minute = 1; minute <= n; minute++){
rotate(cur.begin(), cur.begin() + n - 1, cur.end());
for (int i = 0; i < n; i++)
cur[i] = min(cur[i], cap[i]);
cout<<accumulate(cur.begin(), cur.end(), 0LL)<<"\n";
}
}
Subtask 2: $a_i \le 2$.
Each bucket has capacity of either $1$ or $2$ in this subtask. Consider a cow that starts off with $2$ unit of milk. That specific $2$ units of milk will keep getting passed until it reaches a bucket with capacity $1$ where it will be reduced to $1$ unit of milk.
For each $a_i=2$ we want to find the time $t$ in which it will reach a bucket with capacity $1$. Then we know that $1$ milk is lost at time $t$. We can find $t$ by finding the first $a_j=1$ on the right of $i$.
We can rotate the array such that the minimum element appears at the end. Iterating over the array backwards and keeping track of the most recent $1$ leads to an $\mathcal{O}(N)$ solution.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<int> A(n);
vector<int> reduce(n + 5, 0);
int sum = 0;
for (int &i : A){
cin >> i;
sum += i;
}
rotate(A.begin(), next(min_element(A.begin(), A.end())), A.end());
for (int i = n - 1, lst = -1; i >= 0; i--){
if (A[i] == 1)
lst = i;
if (A[i] == 2 and lst != -1){
// At time lst - i the 2 will get reduced to a 1
reduce[lst - i]++;
}
}
for (int i = 1; i <= n; i++){
sum -= reduce[i];
cout<<sum<<"\n";
}
}
Subtask 3: All $a_i$ are generated uniformly at random in the range $[1,10^9]$.
Let's rotate the array such that the minimum element appears at the end.
In the previous subtask, for each $a_i=2$, we wanted to find when that specific $2$ units of milk will reach a bucket with capacity $1$. We can extend this reasoning. For some $a_i$, we want to find all times in which that milk will get reduced.
To find these values, we can iterate over the array backwards and keep a monotonic stack. At each element, we can iterate over the entire stack and update our answer.
Because all $a_i$ are generated uniformly at random, the expected size of the monotonic stack at each $i$ is $\mathcal{O}(\log N)$. This is since the probability of $j$ ($i \le j < i+N$) being in the stack is at most $\frac{1}{j-i+1}$ since $a_j$ must be smaller than $[a_i,a_{i+1},...,a_{j-1}]$. By the linearity of expectation, the expected size of the stack is $\frac{1}{1}+\frac{1}{2}+ \dots +\frac{1}{N}=\mathcal{O}(\log N)$ by the harmonic series. Thus, the solution runs in $\mathcal{O}(N\log N)$ time.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<int> A(n);
ll sum = 0;
for (int &i : A){
cin >> i;
sum += i;
}
rotate(A.begin(), next(min_element(A.begin(), A.end())), A.end());
vector<int> stk;
vector<ll> reduce(n + 5, 0);
auto procStack = [&](int pos){
for (int i = 1; i < stk.size(); i++){
int delta = A[stk[i]] - A[stk[i - 1]];
reduce[stk[i - 1] - pos] += delta;
}
};
for (int i = n - 1; i >= 0; i--){
while (stk.size() and A[stk.back()] >= A[i]){
stk.pop_back();
}
stk.push_back(i);
procStack(i);
}
for (int i = 1; i <= n; i++){
sum -= reduce[i];
cout<<sum<<"\n";
}
}
Full Solution 1:
Let's look at what is redundant in our subtask $3$ solution. Suppose the bottom $2$ elements of the stack remain there for a long time. Then we will be iterating over them each time we process the stack.
Let's speed up our subtask $3$ solution. Consider some adjacent pair of elements ($j_{p-1},j_p$) in the stack. We know that $d=a_{j_{p-1}}-a_{j_p}$ milk is lost by going from $j_{p-1}$ to $j_p$. Let's look at all $i$ ($1 \le i \le N$) where ($j_{p-1},j_p$) is in the stack at $i$ (meaning the milk originating from $i$ will be reduced by $d$ at time $j_p-i$). Clearly, all such $i$ will form an interval.
When we remove an element from the top of the stack, we can get the interval it was active for and perform a range add to keep track of how much milk is lost at what time. This leads to an $\mathcal{O}(N)$ solution.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<int> A(n);
ll sum = 0;
for (int &i : A){
cin >> i;
sum += i;
}
rotate(A.begin(), next(min_element(A.begin(), A.end())), A.end());
vector<int> stk;
vector<ll> reduce(n + 5, 0);
for (int i = n - 1; i >= 0; i--){
while (stk.size() and A[stk.back()] >= A[i]){
if (stk.size() > 1){
// i < t1 < t2
int t1 = stk.back();
int t2 = stk[stk.size() - 2];
// Milk lost from going from t1 to t2
int delta = A[t1] - A[t2];
// When does the pair begin applying delta
int st = t2 - t1;
// For how long does the pair apply delta
int sz = t1 - i;
reduce[st] += delta;
reduce[st + sz] -= delta;
}
stk.pop_back();
}
stk.push_back(i);
}
// Finish proccessing rest of stack
while (stk.size() > 1){
int t1 = stk.back();
int t2 = stk[stk.size() - 2];
int delta = A[t1] - A[t2];
int st = t2 - t1;
int sz = t1 + 1;
reduce[st] += delta;
reduce[st + sz] -= delta;
stk.pop_back();
}
// Get answer
for (int i = 1; i <= n; i++){
reduce[i] += reduce[i - 1];
sum -= reduce[i];
cout<<sum<<"\n";
}
}
Full Solution 2:
For each $i$, we want to find the number of buckets with milk $a_i$ at each minute. To deal with the case where there are multiple same $a_i$, we only consider the number of buckets equal to $a_i$ whose milk was specifically reduced (by a non-zero amount) to $a_i$ by the bucket at $i$ (we also count the milk starting at $i$).
Let $l_i$ be the index of the first element less than or equal to $a_i$ on the left of $i$. Consider all elements strictly between $l_i$ and $i$. All these elements will be greater than $a_i$ and thus will be reduced to $a_i$ when they reach $i$. Suppose there are $s$ such elements including $a_i$. Then we will gain one additional element equal to $a_i$ at times $0,1,...,s-1$ (if we suppose we start off with $0$ elements equal to $a_i$).
Let $w_i$ store the total amount of milk at time $i$. We should perform the following update:
We also know that buckets with $a_i$ milk can be reduced to a smaller value. Let $r_i$ be the index of the first element strictly less than $a_i$ on the right of $i$. Let time $t$ be the time for the milk originating at $i$ to reach $r_i$. Then we will lose one element equal to $a_i$ at times $t,t+1,...,t+s-1$. A similar update to the one above should be performed.
We can use a monotonic stack to find $l_i$ and $r_i$. Implementation can be made easier by prepending and appending the array to itself. We can use prefix sums of prefix sums to perform the updates on $w$ efficiently. See the following example:
Thus, this solution runs in $\mathcal{O}(N)$ time.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<int> A(n);
for (int &i : A)
cin >> i;
for (int i = 0; i < 2 * n; i++)
A.push_back(A[i]);
// L is first <= on left and R is first < on right
vector<int> L(A.size()), R(A.size());
{
stack<int> stk;
for (int i = 0; i < A.size(); i++){
while (stk.size() and A[i] < A[stk.top()])
stk.pop();
L[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
}
{
stack<int> stk;
for (int i = (int)A.size() - 1; i >= 0; i--){
while (stk.size() and A[i] <= A[stk.top()])
stk.pop();
R[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
}
vector<ll> psm(n + 5, 0);
for (int i = n; i < 2 * n; i++){
// Gain A[i] during minutes [0, sz - 1]
int sz = i - L[i];
psm[0] += A[i];
psm[sz] -= A[i];
// Lose A[i] during minutes [R[i] - i, R[i] - i + sz - 1]
if (R[i] != -1){
psm[R[i] - i] -= A[i];
psm[R[i] - i + sz] += A[i];
}
}
for (int i = 1; i <= n; i++)
psm[i] += psm[i - 1];
for (int i = 1; i <= n; i++){
psm[i] += psm[i - 1];
cout<<psm[i]<<"\n";
}
}