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

sh415
New poster
Posts: 13
Joined: Fri Nov 13, 2009 9:31 am
Location: JU

Re: 10252 - Common Permutation

Post by sh415 » Sun Sep 05, 2010 5:07 am

ExUCI wrote:Hi, I just got AC without caring about such cases with uppercases like aaAAAaaa or whatever and there is no such thing. And yes, LCD can be used, I used it but I gonna change it for the simpler alg now!!

I read too many posters for nothing :evil:
I m getting frequent WA.......
can U give some sample input outpe.........................................

sh415
New poster
Posts: 13
Joined: Fri Nov 13, 2009 9:31 am
Location: JU

Re: 10252 - Common Permutation

Post by sh415 » Sun Sep 05, 2010 5:11 am

I m getting frequent WA........
can u give some sample INPUT OUTPUT.............

Ivan Goroun
New poster
Posts: 10
Joined: Sun Dec 20, 2009 12:01 am

Re: 10252 - Common Permutation

Post by Ivan Goroun » Sat Feb 05, 2011 11:32 pm

Don't use cin, use cin.getline. A line of text is an input, so it could be more than 1 word.

jcvb
New poster
Posts: 4
Joined: Tue Feb 15, 2011 5:35 pm

Re: 10252 - Common Permutation

Post by jcvb » Tue Feb 15, 2011 5:37 pm

why did i get WA?
my code(ansi c):

Code: Select all

#include <stdio.h>
#include <stdlib.h>
int charcmp(char *i,char* j)
{
	if(*i>*j)return (1);
	if(*j>*i)return (-1);
	return 0;
}

main()
{	
	while (1){
		char a[1500]={0},b[1500]={0};
		char c;		
		int la=0,lb=0;
		int ia=0,ib=0;
		int i;
		gets(a);gets(b);
		if (!(a[0]&&b[0])) break;
		qsort(a,strlen(a),sizeof(char),charcmp);
		qsort(b,strlen(b),sizeof(char),charcmp);
		for (c='a';c<='z';c++){
			for (;a[ia]==c;ia++);
			for (;b[ib]==c;ib++);
			
			for(i=0;i<(((ia-la)<(ib-lb))?(ia-la):(ib-lb));i++)
				printf("%c",c);
			la=ia;lb=ib;				
		}
		printf ("\n");
	}	
	return 0;
}
thanks!
Last edited by jcvb on Wed Feb 16, 2011 4:04 pm, edited 2 times in total.

SeineRiver
New poster
Posts: 2
Joined: Mon Jan 24, 2011 8:00 am

Re: 10252 - Common Permutation

Post by SeineRiver » Wed Feb 16, 2011 9:06 am

Hi,

if you've tried to apply and resubmit whatever's been discussed in the last 9 pages and you are still reading this, meaning you haven't got AC. Here's my clarification:

1. There's absolutely nothing like UPPERCASE characters or blank, or whatsoever in the input. Only string of zero or more lowercase characters. Don't fall into this, the error must be somewhere else. (I felt into that myself)

2. My mistake is a funny one, I never put a end line after the last output, as I think it should not be there. So if you are doing that, simply put an end line after the last output.

Cheers

jcvb
New poster
Posts: 4
Joined: Tue Feb 15, 2011 5:35 pm

Re: 10252 - Common Permutation

Post by jcvb » Wed Feb 16, 2011 4:10 pm

oh, thanks. i got ac now..
i ignored the empty strings..

Asma_ju
New poster
Posts: 4
Joined: Sat Jun 11, 2011 9:20 am

Re: 10252 - Common Permutation

Post by Asma_ju » Fri Jun 17, 2011 2:29 pm

Code: Select all

for(i=0;i<sz;i++)
        cout<<v[i];
        cout<<""<<endl;
i used a vector to contain the character of the commom sequence.After printing all character from the vector i print a nul character "" as shown in the code and got ACCEPTD.So every one can try if you cant found any other problem in your code.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 10252 - Common Permutation

Post by zobayer » Sat Jun 18, 2011 12:12 pm

Asma_ju wrote:

Code: Select all

for(i=0;i<sz;i++)
        cout<<v[i];
        cout<<""<<endl;
i used a vector to contain the character of the commom sequence.After printing all character from the vector i print a nul character "" as shown in the code and got ACCEPTD.So every one can try if you cant found any other problem in your code.
I do not think this is necessary.
You should not always say what you know, but you should always know what you say.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10252 - Common Permutation

Post by plamplam » Sun Jun 19, 2011 5:57 pm

Okay I must admit that this problem really pissed me off. For everyone getting WA continously, listen. The input description is perfectly fine, the judge data set is correct too (May be it was incorrect before I don't know, but it is sure fixed at the time Im writing this). The input will consist of only lowercase characters. Use gets or fgets instead of scanf, and it is not necessary to print the NULL character. However blank lines might be given as input and in that case make sure you program is printing ONLY a newline if the given string/s are empty. Another possible mistake could be the array size. If you used ch[1000], then if there are 1000 characters, then there would be no room left for the NULL character(My AC code had Array size 100000).

Finally, after checking all these cases, if you still get WA, then I hardly doubt that your algorithm is incorrect after going through all these posts. I made a very silly mistake. count1[50] and count2[50] is supposed to be integer type, but I mistakenly declared them as character array :x :x :x. It worked perfectly on my pc for all the inputs but the judge verdict was WA. I Got 6 WA because of that(and also partially because of this thread, as I found it very confounding and misleading :lol: ). So check for silly mistakes like this in your code.
Note : If the problem description is unclear then read the previous posts.
Best wishes :wink:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10252 - Common Permutation

Post by plamplam » Sun Jun 19, 2011 6:00 pm

plamplam wrote:Okay I must admit that this problem really pissed me off. For everyone getting WA continously, listen. The input description is perfectly fine, the judge data set is correct too (May be it was incorrect before I don't know, but it is sure fixed at the time Im writing this). The input will consist of only lowercase characters. Use gets or fgets instead of scanf, and it is not necessary to print the NULL character. However blank lines might be given as input and in that case make sure you program is printing ONLY a newline if the given string/s are empty. In case of inputs like "help" and "no", make sure your program prints a newline. Another possible mistake could be the array size. If you used ch[1000], then if there are rooms for 1000 characters, there would be no room left for the NULL character(My AC code had Array size 100000).

Finally, after checking all these cases, if you still get WA, then I hardly doubt that your algorithm is incorrect after going through all these posts. I made a very silly mistake. count1[50] and count2[50] is supposed to be integer type, but I mistakenly declared them as character array :x :x :x. It worked perfectly on my pc for all the inputs but the judge verdict was WA. I Got 6 WA because of that(and also partially because of this thread, as I found it very confounding and misleading :lol: ). So check for silly mistakes like this in your code.
Note : If the problem description is unclear then read the previous posts.
Best wishes :wink:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: 10252 - Common Permutation

Post by mgavin2 » Fri Oct 12, 2012 11:17 pm

I don't know how many times I can solve this problem by taking the minimum of the counted frequency of the characters in each string and printing those characters out in sorted order.
They all come back WA. There must be something wrong with the judge data because I've copied someone else's AC solution and got WA.

Here's my code so far. I began using C++ getline, and vectors. But some judge systems f* that up. So good old char*s for now.

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define DEBUG
//#undef DEBUG //uncomment this line to pull out print statements
#ifdef DEBUG
#define TAB '\t'
#define debug(a, end) cout << #a << ": " << a << end
#define dbg(end) end
#else
#define debug(a, end)
#define dbg(end)
#endif

typedef pair<int, int> point;
typedef long long int64; //for clarity
typedef vector<int> vi; //?
typedef vector<point> vp; //?
template<class T> void chmin(T &t, T f) { if (t > f) t = f; } //change min
template<class T> void chmax(T &t, T f) { if (t < f) t = f; } //change max

#define UN(v) SORT(v),v.erase(unique(v.begin(),v.end()),v.end())   
#define SORT(c) sort((c).begin(),(c).end())   
#define FOR(i,a,b) for (int  i=(a); i < (b); i++)    
#define REP(i,n) FOR(i,0,n)    
#define CL(a,b) memset(a,b,sizeof(a))
#define CL2d(a,b,x,y) memset(a, b, sizeof(a[0][0])*x*y)

/*global variables*/
char line1[1005], line2[1005];
int counted[50];
/*global variables*/

void dump()
{
    //dump data
}

int count_char(const char* s, const char& ltr)
{
    int count = 0;
    REP(i, strlen(s))
        if (s[i] == ltr) ++count;

    return count;
}

bool getInput()
{
    //get input
    if (feof(stdin)) return false;
    fgets(line1, 1005, stdin);
    if (feof(stdin)) return false;
    fgets(line2, 1005, stdin);
    
    /*
    string line;
    line.clear();
    REP(i, line1.length())
        if (isalpha(line1[i]) && islower(line1[i]))
            line += line1[i];

    line1 = line;
    line.clear();

    REP(i, line2.length())
        if (isalpha(line2[i]) && islower(line2[i]))
            line += line2[i];

    line2 = line;*/
    return true;
}

void process()
{

    //process input
    string line = line1;
    UN(line);
    REP(i, line.length())
    {
        counted[line[i]-'a'] = min(count_char(line1, line[i]), count_char(line2, line[i]));
    }
    REP(i, 26)
    {
        if (counted[i] != 0)
        {
            REP(j, counted[i])
            {
                printf("%c", ('a'+i));
            }
        }
    }
    
    printf("\n");
}

int main()
{
    while (getInput())
    {
        CL(counted, 0);
        process();

        /*CLEAR GLOBAL VARIABLES!*/

        /*CLEAR GLOBAL VARIABLES!*/
    }

    return 0;
}

all that matters is AC

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 Oct 16, 2012 1:16 am

fgets includes '\n' in the copied string.
Check input and AC output for thousands of problems on uDebug!

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: 10252 - Common Permutation

Post by mgavin2 » Wed Oct 17, 2012 9:47 pm

So I added

Code: Select all

line1[strlen(line1)-1] = 0;
before I make that line unique to count the common characters between the two lines, and got AC.
I love how on my machine, the output with that line looks exactly identical to the output without that line. Even a diff on the output reports no difference.
I also love how the judge system reports WA instead of PE.

Thanks for the help :\
all that matters is AC

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

Re: 10252 - Common Permutation

Post by kier.guevara » Sun Jan 20, 2013 7:17 pm

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

?????? ????
New poster
Posts: 7
Joined: Tue Apr 03, 2012 2:34 pm
Location: Manikgonj, Bangladesh

Re: 10252 - Common Permutation

Post by ?????? ???? » Mon Jan 21, 2013 9:20 am

kier.guevara wrote:i keep getting wa..i tried a lot of test cases but still WA..
what's wrong with my code?
Input:

Code: Select all

a
aaaa
aaaa
a
Output:

Code: Select all

a
a
Last edited by ?????? ???? on Mon Jan 21, 2013 9:32 am, edited 1 time in total.

Post Reply

Return to “Volume 102 (10200-10299)”