12049 - Just Prune The List
Moderator: Board moderators
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>=arrayb)
count+=(arraya-arrayb);
else
count+=(arrayb-arraya);
}
printf("%lld\n",count);
test--;
}
return 0;
}
#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;
}
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.......
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.......
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......![:)](./images/smilies/icon_smile.gif)
u can use data structure map.......bcz the value r so large......
![:)](./images/smilies/icon_smile.gif)
Re: Why I m getting RE for 12049- Just Prune The List
thank u friend......... I hv solved and AC
-
- New poster
- Posts: 2
- Joined: Tue Jun 19, 2012 8:30 pm
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 = 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;
}
#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;
}
-
- 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
Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 2
- Joined: Tue Jun 19, 2012 8:30 pm
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.
-
- 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
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;
}
-
- 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
4294967297 is larger than a 32bit signed integer can handle.
Check input and AC output for thousands of problems on uDebug!
-
- 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
Guru
Please, give me some critical input / output.
Please, give me some critical input / output.
-
- 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
Input:AC output: 2
Code: Select all
1
1 1
1
2
Check input and AC output for thousands of problems on uDebug!
-
- 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
Code: Select all
1
2 1
1 1
2
Check input and AC output for thousands of problems on uDebug!
Re: Why I m getting RE for 12049- Just Prune The List
brianfry713,
Thanks so much for the test cases. Those were super useful.
Thanks so much for the test cases. Those were super useful.
Re: Why I m getting RE for 12049- Just Prune The List
I'm enclosing some input / output that I found useful during testing / debugging. Again, a special shout out to brianfry713 for his help.
Input:
AC Output:
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
Code: Select all
2
15
2
15
3
0
4
4
2
8
6
-
- Learning poster
- Posts: 69
- Joined: Mon Feb 09, 2015 1:56 am
Re: 12049 - Just Prune The List
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.
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;
}
}