12049 - Just Prune The List

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
rahian
New poster
Posts: 5
Joined: Wed Jul 30, 2008 3:27 am
Location: CUET
Contact:

12049 - Just Prune The List

Post by rahian » Thu Aug 11, 2011 11:42 pm

#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>=arrayb)
count+=(arraya-arrayb);
else
count+=(arrayb-arraya);
}
printf("%lld\n",count);

test--;
}

return 0;
}

ferd@u$
New poster
Posts: 4
Joined: Fri Jul 16, 2010 2:02 pm
Location: CUET
Contact:

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

Post by ferd@u$ » Fri Aug 19, 2011 10:34 pm

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.......

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

Post by robot » Mon Aug 22, 2011 1:49 pm

Hi, ferd@ud$ is right..
u can use data structure map.......bcz the value r so large...... :)

rahian
New poster
Posts: 5
Joined: Wed Jul 30, 2008 3:27 am
Location: CUET
Contact:

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

Post by rahian » Wed Sep 28, 2011 12:22 am

thank u friend......... I hv solved and AC

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

Why wrong answer? Can anyone help with critical inputs?

Post by milton_iut » Tue Jun 19, 2012 8:41 pm

#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 = 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;
}

brianfry713
Guru
Posts: 5947
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

Post by brianfry713 » Tue Jun 19, 2012 11:33 pm

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

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

Post by milton_iut » Wed Jun 20, 2012 8:58 am

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

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

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

Post by uvasarker » Fri Jul 13, 2012 1:17 pm

I am getting W A. Why? please help me..

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;
}


brianfry713
Guru
Posts: 5947
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

Post by brianfry713 » Tue Jul 17, 2012 11:55 pm

4294967297 is larger than a 32bit signed integer can handle.
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

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

Post by uvasarker » Wed Jul 18, 2012 9:37 am

Guru
Please, give me some critical input / output.

brianfry713
Guru
Posts: 5947
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

Post by brianfry713 » Thu Jul 19, 2012 3:03 am

Input:

Code: Select all

1
1 1
1
2
AC output: 2
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
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

Post by brianfry713 » Fri Jan 10, 2014 10:09 pm

Code: Select all

1
2 1
1 1
2
AC output 3
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

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

Post by uDebug » Sat Jan 11, 2014 7:26 am

brianfry713,

Thanks so much for the test cases. Those were super useful.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

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

Post by uDebug » Sat Jan 11, 2014 7:29 am

I'm enclosing some input / output that I found useful during testing / debugging. Again, a special shout out to brianfry713 for his help.

Input:

Code: Select all

11
5 5
1 2 3 2 1
1 2 5 2 3
5 10
1 2 3 4 5
6 7 8 9 10 11 12 13 14 15
1 1
1
2
10 5
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15
7 6
8 8 8 7 1 2 2
2 1 8 8 -8 2 
6 6
4967297 -4967297 0 1 2 3
3 0 4967297 1 2 -4967297
1 5
66
4 2 1 3 66
5 1
4 2 1 3 66
66
2 2
1 2
1 1
7 1
99 99 99 99 99 99 99 
2
1 5
28956
11 11 11 11 11
AC Output:

Code: Select all

2
15
2
15
3
0
4
4
2
8
6
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 12049 - Just Prune The List

Post by anacharsis » Sun Jun 07, 2015 6:30 pm

This one is a trail of tears if you are doing it in java.
And it's only because there is a lot of input that takes a while to parse.
I appended an optimized input reader class to help level the playing field with the c/c++ people.
This input reader can read the test data in about 0.6 seconds, which should give you plenty of time to solve the problem in under 1 second.

Code: Select all

	static class InputReader {
		private BufferedReader reader;
		private int idx;
		private String next;
		private int len;

		public InputReader( InputStream stream ) {
			reader = new BufferedReader( new InputStreamReader( stream ) );
		}

		public void next() throws IOException {
			next = reader.readLine().trim();
			idx = 0;
			len = next.length();
		}

		public int nextInt() throws IOException {
			if ( next == null || idx >= len ) {
				next();
			}

			while ( idx < len && next.charAt( idx ) == ' ' ) {
				++idx;
			}

			int num = 0;
			char ch;
			boolean neg = false;
			while ( idx < len && ( ch = next.charAt( idx ) ) != ' ' ) {
				if ( ch == '-' ) {
					neg = true;
				} else {
					num *= 10;
					num += ch - 48;
				}

				++idx;
			}

			return neg ? -num : num;
		}
	}


Post Reply

Return to “Volume 120 (12000-12099)”