I had also tried the same approach, but not getting AC.
Anyone please tell me where I am wrong.
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…
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.
grt
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
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.
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.
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();
}
}
}
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;
}
}
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.