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