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.
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
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 .
@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.
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
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 and that too in a short contest…
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 that too in a short contest
@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 and that too in a short contest… XD
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:CodeChef: Practical coding for everyone
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)
…
that too in a short contest
and that too in a short contest… XD