10252 - Common Permutation

[Amir Aavani]

I think your program get SigSeg somewhere and so, it got TLE. Try to replace memset with a for loop which set all the elements of an array. I am not sure about how memset in C/C++ do.

[Fali]

Why WA, so weird, please help me with this problem.

Here is my code:

Code: Select all

/*
  Common Permutation, Uva 10252
  Nephtali Garrido
*/
#include <cstdio>
#include <iostream>
using namespace std;

char v1[1000],v2[1000],x;
int cuan1[29],cuan2[29],c,c2;

int main()
{   while(cin>>v1>>v2)
    { for(c=0;c<29;c++)
       cuan1[c]=cuan2[c]=0;
      for(c=0;v1[c]!='\0';c++)
       cuan1[v1[c]-'a']++;
      for(c=0;v2[c]!='\0';c++)
       cuan2[v2[c]-'a']++;
      for(c=0;c<29;c++)
      { x=c+'a';
        if(cuan1[c]>=cuan2[c])
         for(c2=0;c2<cuan2[c];c2++)
          printf("%c",x);
        else
         for(c2=0;c2<cuan1[c];c2++)
          printf("%c",x);
      }
      printf("\n");
    }
    return 0;
}

If anyone knows why i got WA, please help me

[j_hines]

not sure if this will help, but i solved this problem a long time ago ... you can look at my source code if you want, it's at http://itnoise.com, you have to register though to see the solution repository. There are quite a few solutions there, and you can upload some of yours too if you like, it's a resource for students who are practising to participate in programming competitions.

cheers

[marco_dick]

I have used "division by zero" method, and I can conclude that the strings a and b contain ONLY LOWERCASE character. Also, there can be blank line as a or b.

However, after making corresponding changes to my program, I am still getting WA. I use the method of counting frequency, stated by IIUC GOLD.

I just wonder is the algorithm wrong, or there is something really tricky.

[dust_cover]

I have chked all the test cases from previous discussions
Also add the capital letter case & blank space
but still getting WA. plz HELP!

Code: Select all

removed after AC!

Thnx in Advance!

[sakhassan]

dust cover


pls chk for this input

pretty woman
walking down

ur output is

*anow (* stands for space)

i think u got ur problem

[dust_cover]

hi corrected it. But still WA
input--

Code: Select all

pretty woman
walking down
qwe
   
pretty
women

output

Code: Select all

anow

e

can someone ac telle me whether my output is right?

[dust_cover]

Hello sorry i had the problem with my Array size
And I checked that no need to consider the Capital letter or blank space
Which is clearly stated in the problemset. i used the ASCII value from 97 to 122 & got AC!
And there is no such data in Judge Input also

--thanx

[JoongHo]

Who can give advice to me?

-------------------------------------------------------------------------------------

/*
No. 10252 Common Permutation
*/

#include <iostream>
#include <string>

using namespace std;

void quick_sort (char a[], int n)
{
char v, t;
int i, j;
if (n > 1)
{
v = a[n-1];
i = -1;
j = n-1;
while(1)
{
while(a[++i] < v);
while(a[--j] > v);
if (i >= j) break;
t = a;
a = a[j];
a[j] = t;
}
t = a;
a = a[n-1];
a[n-1] = t;
quick_sort(a, i);
quick_sort(a+i+1, n-i-1);
}
}


int main()
{
char input1[1001], input2[1001], result[1001];
int inputLen1, inputLen2, resultLen, k, L, i, j;

while(!cin.eof())
{
k = 0;
// Array Clear
for (L = 0; L < 1001; L++)
input1[L] = 0;

for (L = 0; L < 1001; L++)
input2[L] = 0;

for (L = 0; L < 1001; L++)
result[L] = 0;

// String Input
cin.getline(input1, 1000);
cin.getline(input2, 1000);

// String Length Check
inputLen1 = strlen(input1);
inputLen2 = strlen(input2);

for (i = 0; i < inputLen1; i++)
{
for(j = 0; j < inputLen2; j++)
{
if (result[k] == 0 && input1 == input2[j])
{
result[k] = input1;
input2[j] = NULL;
j = inputLen2;
}
}
if (result[k] != 0)
k++;
}


quick_sort(result, k);

for(int r = 0; r < k; r++)
{
cout << result[r];
}

cout << endl;
}

return 0;
}

[Jan]

Dont open a new thread if there is one already. Check the following thread...
http://online-judge.uva.es/board/viewto ... ight=10252

[mpi]

I've tried it hundreds of times but always get WA. I'm getting tired of this silly problem, it's too straightforward to worth doing it. My approach is based on counting the frequencies of characters in the two input strings, handling empty lines too. Here is my short code for this problem:

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAXLEN 1000

char cadena1[MAXLEN+2], cadena2[MAXLEN+2], permutacion[MAXLEN+1];
char letras1[256], letras2[256];
int len1, len2;

int main()
{
    int i, j, k;
    int min;

    while (gets(cadena1) && gets(cadena2)) {
        len1 = strlen(cadena1);
        len2 = strlen(cadena2);
        for (i = 0; i < len1; i++) letras1[cadena1[i]]++;
        for (i = 0; i < len2; i++) letras2[cadena2[i]]++;

        for (i = 'a', k = 0; i <= 'z'; i++) {
            min = (letras1[i] < letras2[i]) ? letras1[i] : letras2[i];
            for (j = 0; j < min; j++) {
                permutacion[k++] = i;
            }
            letras1[i] = letras2[i] = 0;
        }

        permutacion[k] = '\0';
        printf("%s\n", permutacion);
    }

    return 0;
}

Thanks in advance!

[mpi]

OK, i've just found the subtle mistake that was spoiling my code and hence my results, notice the difference:

Before:

Code: Select all

for (j = 0; j < min; j++) 
    permutacion[k++] = i;

After:

Code: Select all

for (j = 0; j < min; j++) 
    permutacion[k++] = (char)i;

Sometimes i feel a bit embarrassed

[kana]

i'm getting PE!!! can anyone help?

Code: Select all

[Jan]

Read the description again.

Each string is on a separate line and consists of at most 1000 lowercase letters

So, there can be blank strings.

Code: Select all

    if(l1 == 0) 
        continue; 

So, you dont need this line.

Hope it helps.

[himanshu]

If several x satisfy the criteria above, choose the first one in alphabetical order.

Can this problem have two answers or that is just to confuse the extra cautions.

Thank You,
HG