BENCHP - Editorial

I had also tried the same approach, but not getting AC.
Anyone please tell me where I am wrong.

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

public static void main(String[] args) throws IOException {
	BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
	int T = Integer.parseInt(sc.readLine());
	for(int  i =0 ;i <T ;i++) {
		StringTokenizer st = new StringTokenizer(sc.readLine());
		int N = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int Wr = Integer.parseInt(st.nextToken());
		
		
		Set<Integer> h = new HashSet<Integer>();
		StringTokenizer st1 = new StringTokenizer(sc.readLine());
		int[] a = new int[N];
		ArrayList<Integer> arr = new ArrayList<Integer>();
		int sum = 0 ;
		int z = 0 ;
		for(int j = 0 ; j<N ; j++) {
			a[j] = Integer.parseInt(st1.nextToken());
			if(h.contains(a[j])) {
				arr.add(a[j]);
				sum += arr.get(z);
				h.remove(a[j]);
				z++;
			}
			else {
				h.add(a[j]);
			}
		}
		
		if(W<=Wr) {
			System.out.println("YES");
		}
		
		else {
		
		int s = W-Wr;
		System.out.println(sum);
		if(s<=(sum*2)) {
			System.out.println("YES");
		}
		else {
			System.out.println("NO");
		}
		}
	}

can anyone tell me why this is giving me a wrong verdict !?

but these input-variables are in int size limit i.e. less than 10^6
what’s the reason behind WA?

This particular line is causing the error

map<int,int> m;

replace this with

map<ll,ll> m;

rest is fine… :innocent:

share your code here

i dont think that should cause an error…
he has used map with <int,int> … It has to be <long long int, long long int>

got my mistake. Actually yesterday i *ucked my lunchtime. I miss read the question and forgot about the word , “at least” mentioned in the question. I solved it for exactly W weight . you can see my code for that variation here. I considered that if the weigh we want to add is an odd number then we cannot perform the operation. B ut at last moment i read it as at least mentioned in the question and solved it for that part.

1 Like

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