10252 - Common Permutation

[sh415]

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]

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

[Ivan Goroun]

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

[jcvb]

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!

[SeineRiver]

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]

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

[Asma_ju]

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]

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.

[plamplam]

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

[plamplam]

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

[mgavin2]

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;
}



[brianfry713]

fgets includes '\n' in the copied string.

[mgavin2]

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 :\

[kier.guevara]

Code Removed After AC!

[মেহেদী সবুজ]

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