int main() {
// your code goes here
int t,n,i;
long x,a,mini,infec;
cin >> t;
while(t>=1)
{
cin >> n >> x;
vector days;
for(i=0;i<n;i++)
{
cin >> a;
days.push_back(a);
}
sort(days.begin(),days.end(),greater());
infec = days[0]; //infec variable contains max population amongst countries
mini =0;
/*
In this algo what I am doing is I am running a while loop to increase the value of x until it becomes greter than the
total no of people infected in country with max population. I am decreasing the value of infec when 2*x>infec
while increasing the value of x if it becomes greter than the population of other countries than i am increasing value of days and
removing that country from list.
my test cases are running fine.
*/
while(!days.empty() && x<infec)
{
if(x>=days.back() && (2*days.back())>x)
{
mini++;
x = days.back()*2;
days.pop_back();
//cout << mini <<endl;
continue;
}
else
{
mini++;
x = x*2;
if(infec<2*x)
{
infec = infec - x;
infec = 2*infec;
//x = x*2;
}
}
//cout << x <<endl;
}
if(x>=infec && !days.empty())
{
while(!days.empty())
{
days.pop_back();
mini++;
}
}
cout << mini <<endl;
t--;
}
return 0;
in last while loop, i am comparing the last element with x and multiplying x by 2 and decrementing a[n-1] - x and then multiplying a[i]*2 and after that if a[i] becomes greater than that of original value of a[i] then donât change a[i].
in this process if we find an element in the array a, which became less than x due to doubling of x.
then what we do is, we give vaccines to that one and make the infected people of that country zero. and x= a[pos] * 2
(HERE POS IS THE POSITION OF THAT ELEMENT WHICH IS SMALLER THAN OR EQUAL TO X)
(THIS I HAVE DONE IN THAT FOR LOOP INSIDE WHILE LOOP)
(IF WE FOUND POS THEN DO THE ABOVE THING ELSE CARRY ON WITH THE LAST ELEMENT)
1st we will cure country with pop 20 and get 40 vac. +1
now we will cure the country with pop 41 and get 80 vac. but it will not cure it fully +1
now we will cure â19â and get 38 vac +1
//by this time array looks like 9,0,0,4 due to doubling of pop.
now we will cure 9 ans get 18 vac. +1
//now array is {8}
we will cure last one. +1
total â+1â -->5
time limit exceeds for 5 cases in subtask 2
please help:-
#include #include #include #include #include
using namespace std;
long long sums(vector a){
long long sum{};
for(long long c:a)
sum=sum+c;
return sum;
}
int main(){
long long n{};
cin>>n;
vector result{};
for(int i{};i<n;i++){
long long m{},vaccines{},sum{},counts{};
cin>>m>>vaccines;
vector a{};
for(int j{};j<m;j++){
long long h{};
cin>>h;
sum=sum+h;
a.push_back(h);}
sort(a.begin(),a.end());
while(sum!=0){
vector pos{};
if(a[m-1]<=vaccines){
sum=0;
for(long long c:a){
if(c!=0)
counts=counts+1;}}
else{
for(long long j{};j<m;j++){
if(a[j]<=vaccines and 2*a[j]>=vaccines){
vaccines = 2*a[j];
a[j]=0;
counts=counts+1;
sum=sums(a);}}}
if(sum!=0){
for(long long j{m-1};j>=0;j--){
if(2*a[j]>=vaccines){
pos.push_back(j);
break;}}
sort(pos.begin(),pos.end());
if(pos.size()==0){
sum=0;
for(long long c:a){
if(c!=0)
counts=counts+1;}}
else{
long long z{pos[pos.size()-1]};
for(long long j{};j<m;j++){
if(j!=z)
a[j] = min(a[j],2*a[j]);}
a[z] = min(a[z],2*(a[z]-vaccines));
vaccines=2*vaccines;
sum=sums(a);
counts=counts+1;}}
}
result.push_back(counts);
@g_himanshu0100 your logic goes O(n^2) in the worst case , while O(n) or O(n logn) is accepted , try reducing your complexity
if you have any doubts , click here to view my solution
my logic - i have created a multiset storing poppulations of every country in ascending order.
At any day (be it the first day of curing) if the number of cures vailable, X,
is equal or greater than the largest element in multiseet (country with the largest population) then the answerw will be size of the multiset (as if we start from the last we can cure each country in one day)
IF X is less than last element of multiset then arises two cases :
A) if its the first day of curing - then simply use X to cure the country with highest population (last ekement of set), no need to update X (X remains same for the next day) and then update the coutnries population (after doubling) on which we used X cures. and we increment the tally of total days required by one.
B) else (when its not first day) - then we further chek a condition hence two cases arise -
a) we will search for a element in multiset within the range [x,2x] inclusively
if a value found then we will use as many cures as the value of element returned
i.e size of population found within range [x,2x] let that population be P,
thus X = P (updating X for next day) and we remove that element from multiset
(because this country will be country cured on that day) and we increment the
total days required by one.
b) else (hwen no such value in multiset exits in range [x,2x] ) then again we will
go to cure the country with largest population present. X will be updated to 2*X
(because today we can use 2*X cures to cure the most populated country), thus
X = X*2, we also update the population of that country adter doubling at end of
the day.
Note : Also before doing all these tasks i also chek whether my multiset is empty or not.
I have also attached explanation with sample testases.
Testcase 1 :
when X = 1, N =5 and countryâs populations are 10, 20, 30, 40, 50
Deliver Or not the value of x will be doubled until you get a equal or the consecutive smaller country let me take the example from sample
3 10
1 20 110
On first day x is 10 now if we use it at 1 our next x will be 2 so we canât do that if we use 10 at 20 remaining infected people will be 10 and next x will be 20 and the next value will be 20 again because remaining infected people and cure gets double. So if you look closely I will give u a scenario in case of 20 last time we took two days to eliminate but what if we donât use the cure on first day now or 10 will increase to 20 and on second day it will cutt off the 20 once at all it took 2 days again. So, it doesnât matter you use the x Or not the days will remain the same.
Now if you try to solve x for 110 you will also observe that the scenario will be same in that case too and in all other cases. So, if you want to use x every time it wonât be wrong but if you donât use x and double it every time until you find equal and a previous consecutive value the scenario will also be same.
0 1 2 3
9 19 20 41
1.x=20 then a[2]>=20 a[2] cured , next x= 40
2.then 40<a[3] ; 40 used for a[3] but still not equal to population, next x=80
3.then 80>a[3], 41 used for a[3] next x= 82 ,a[3] cured
4. 82>a[1] ,used for a[1] , x=2*a[1]=38 ,a[1] cured
5.38>a[0], used for a[0], a[0] cured .
all country are cured now.
If we do not deliver the cures and wait for it to become 16, we can cure all 10 of them in a single day and thus x will be 20. It takes less number of days in this case if we assume that the number of cures will be doubled even if we do not deliver any of them.
If I assume x wonât be doubled if I donât deliver any cure:
we can cure 8 people of the first country and thus x will be 16. In this process, it takes more days.
I canât understand why we have to double the value of x after delivering 0 cures. (0*2 = 0)
The problem statement says,
Chef can supply twice the number of cures that were delivered (i.e. people that were cured) on the previous day. Chef cannot supply leftovers from the previous or any earlier day.
Definitely Iâm wrong as Iâm getting WA. But I want to understand.
but if you donât use x and double it every time until you find equal and a previous consecutive value the scenario will also be same.
