10252 - Common Permutation

[kier.guevara]

Code: Select all

Code Removed After AC!

[BUET]

Sample input:

Code: Select all

aasgfndfdsndsbfngferdsfnshhgbshehbnbniavnnbroaegbwaibhubdskeienvbffnhrr
ufiuewgbvsusiuvnjakaslcvnirghbnvlodsjdvsbbfsoohbvrrbvdsdfsvdsundvssaamsmdn

My accepted program returns:

Code: Select all

aaaabbbbbbbbdddddeeeffffffggghhhhiiiknnnnnnnnnorrrsssssssuvvw

Your program returns:

Code: Select all

aaaabbbbbbdddddefffgghhiiiknnnnnorrrsssssssuvvw

See the output for letter 'e', 'f', 'g'

[kier.guevara]

Thanks Shadek for the input and output! I now know what's wrong with my code!

[alimbubt]

My Accepted code gives the following input output......
Sample Input:

Code: Select all

i like programming
do u love me
bangladeshi
me gan rsgb
uasfgi ksufhk sfhj
ahdj shgvasa
aaaaa ssssss dddd ffff
aa dd fff d
np pn
pp
alim
mila
shipu alim anjan
sufi timekiller mr energy

Sample Output:

Code: Select all

  elmo
abegns
 aghhjss
   aadddfff
pp
ailm
  iilmnsu

[MewCatcher]

As the title,

Wrong Answer C code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int cmp( const void *a, const void *b )
{
    return *(char *)a - *(char *)b;
}

char a[ 1001 ], b[ 1001 ];

int main( )
{
    while( 1 ) {
        /* read */
        gets( a ); gets( b );
        if( a[ 0 ] == '\0' ) break;
        
        /* sort */
        int L_a = strlen( a ), L_b = strlen( b );
        qsort( a, L_a, sizeof( char ), cmp );
        qsort( b, L_b, sizeof( char ), cmp );
        
        /* search */
        int i = 0, j = 0;
        while( i < L_a && j < L_b ) {
            if( a[ i ] == b[ j ] ) {
                printf( "%c", a[ i ] );
                i++; j++;
            }
            else {  
                if( a[ i ] < b[ j ]) i ++;  
                else j ++;
            }
        }
        printf( "\n" );
    }
    return 0;
}

AC C++ code:

Code: Select all

#include <iostream>
#include <algorithm>
	
using namespace std;
	
bool cmp(char a, char b)
{
	return a < b;
}
	
int main(int ac, char *av[])
{
	string a;
	string b;
	
	while (getline(cin, a), getline(cin, b))
	{
		sort(&a[0], &a[0] + a.length(), cmp);
		sort(&b[0], &b[0] + b.length(), cmp);
		
		int i = 0;
		int j = 0;
		while (i < a.length() && j < b.length())
		{
			if (a[i] == b[j])
			{
				cout << a[i];
				i++;
				j++;
			}
			else
			{
				if (a[i] < b[j])
					i++;
				else
					j++;
			}
		}
		cout << endl;
	}
	return 0;
}

So, what's the difference?

[MewCatcher]

Who know the answer? Please!~

[brianfry713]

You should check the return value of gets to see if it equals NULL.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int cmp( const void *a, const void *b )
{
    return *(char *)a - *(char *)b;
}

char a[ 1001 ], b[ 1001 ];

int main( )
{
    while(gets(a) != NULL && gets(b) != NULL) {
        /* read */
        if( a[ 0 ] == '\0' ) break;
       
        /* sort */
        int L_a = strlen( a ), L_b = strlen( b );
        qsort( a, L_a, sizeof( char ), cmp );
        qsort( b, L_b, sizeof( char ), cmp );
       
        /* search */
        int i = 0, j = 0;
        while( i < L_a && j < L_b ) {
            if( a[ i ] == b[ j ] ) {
                printf( "%c", a[ i ] );
                i++; j++;
            }
            else { 
                if( a[ i ] < b[ j ]) i ++; 
                else j ++;
            }
        }
        printf( "\n" );
    }
    return 0;
}

[MewCatcher]

Thx, I've tried that, but still WA why?

[brianfry713]

Also remove this line:
if( a[ 0 ] == '\0' ) break;

[MewCatcher]

Got AC!
But what's the reason? I want to know!

And if I change into this.

Code: Select all

......
while( fgets( a, 1001, stdin ) != NULL && fgets( b, 1001, stdin ) != NULL ) {
a[ strlen( a ) - 1 ] = '\0'; b[ strlen( b ) - 1 ] = '\0';
......

WA, why?

[brianfry713]

Maybe there is a blank line in the judge's input. Maybe there isn't a newline at the end of the last line.

[MewCatcher]

Got it!
Thank you, very much.

[samg]

Sample input:

Code: Select all

aasgfndfdsndsbfngferdsfnshhgbshehbnbniavnnbroaegbwaibhubdskeienvbffnhrr
ufiuewgbvsusiuvnjakaslcvnirghbnvlodsjdvsbbfsoohbvrrbvdsdfsvdsundvssaamsmdn

My accepted program returns:

Code: Select all

aaaabbbbbbbbdddddeeeffffffggghhhhiiiknnnnnnnnnorrrsssssssuvvw

Your program returns:

Code: Select all

aaaabbbbbbdddddefffgghhiiiknnnnnorrrsssssssuvvw

See the output for letter 'e', 'f', 'g'

What permutation of [1] is a subsequence of [2]? There is just one "e" in [2]. What am I getting wrong?

[1] aaaabbbbbbbbdddddeeeffffffggghhhhiiiknnnnnnnnnorrrsssssssuvvw
[2] ufiuewgbvsusiuvnjakaslcvnirghbnvlodsjdvsbbfsoohbvrrbvdsdfsvdsundvssaamsmdn

My program got AC and returns just like [3], the original problem (that drove my here) was with an empty input line ( didn't realized this possibility when first reading the problem description).

[3] aaaabbbbbbdddddefffgghhiiiknnnnnorrrsssssssuvvw

[nasim.ruet]

Code: Select all

I also think as Mr. samg .
Mr. BUET may mistake.
My AC program returns this : 

input

Code: Select all

aasgfndfdsndsbfngferdsfnshhgbshehbnbniavnnbroaegbwaibhubdskeienvbffnhrr
ufiuewgbvsusiuvnjakaslcvnirghbnvlodsjdvsbbfsoohbvrrbvdsdfsvdsundvssaamsmdn

output

Code: Select all

aaaabbbbbbdddddefffgghhiiiknnnnnorrrsssssssuvvw

[brianfry713]

Yes I agree BUET's post is incorrect.