BENCHP - Editorial

grt :smiley:

Because you didn’t use long long int in map, I ran into the same problem. I would suggest you to change data type of map to unordered_map<long long int,long long int>. then it will pass

1 Like

i did something else and it’s cool we don’t need to count the frequency.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,weight,wr;
        cin>>n>>weight>>wr;
        int arr[n];
        for(int i=0; i<n; i++) cin>>arr[i];
        if(wr>=weight) {
            cout<<"YES"<<endl;
            continue;
        }
        sort(arr,arr+n);
        ll reqWeight = weight-wr;
        ll l=0,r=0;
        bool answer = false;
        for(int i=0; i<n; i++){
            if(l==r && (l+r)>=reqWeight){
                answer = true;
                break;
            }
            if(l<r) l+=arr[i];
            else r+=arr[i];
            if(l==r && (l+r)>=reqWeight){
                answer = true;
                break;
            }
        }
        if(answer) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        
    }
    return 0;
}

Here is the code

The count variable in your code can go up to N \le 10^5 and wgt[i] values can also be up to 10^5 so when you multiply both these entities in this statement.
image
Since both of them are integers so the result is also an integer but its value can be up to 10^5 \times 10^5=10^{10} which is leading to an overflow.
check this changing wgt[i] to long long is sufficient.

3 Likes
import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		Reader sc = new Reader();
		int t=sc.nextInt();
		while(t-- >0){
		    int n=sc.nextInt();
		    int w=sc.nextInt();         //satisfied weight
		    int wr=sc.nextInt();        //rod weight
		    int[] arr=new int[n];
		    for(int i=0;i<n;i++){
		        arr[i]=sc.nextInt();
		    }
		    Arrays.sort(arr);
		    int temp=wr;
		    
		    if(temp<w){
		        if(n%2==0){
		            for(int i=0;i<n-1;i=i+2){
		            if(arr[i]==arr[i+1]){
		                temp=temp+arr[i]+arr[i+1];
		            }
		            if(temp>=w){
		                System.out.println("YES");
		                break;
		            }
		        }
		        }else{
		            for(int i=1;i<n-1;i=i+2){
		            if(arr[i]==arr[i+1]){
		                temp=temp+arr[i]+arr[i+1];
		            }
		            if(temp>=w){
		                System.out.println("YES");
		                break;
		            }
		        }
		        }
		    }else{
		        System.out.println("YES");
		    }
		    if(temp<w){
		        System.out.println("NO");
		    }
		}
	}
}

LOL, why is your code failing for this test case:

Input

1
3 9 7
1 2 2

Your Output

NO

Expected Output

YES

So, can we conclude that the test cases are weak?
@cubefreak777 what do you say about this (just an opinion)?

@rhythmvarshney time complexity of your code is N\log{N} because you are sorting the Array.

I am locking your code now.

Your so called O(N) code
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Reader sc = new Reader();
		int t=sc.nextInt();
		while(t-- >0){
		    int n=sc.nextInt();
		    int w=sc.nextInt();         //satisfied weight
		    int wr=sc.nextInt();        //rod weight
		    int[] arr=new int[n];
		    for(int i=0;i<n;i++){
		        arr[i]=sc.nextInt();
		    }
		    Arrays.sort(arr);
		    int temp=wr;
		    
		    if(temp<w){
		        for(int i=0;i<n-1;i=i+2){
		            if(arr[i]==arr[i+1]){
		                temp=temp+arr[i]+arr[i+1];
		            }
		            if(temp>=w){
		                System.out.println("YES");
		                break;
		            }
		        }
		    }else{
		        System.out.println("YES");
		    }
		    if(temp<w){
		        System.out.println("NO");
		    }
		}
	}
	static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
}

Does seem to be the case. Proposed solution by @rythmagarwal is incorrect.

I wrote this code and got 70/100 first subtask of 30 marks failed and the second passed, can someone figure out why is my solution partially accepted

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,w,wr;
cin>>n>>w>>wr;
int *arr=new int[n];
for(int i=0;i<n;i++)
{
cin>>*(arr+i);
}
sort(arr,arr+n);
long long ans=wr;
if(wr>=w)
{
cout<<“YES”<<endl;
}
else
{
for(int i=0;i<n;i=i+2)
{
if(arr[i]==arr[i+1])
{
ans=ans+(2*arr[i]);
}
if(ans>=w)
{
break;
}
}
if(ans>=w)
{
cout<<“YES”<<endl;
}
else
{
cout<<“NO”<<endl;
}
}
delete []arr;
}
}

1 Like

the code is incorrect ig… the corect answer should be “yes”

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.

Yes, your modified code still fails in the following test case.

Input

1
10 40 3
9 1 7 4 4 1 7 4 10 9

Expected Output

YES

Your Output

NO

@polmbil why are you adding weight of rod at each step when u get same weight
it should be only added once

thanks for clearing my doubt, Achintya! guys like you are the gem for community. :black_heart:

2 Likes

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