PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Aaryan Prakash
Testers: Utkarsh Gupta, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
2398
PREREQUISITES:
None
PROBLEM:
Infinitely many people stand in a line, and some operations are performed:
- Type 1: A ball is given to the first person. Then, if someone has two balls, they drop one and pass the other to the person on their right. This continues as long as at least one person has two balls.
- Type 2: Each person with a ball passes it to the person on their left. If the first person has a ball, they drop it.
You are given the total number of operations N, and the K instances of time (A_1, A_2, \ldots, A_K) when type 2 operations were performed. Find the total number of dropped balls.
EXPLANATION:
Let’s treat the current state of the people as a binary string: the i-th character is 1 if person i currently holds a ball, and 0 otherwise. Let the number represented by this binary string be x.
Now, note that:
- A type 1 operation corresponds to adding 1 to x.
- A type 2 operation corresponds to dividing x by 2.
This allows to easily represent the current state of the people using only arithmetic operations.
We want to count the number of dropped balls at the end of the process. This is the same as the total number of balls introduced, minus the number of balls present at the end of the process.
These two quantities are not too hard to calculate:
- Note that each type 1 operation introduces exactly one new ball (and maybe drops some old balls, but we don’t care about that). A type 2 operation doesn’t introduce any new ball.
So, the total number of balls is exactly N - K, i.e the number of type 1 operations. - To compute the number of balls at the end, we can use the arithmetic operations above to quickly simulate the process.
- Initially, x = 0.
- Consider a type 2 operation at time A_i.
- The previous type 2 operation was at A_{i-1} (for convenience, define A_0 := 0). So, exactly A_i - A_{i-1} - 1 type 1 operations were performed before this. Each of them adds 1 to x, so we increase x by A_i - A_{i-1} - 1. Now, divide x by 2 to simulate the type 2 operation at time A_i.
- Finally, there are N - A_K more type 1 operations at the end, so add this value to x.
This process lets us compute the final value of x in \mathcal{O}(K). Once we know x, the number of balls currently with us is exactly the number of set bits in the binary representation of x, which is easy to compute.
Subtract this value from N-K and we obtain our final answer.
TIME COMPLEXITY
\mathcal{O}(K) per test case.
CODE:
Setter's code (C++)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <numeric>
#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
// change if necessary
#define MAXN 1000000
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
int cur_val = 0;
int prev = 0;
for (int i = 0; i < k; i++) {
int a;
cin >> a;
cur_val += a - prev - 1;
cur_val >>= 1;
prev = a;
}
cur_val += n - prev;
cout << (n - k) - __builtin_popcount(cur_val) << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
num = prv = 0
for x in a:
num += x - prv - 1
num //= 2
prv = x
num += n - prv
print(n-k - bin(num)[2::].count('1'))