PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Udit Sanghi
Tester: Teja Vardhan Reddy
Editorialist: Oleksandr Kulkov
DIFFICULTY:
SIMPLE
PREREQUISITES:
Priority queue
PROBLEM:
Pied Piper has A users and gain X users everyday. Meanwhile Hooli has B users and gain Y users everyday. Whichever company reaches Z users first takes over Pipernet.
Pied Piper has N supporters with contribution values C_1, \dots, C_N. When i-th supporter contributes, Pied Piper get C_i users instantly. After this C_i is halved, thus it’s going to be equal to \lfloor C_i / 2 \rfloor. What is the minimum number of times supporters must contribute?
EXPLANATION:
It’s always profitable to make all contributions on the first day and contribute only largest possible numbers at every moment of time. To do this you may, keep a current set C_1, \dots, C_N in priority queue and pick the largest one all the time returning half of it to the queue.
How to check if Pied Piper loses to Hooli? You have to find minimum integer T_1 such that A+XT_1 \geq Z and minimum integer T_2 such that B+YT_2 \geq Z and compare them. It holds that:
Thus this check is done in the following code:
bool lose(int A, int X, int B, int Y, int Z) {
int t1 = (Z - A + X - 1) / X;
int t2 = (Z - B + Y - 1) / Y;
return t1 >= t2;
}
Work with priority queue is quite straight-forward and looks like this afterwards:
priority_queue<int> C = {C_1, ..., C_N};
while(C.top() != 0 && lose(A, X, B, Y, Z)) {
ans++;
A += C.top();
C.push(C.top() / 2);
C.pop();
}
if(lose(A, X, B, Y, Z)) {
cout << "RIP" << endl;
} else {
cout << ans << endl;
}
This solution works in O(N \log N \log C). Note that multiset wouldn’t do here due to higher constant, as well as full sorting of all possible values. But it’s possible to solve the problem in O(N \log C) using radix sort, which is a bit more complicated.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
