10252 - Common Permutation

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

Moderator: Board moderators

kier.guevara
New poster
Posts: 30
Joined: Thu Jul 19, 2012 11:24 pm

Re: 10252 - Common Permutation

Post by kier.guevara » Mon Jan 21, 2013 11:05 am

Code: Select all

Code Removed After AC!
Last edited by kier.guevara on Mon Jan 21, 2013 3:14 pm, edited 1 time in total.

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

Re: 10252 - Common Permutation

Post by BUET » Mon Jan 21, 2013 1:13 pm

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
New poster
Posts: 30
Joined: Thu Jul 19, 2012 11:24 pm

Re: 10252 - Common Permutation

Post by kier.guevara » Mon Jan 21, 2013 3:13 pm

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

alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Location: BUBT,Dhaka, Bangladesh
Contact:

Re: 10252 - Common Permutation

Post by alimbubt » Tue Feb 26, 2013 8:13 am

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
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

( 10252 ) What's the diffrence between the two codes?

Post by MewCatcher » Sun Mar 10, 2013 7:34 pm

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
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

Re: ( 10252 ) What's the diffrence between the two codes?

Post by MewCatcher » Tue Mar 12, 2013 6:01 pm

:( Who know the answer? Please!~

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

Re: ( 10252 ) What's the diffrence between the two codes?

Post by brianfry713 » Tue Mar 12, 2013 10:23 pm

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;
}
Check input and AC output for thousands of problems on uDebug!

MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

Re: ( 10252 ) What's the diffrence between the two codes?

Post by MewCatcher » Wed Mar 13, 2013 3:12 am

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

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

Re: ( 10252 ) What's the diffrence between the two codes?

Post by brianfry713 » Wed Mar 13, 2013 6:17 am

Also remove this line:
if( a[ 0 ] == '\0' ) break;
Check input and AC output for thousands of problems on uDebug!

MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

Re: ( 10252 ) What's the diffrence between the two codes?

Post by MewCatcher » Wed Mar 13, 2013 8:17 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: ( 10252 ) What's the diffrence between the two codes?

Post by brianfry713 » Wed Mar 13, 2013 9:43 pm

Maybe there is a blank line in the judge's input. Maybe there isn't a newline at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

Re: ( 10252 ) What's the diffrence between the two codes?

Post by MewCatcher » Thu Mar 14, 2013 1:15 pm

Got it!
Thank you, very much.

samg
New poster
Posts: 1
Joined: Thu Apr 24, 2014 12:32 am

Re: 10252 - Common Permutation

Post by samg » Thu Apr 24, 2014 12:44 am

BUET wrote: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
New poster
Posts: 10
Joined: Sat Sep 06, 2014 12:44 pm

Re: 10252 - Common Permutation

Post by nasim.ruet » Tue Sep 23, 2014 3:34 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10252 - Common Permutation

Post by brianfry713 » Tue Sep 23, 2014 8:59 pm

Yes I agree BUET's post is incorrect.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 102 (10200-10299)”