C - Merge the balls Editorial by en_translator
Consider simulating the operations.
Note that the sizes of the \(N\) balls are all power of two, and when the balls’ sizes removed by the procedure are power of two, the newly added ball also has a size of power of two, so all balls that appear has a size of power of two.
Also, \(X=Y\) is equivalent to \(2^X=2^Y\), so it is sufficient to manage the logarithm (base \(2\)) of sizes of balls instead of the sizes themselves.
Specifically, we manage the number of balls in the sequence \(L\) and the logarithm of the sizes of the balls in the sequence from left to right, \(S=(S_1,S_2,\ldots,S_L)\), and update them accordingly.
Initially, \(L=0\) and \(S=()\) (an empty sequence).
Adding the \(i\)-th ball at the right end of the sequence is achieved by letting \(L\leftarrow (L+1)\), and appending \(A_i\) to the tail of \(S\).
After that, while the length of the sequence is two or greater, repeatedly “take the last two elements \(S_{L-1}\) and \(S_{L}\) out of \(S\), compare the values, and put it back if they are different or let \(L\leftarrow (L-1)\) and append \((X+1)\) to the tail of \(S\) if they are the same.” Here, note that \(2^X+2^X=2^{X+1}\). The value \(L\) after the \(N\) operations is the answer.
Next, we consider the complexity. The former operation of adding the \(i\)-th (\(1\leq i\leq N\)) occurs exactly \(N\) times. For the latter procedure, “taking the two balls out and adding one” decreases the number of balls in the sequence by one, so it can be done at most \((N-1)\) time during the \(N\) operations. Therefore, taking out and appending ball out of or into the balls happen at most \(O(N)\) times.
Each operation can be achieved in an array, or managed in a stack. Either case, appending to or removing from the tail can be done in \(O(1)\) time. Therefore, the simulation costs a total of \(O(N)\) time, which is fast enough. Thus, the problem has been solved.
Sample code in C++:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,l=0;
int a[200000];
cin>>n;
for(int i=0;i<n;i++){
cin>>a[l];
l++;
while(l>1){
if(a[l-2]==a[l-1]){
a[l-2]++;
l--;
}
else break;
}
}
cout<<l<<endl;
return 0;
}
posted:
last update: