10252 - Common Permutation

Moderator: Board moderators

Re: 10252 - Common Permutation

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

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

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

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

Re: 10252 - Common Permutation

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

Posts: 10
Joined: Sun Dec 20, 2009 12:01 am

Re: 10252 - Common Permutation

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.
jcvb
New poster

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

Re: 10252 - Common Permutation

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
SeineRiver
New poster

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

Re: 10252 - Common Permutation

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

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

Re: 10252 - Common Permutation

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.
Asma_ju
New poster

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

Re: 10252 - Common Permutation

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.
zobayer
Experienced poster

Posts: 110
Joined: Tue May 06, 2008 2:18 pm

Re: 10252 - Common Permutation

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 . 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 ). So check for silly mistakes like this in your code.
Note : If the problem description is unclear then read the previous posts.
Best wishes
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster

Posts: 151
Joined: Fri May 06, 2011 11:37 am

Re: 10252 - Common Permutation

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 . 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 ). So check for silly mistakes like this in your code.
Note : If the problem description is unclear then read the previous posts.
Best wishes
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster

Posts: 151
Joined: Fri May 06, 2011 11:37 am

Re: 10252 - Common Permutation

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)#endiftypedef pair<int, int> point;typedef long long int64; //for claritytypedef vector<int> vi; //?typedef vector<point> vp; //?template<class T> void chmin(T &t, T f) { if (t > f) t = f; } //change mintemplate<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;}`
mgavin2
New poster

Posts: 21
Joined: Sat Jul 28, 2012 6:29 pm

Re: 10252 - Common Permutation

fgets includes '\n' in the copied string.
brianfry713
Guru

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

Re: 10252 - Common Permutation

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 :\
mgavin2
New poster

Posts: 21
Joined: Sat Jul 28, 2012 6:29 pm

Re: 10252 - Common Permutation

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

Posts: 29
Joined: Thu Jul 19, 2012 11:24 pm

Re: 10252 - Common Permutation

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
`aaaaaaaaaa`

Output:
Code: Select all
`aa`
Last edited by মেহেদী সবুজ on Mon Jan 21, 2013 9:32 am, edited 1 time in total.
মেহেদী সবুজ
New poster

Posts: 6
Joined: Tue Apr 03, 2012 2:34 pm

PreviousNext

Who is online

Users browsing this forum: No registered users and 1 guest