## Why I m getting RE for 12049- Just Prune The List

Moderator: Board moderators

### Why I m getting RE for 12049- Just Prune The List

#include<stdio.h>
#define MAX 100009
int main()
{
long test,arraya[MAX],arrayb[MAX],a,b,p,max,count,i;
scanf("%lld",&test);
while(test)
{
scanf("%lld %lld",&a,&b);
for(i = 1; i <=a; i++)
{
scanf("%lld",&p);
arraya[p]++;
}
for(i = 1; i <=b; i++)
{
scanf("%lld",&p);
arrayb[p]++;
}

if(a>=b)
max=b;
else
max=a;
count=0;

for(i=1;i<=max;i++)
{
if(arraya[i]>=arrayb[i])
count+=(arraya[i]-arrayb[i]);
else
count+=(arrayb[i]-arraya[i]);
}
printf("%lld\n",count);

test--;
}

return 0;
}
rahian
New poster

Posts: 5
Joined: Wed Jul 30, 2008 3:27 am
Location: CUET

### Re: Why I m getting RE for 12049- Just Prune The List

Read the problem statement and input carefully..........@ Each integers in the input is 32 bit signed integer!!!!!!!!!!!!

You have defined MAX only 100009............when executing arraya[p]++ or arrayb[p]++ it occurs array overflow for those cases where the value of p is more than 100009.......
for example.........when p=234765897, your defined array does not have this index that's why u r getting runtime error...........try to find another method to solve this problem........Best of luck.......
ferd@u\$
New poster

Posts: 4
Joined: Fri Jul 16, 2010 2:02 pm
Location: CUET

### Re: Why I m getting RE for 12049- Just Prune The List

Hi, ferd@ud\$ is right..
u can use data structure map.......bcz the value r so large......
robot
New poster

Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Re: Why I m getting RE for 12049- Just Prune The List

thank u friend......... I hv solved and AC
rahian
New poster

Posts: 5
Joined: Wed Jul 30, 2008 3:27 am
Location: CUET

### Why wrong answer? Can anyone help with critical inputs?

#include<stdio.h>
#define MAXARRAY 10000
int mergesort(long int a[], int low, int high);
int main(){
int N,M,T,i,j,count;
long int first[MAXARRAY],second[MAXARRAY];
scanf("%d",&T);
for(i=0;i<T;i++){
count=0;
scanf("%d %d",&N,&M);
for(j=0;j<N;++j){
scanf("%ld",&first[j]);
}
mergesort(first,0,N-1);
for(j=0;j<M;++j){
scanf("%ld",&second[j]);
}
mergesort(second,0,M-1);
while(M>=0&&N>=0){
if(first[N]>second[M]){
--N;
++count;
}
else if(second[M]>first[N]){
--M;
++count;
}
else{
--M;
--N;
}
}
count+=M+N+2;
printf("%d\n",count);
}
return 0;
}
int mergesort(long int a[], int low, int high){
int i = 0;
int length = high - low + 1;
int pivot = 0;
int merge1 = 0;
int merge2 = 0;
long int working[MAXARRAY];

if(low == high)
return 0;

pivot = (low + high) / 2;

mergesort(a, low, pivot);
mergesort(a, pivot + 1, high);

for(i = 0; i < length; i++)
working[i] = a[low + i];

merge1 = 0;
merge2 = pivot - low + 1;

for(i = 0; i < length; i++) {
if(merge2 <= high - low){
if(merge1 <= pivot - low){
if(working[merge1] > working[merge2])
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
}
else
a[i + low] = working[merge2++];
}
else
a[i + low] = working[merge1++];
}
return 0;
}
milton_iut
New poster

Posts: 2
Joined: Tue Jun 19, 2012 8:30 pm

### Re: Why I m getting RE for 12049- Just Prune The List

Doesn't match the sample I/O.
brianfry713
Guru

Posts: 1870
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Why I m getting RE for 12049- Just Prune The List

Got AC. Just needed to decrement the value of M and N by 1 before entering into the while loop.
milton_iut
New poster

Posts: 2
Joined: Tue Jun 19, 2012 8:30 pm

### Re: Why I m getting RE for 12049- Just Prune The List

Code: Select all
`#include <cstdio>#include <vector>using namespace std;int main(){    int T;    //freopen("in-12049.txt","r",stdin);    //freopen("O U T.txt","w",stdout);    scanf("%d",&T);    while(T--){        long long n, m, tmp;        long long fr[100010], sn[100010];        scanf("%lld %lld",&n,&m);        for(long i=0 ; i<n ; i++){            scanf("%lld",&fr[i]);        }        for(long i=0 ; i<m ; i++){            scanf("%lld",&sn[i]);        }        long long tt=0,num=0, mid=0;        if(n>m){                mid=(n/2);                for(long i=0 ; i<m ; i++)                {                        for(long j=0 ; j<=mid ; j++)                        {                                if( sn[i]==fr[j] && j<mid && fr[j]!=4294967297 )                                {                                    fr[i]=4294967297;                                    tt++;                                    break;                                }                                else if(sn[i]==fr[(n-1)-j] && fr[(n-1)-j]!=4294967297)                                {                                    fr[(n-1)-j]=4294967297;                                    tt++;                                    break;                                }                        }                }        }        else{            mid=(m/2);                for(long i=0 ; i<n ; i++)                {                        for(long j=0 ; j<=mid ; j++)                        {                                if(fr[i]==sn[j] && j<mid  && sn[j]!=4294967297 )                                {                                    sn[j]=4294967297;                                    tt++;                                    break;                                }                                else if(fr[i]==sn[(m-1)-j] && sn[(m-1)-j]!=4294967297 )                                {                                    sn[(m-1)-j]=4294967297;                                    tt++;                                    break;                                }                        }                }        }        num+=n-tt;        num+=m-tt;        printf("%lld\n",num);    }    return 0;}`
uvasarker
Learning poster

Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm

### Re: Why I m getting RE for 12049- Just Prune The List

4294967297 is larger than a 32bit signed integer can handle.
brianfry713
Guru

Posts: 1870
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Why I m getting RE for 12049- Just Prune The List

Guru
Please, give me some critical input / output.
uvasarker
Learning poster

Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm

### Re: Why I m getting RE for 12049- Just Prune The List

Input:
Code: Select all
`11 112`
AC output: 2
brianfry713
Guru

Posts: 1870
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA