I have corrected time complexity, and you are right my code is giving wrong answer to the test case given by you. Since I’m a beginner, I thought that the code was right as it got AC. Now, I’ve made a change in my code, which is passing the testcase given by you. You can review it and tell me if there is a problem still in my code.
Thanks for that! It passed. But I do not understand how, with the given constraints, it should matter. If all the elements are the same, even then the value of the map would very well be within the limits of int, which is the size of the array. Any leads? Seems like the test cases were weird.
Consider the case when you have to lift at least 10 Units.
Now, the weight you already have is 8 units.
The number of additional weights you can add is 10^5 and all of them are 10^5. In your approach, there is only one element in the map., viz., 10^5. You are adding the product to a variable.
have += i * w[i];
The R.H.S is 10^{10}. It is automatically typecasted to Int which will result in overflow. Hence WA.
Hey bro I used the same logic as yours that finding the pairs of same number but I did it with array like I first sorted it then found out the pairs from start till end, but I did’nt understand your working with maps like how did you learn and implement them?
My code: #include <bits/stdc++.h>
using namespace std; #define MOD 1000000007 #define ll long long
int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
ll int n, w, wr;
cin>>n>>w>>wr;
ll int a[n];
for(int i=0; i<n; i++)
{
cin>>a[i];
}
sort(a, a+n);
if(wr>=w)
{
cout<<“YES\n”;
continue;
}
//10 10 10 10 10 10
for(int i=0; i<n; i++)
{
if(a[i]==a[i+1]) {
wr+=2*a[i];
i++;
}
}
if(wr>=w) cout<<“YES\n”;
else cout<<“NO\n”;
this is my solution … hope helps … case if odd u can use x-1 thats even weights
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;std::cin >> t;
while(t--){
long long int n,w,wr;std::cin >> n>>w>>wr;
unordered_map<long long int,long long int>weights;
for(long long int i=0 ;i<n;i++){
long long int x;std::cin >> x;weights[x]++;
}
w-=wr;
for(auto it=weights.begin() ; it!=weights.end() ; it++){
if(it->second % 2 == 0){
long long int total = it->first * it->second;
w-=total;
}
else{
long long int total = it->first * (it->second-1);
w-=total;
}
if(w<=0){
break;
}
}
if(w<=0){
std::cout << "YES" << std::endl;
}
else{
cout<<"NO\n";
}
}
return 0;
}
Lets say the weight of rod is Wr and he is satisfied at weight Wsatis and lets say the weights we put on both side being equal as Wex then the question says
Wr + 2Wex > = Wsatis
so we want to find if its possible to find two pair of array elements whose sum are equal (40+60 = 50+50) for this to satisfy.
Its not necessary that every weight in the pair occur two times
(40+60=60+40). But the official solution solve this problem on the basis of this. Which has flaw in his logic.
. I was also facing the same issue.