BENCHP - Editorial

ahhh my bad !
thank you !

Thanks a lot, it helped :smiley:. I was also facing the same issue.

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.

Any idea why this failed the second task?

https://www.codechef.com/viewsolution/45612811

The main solution is from line 66 to 85.

Your Code, ACfied
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vpll = vector<pll>;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(vector<bool> v) {bool first = true; cerr << "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) {if (!first) {cerr << ", ";} first = false; __print(v[i]);} cerr << "}";}
template <size_t N>
void __print(bitset<N> bs) {string res = "<"; for (size_t i = 0; i < N; i++) {res += static_cast<char>('0' + bs[i]);} res += '>'; cerr << res;}
template<typename T>
void __print(const T &x) {int j = 0; cerr << "{"; for (auto &i: x) cerr << (j++ ? ", " : ""), __print(i); cerr << "}";}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << "("; __print(x.first); cerr << ", "; __print(x.second); cerr << ")";}
template <typename A, typename B, typename C>
void __print(const tuple<A, B, C> t) {cerr << "("; __print(get<0>(t)); cerr << ", "; __print(get<1>(t)); cerr << ", "; __print(get<2>(t)); cerr << ")";}
template <typename A, typename B, typename C, typename D>
void __print(const tuple<A, B, C, D> t) {cerr << "("; __print(get<0>(t)); cerr << ", "; __print(get<1>(t)); cerr << ", "; __print(get<2>(t)); cerr << ", "; __print(get<3>(t)); cerr << ")";}
void _print() {cerr << " ]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifndef ONLINE_JUDGE
#define deb(...) cerr << "~ [ " << #__VA_ARGS__ << " ] => [ "; _print(__VA_ARGS__)
#define debn(...) cerr << "~ [ "; _print(__VA_ARGS__)
#else
#define deb(...)
#define debn(...)
#endif

#define ALL(DS) (DS).begin(), (DS).end()
#define PB push_back
#define EB emplace_back
#define SZ(DS) (int)((DS).size())
#define fo(ITER, LO, UP) for (ITER = (LO); ITER < (UP); ++ITER)
#define foi(ITER, LO, UP) for (int ITER = (LO); ITER < (UP); ++ITER)
#define foll(ITER, LO, UP) for (ITER = (ll)(LO); ITER < (ll)(UP); ++ITER)
#define folli(ITER, LO, UP) for (ll ITER = (ll)(LO); ITER < (ll)(UP); ++ITER)
#define iter(ITER, DS) for (auto &ITER: DS)

const int MOD = 1000000007;
const int INF = 1e9 + 5;

void init() {}

void solve(int testcase) {
    ll n, t, r, temp; cin >> n >> t >> r;

    map<ll, ll> w;
    foi(i, 0, n) {
        cin >> temp;
        w[temp]++;
    }

    ll sum = r;
    iter(x, w) {
        sum += x.first * ((x.second / 2) * 2);
        if (sum >= t) {
            cout << "YES\n";
            return;
        }
    }

    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    init();
    int T; cin >> T;
    for(int t = 1; t <= T; ++t) {
        solve(t);
    }
}


What are you missing?

map<ll, ll> w;

shall be used instead of

map<int, int> w;
1 Like

But arenā€™t all the numbers in the int range? I did use lls everywhere elseā€¦ Is this some C++ thing or am I just being dumb?

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.

2 Likes

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ā€;

}
return 0;

}

Thanks a lot.

Better to use long long rather than int.

Iā€™m surprised my solution got accepted. I only considered the even count weights and didnā€™t add any weights with odd count.
https://www.codechef.com/viewsolution/45583410

1 Like

Canā€™t the chef place 90 and 10 on the left and 100 on the right?

I had the same problem. Apparently using long long and an if condition before the loop solves it.

Open Code for V1

Alternatively, decreasing the value of w instead of increasing wr, solves the issue.

Open Code for V2

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.