i tried to seek help from codechef forums but couldn't get any major help hence i posting my problem here !
the question is from July long challenge on codechef. problem link : https://www.codechef.com/JULY20B/problems/DRCHEF
code link : https://www.codechef.com/viewsolution/35869168
My code __
#include <iostream>
#include <set>
#include <iterator>
#include <stdio.h>
using namespace std ;
// it returns highest value present in multiset within the range [x,2x]
long int range_search (multiset <long int> S, long int X)
{
multiset<long int>::iterator it1, it2;
it1 = S.lower_bound(X);
it2 = S.upper_bound(2 * X);
long int ans;
if (it1 != it2)
{
--it2;
ans = *(it2);
}
else
{
ans = -1;
}
return ans;
}
// driver function
int main () {
int T;
cin>>T;
for (int k =0; k<T; k++){
int N ;
long int x ;
scanf("%d",&N) ;
scanf ("%ld",&x) ;
multiset<long int> s ; // storing country populations in multiset
multiset<long int>::iterator itr, itr1, itr2 ;
long int days =0;
long int val ;
long int temp ;
short int test = 0;
for (int i=0; i<N; i++){
scanf ("%ld",&val) ;
s.insert (val) ;
} // inserting population of N countries
/* multiset <long int> :: iterator itrrr;
cout << "\nThe multiset gquiz1 is : ";
for (itrrr = s.begin(); itrrr != s.end(); ++itrrr)
{
cout << '\t' << *itrrr;
}
cout << endl;
*/
while (test == 0){
// <0> if set is empty
if (s.size() == 0){ // <0.1>
test = 1;
break;
}
else { // <0.2>
// <1>
if (days == 0) { // <1.1> if its the first day
itr = s.end () ;
--itr ;
temp = *(itr) ;
if ( (temp - x)*2 > temp ) {
days++ ;
}
else {
s.erase(temp);
s.insert( (temp -x)*2 ) ;
days++ ;
}
test = 0 ;
continue ;
} //end of <1.1>
else { // <1.2> if it isnt first day we will do rangesearch [x,2x]
long int Z = range_search(s,x) ;
itr = s.end();
--itr;
temp = *(itr) ;
// <2>
if (Z != -1) { // <2.1> if some value found using rangesearch
if (Z == temp) { // when Z is equal to most populated country's value
days = days + s.size() ;
test = 0 ;
break;
}
else {
x = Z;
s.erase (Z) ;
days++ ;
test = 0 ;
continue;
}
} // end of <2.1>
else { // <2.2>
x = x*2;
if ( (temp - x)*2 > temp){
s.insert(temp) ;
}
else {
s.erase(itr) ;
s.insert ( (temp - x)*2) ;
}
days++ ;
test = 0 ;
continue ;
} // end of <2.2>
} // end of <1.2>
} // end of <0.2>
} // end of while loop
cout<<days<<endl ;
} // end of testcase loop
return 0;
}
Note : - I don't care whether my logic gives me wrong answer on edge cases or other test cases, i m particularly focusing to fix my code to simply execute my logic and i need help to fix my code errors as i m not getting the correct answers which my logic gives me on paper (meaning i have done some code blunder maybe overflow or something else)
my logic - i have created a multiset storing poppulations of every country in ascending order.
1.At any day (be it the first day of curing) if the number of cures available, X, is equal or greater than the largest element in multiset (country with the largest population) then the answer will be size of the multiset (as if we start from the last we can cure each country in one day)
2.IF X is less than last element of multiset then arises two cases :
2.A) if its the first day of curing - then simply use X to cure the country with highest population (last element of set), no need to update X (X remains same for the next day) and then update the countries population (after doubling) on which we used X cures. and we increment the tally of total days required by one.
2.B) else (when its not first day) - then we further check a condition hence two cases arise -
2.B.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.
2.B.b) else (when 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 after doubling at end of
the day.
Note : Also before doing all these tasks i also check whether my multiset is empty or not.
I have also attached explanation with sample test-cases.
Testcase 1 : when X = 1, N =5 and country’s populations are 10, 20, 30, 40, 50
Testcase 2 :
when X = 10, N = 3 and country’s populations are 1, 20, 110
