PEWDSVTS - Editorial (Unofficial)

Problem

** PREREQUISITES :**
Priority Queue or Queue

PROBLEM:
Pied Piper currently have A users and gains X user every day, Other company Hooli has B users and gains Y users every day, given a parameter Z you have to tell which company reaches Z users first. In case if both the company reach Z users on the same day then you have to print “RIP”

Piper has N supporters C1, C2,…Cn. When an i-th supporter supports Piper, company instantly gains Ci subscriber and the value of Ci is halved
A supporter can support any number of times. Print the “minimum” number of time supporters must support so that Pied piper gains control of Pipernet else print “RIP”.

APPROACH
First we need to calculate the new value of A that is before any support, it can be easily done using:

val = (Z - B) // Y

“val” above represents the day after which “hooli” reaches Z users.
Now we calculate the users gained by Pied Piper in that same number of days using:

newA = A + X * val

After above calculation we need to find if it is possible for Pied Piper to reach Z users with the help of support if so then print the minimum number else “RIP”

The problem can be easily solved using a priority queue, in priority using heap-pop we can pop out the smallest element of the heap, so to actually put this property in use we first replace all the elements of the array by their negative value and heapify it. After this whenever we heap-pop we will get the "biggest number in array or the smallest in heap "(think about this). just keep adding the support(max Ci) value to new value of A, if it gets greater than z then break, After adding the value of max(arr) to new value of A check

if int(Ci/2) >=0

if it is greater then zero then append floor(Ci/2 ) to heap. If length of heap gets equal to zero then break.

Check if newA > Z: print(count), else print “RIP”

Solution (python3) - above approach
Solution using Alternative approach - using 2 queues

5 Likes

Problem can be easily solved using array. My approach is to find the maximum element from the array and make the contribution from all the elements which are greater than maximum/2 then sort the array again . repeat the following steps until maximum element becomes 0 or a reached to z ( as log2(10^9) is something around 33 ) this will not lead to TLE. link to my solution

6 Likes

gazab … amazing… even i thought something like that but yours one is more optimised…

1 Like

Any resources where I can learn to calculate complexity ? All I knew was this isn’t going to happen in linear time, and what 33 actually is.

2 ^ 33 is around 10^9 . so while loop in my code will run 33 time in worst case ( means if largest element in an array is 10^9 ,2 will divide it 33 times to become 1 ) so sorting will also perform atmost 33 times only.
read my code in above reply while going through these lines.

you can find many resources easily to learn to analyse time complexity of an algorithm, just google it .

1 Like

Could you please help me finding my bug in this problem? :sob:
https://www.codechef.com/viewsolution/24074877

@will_of_ken
You need to sort the array after every operation…
Use priority queue… it automatically sorts array after each operation…
suppose you have
16 2 2 1 1 as array…
then you will remove 16 then 8 then 4 and then 2… but your code removes 16 ,2 , 2 ,1 ,… etc.

YOUR CODE EDITED
see this edit in your soln.
It TLE because of not using priority queue…
SAMPLE AC CODE using pq

Yours is O(T*n*30*log(n)) = O(5.10 * 10^8)
My first approach was O(T*n*30*log(n*30))= O(6.6* 10^8)
Mine is TLE :frowning_face:
my second approach was with same time complexity as yours 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…

2 Likes

@l_returns
Thanks a lot… :heart_eyes:
I understand… :blush:

1 Like

You’re welcome :smiley:

i already have a backup plan of O(T nlog(n) ) as after every iteration of while loop i will get two sorted arrays ( first segment of all starting elements which isn’t contributed to A and other which contributed) and it takes only linear time to merge two sorted arrays.
Hopefully time limit is not strict … I love the author for not keeping it strict :slight_smile: that too in a short contest

1 Like

@shivamchef
Authors solution is O(T*n*30*log(n)) (takes 0.45 secs link)
Its strict according to intended solution…
I hate author for keeping it that strict :frowning_face: and that too in a short contest… XD

1 Like

@l_returns
I submitted my O(T * n * log(n) ) and it is taking 0.78 secs link. can u tell the reason? ( Actually i am newbie at Div 1).

1 Like

@shivamchef
actually its O(T*n*log(n) + T*(z-b)/y ) == O(1.051 *10^10)
Now it seems like there were weak test cases also :frowning_face:
Anyways here are your AC optimized solutions…
https://www.codechef.com/viewsolution/24075489 (0.12 secs with fast i/o)
https://www.codechef.com/viewsolution/24075503 (0.34 without fast i/o)

1 Like

ok! just icremented value of A using formula and got link (0.34 secs).
Thnkx :slight_smile:

2 Likes

lol we are working parallel. XD!!

1 Like

XD… Btw I am sorry I posted your solution link on official editorial page…

Thanks a lot.
I was doing the same mistake.

2 Likes

I modified it a bit i.e. instead of breaking loop when A>=Z if i break when A+X>B+Y
I am getting WA.could you please check it ,why is it happening?
here is link:https://www.codechef.com/viewsolution/24080819

1
1 2 4 10 9 83
1
Refer this test case…
here lldA>lldB but still you need one contribution to beat… ( to avoid a situation where both achieves the score together and opponent wins as per que)

1 Like