PEWDSVTS - Editorial

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:

T_1 = \left\lceil \dfrac{Z-A}{X}\right\rceil, T_2 = \left\lceil \dfrac{Z-B}{Y}\right\rceil

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.

3 Likes

Could you please help me by finding my bug… :sob:
https://www.codechef.com/viewsolution/24074877

@mathecodician @teja349 @melfice
Authors solution is O(T*n*30*log(n)) = O(5.10 * 10^8) (0.45 secs)
My first approach was O(T*n*30*log(n*30))= O(6.6* 10^8)
https://www.codechef.com/viewsolution/24055261
Mine is TLE :frowning_face:
My second approach was with same time complexity as authors which passes in 0.42 secs
Too strict time limit… I hate author for keeping it that strict :frowning_face: and that too in a short contest…
Also the test cases were weak in other way… because O(T*n*30*log(n) + T*(z-b)/y) = O(105.10 * 10^8)
also passes…
Link : https://www.codechef.com/viewsolution/24054001
Please correct me if I am wrong…

1 Like

Could you help me to find where I went wrong in my solution?
https://www.codechef.com/viewsolution/24058564

@kprogrammer you should run loop until ‘fina’ becomes ‘z’ not 100 and after this your code is also not optimised it will give tle , try to reduce the number of sort operation or use priority queue as stated in editorial.

I am such a dumb idiot.
Since I am a noob, could you say how could I optimize this without the use of priority queue?
Thanks for your help

you are sorting array after each contribution , you can reduce it to 30 times in worst case.
see here

you can also go through this thread for further explanation.

Thanks.
I cannot understand a lot of c++ but i will try

I have done using multiset ,and its running properly.
https://www.codechef.com/viewsolution/24079558.

hii,
just saw your code,
firstly line
21
what if (y*k)==(z-b)
second
after giving the contribution the last value will become half so you need to sort your array again . you don’t know if the half of the last value is still greater than 2nd last value(always take last value of the sorted array (largest))
and
third you should check whether is it possible for the given contribution to overcome the remaining difference.
try it now.

why we can not use a multiset ?
can you explain plz ?

@anmol1point0
Thanks… :heart_eyes:
I understand :slightly_smiling_face:

1 Like

@admin @vijju123 @mathecodician @teja349 @melfice
Please check this and if you think test cases are weak then please edit the question for practice purpose at least…

Hello can you please tell me what’s wrong with my code? i have first computed the days and the contributions so far by pied and hooli and then i am trying to find the contributions by the remaining people… here is the link to my code

Could any one explain the step
int t1=(Z-A+X-1)/X;

Can’t we do as explained above
int t1=ceil((Z-A)/X);
?

#include <bits/stdc++.h>
#define ll long long int
#define N 100000
#define M 1000000007
#define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define po pop_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define cot cout.tie(0)//Solution by abhj
using namespace std;ll c[N];
#define watch(x) cout << (#x) << " is " << (x) << endl
int main(){
    ibs;cti; 
    int T;
    cin>>T;
    while(T--){
            int n;ll a,b,x,y,z;cin>>n>>a>>b>>x>>y>>z;bool check=0;
            for (int i = 0; i < n; ++i)
                cin>>c[i];
            for (int i = 1; ; ++i)
            {
                for(int j=0;j<n;j++)
                {
                    sort(c,c+n);
                    if (c[n-1]==0)
                    {
                        cout<<"RIP"<<"\n";check=1;break;;
                    }
                    a+=c[n-1];c[n-1]/=2;
                }
                if (check)
                    {
                        check=0;break;
                    }
                if (a>=z&&b<z)
                {
                    cout<<i<<"\n";break;
                }
                a+=x;b+=y;
            }

        }
    return 0;
}

Please help me improve time complexity. It shows TLE