## 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

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am
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
New poster
Posts: 8
Joined: Fri Jul 15, 2005 4:00 am

### 10252 - Common permutations

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
New poster
Posts: 5
Joined: Mon May 24, 2004 6:09 pm
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
New poster
Posts: 2
Joined: Tue Aug 01, 2006 6:34 am
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
New poster
Posts: 23
Joined: Tue Sep 12, 2006 9:46 pm

### getting WA for 10252! PLZZZZZZZZ help

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!
``````
Last edited by dust_cover on Mon Oct 23, 2006 10:03 pm, edited 1 time in total.
i wanna give it a try....

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
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
New poster
Posts: 23
Joined: Tue Sep 12, 2006 9:46 pm
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?
i wanna give it a try....

dust_cover
New poster
Posts: 23
Joined: Tue Sep 12, 2006 9:46 pm
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
i wanna give it a try....

JoongHo
New poster
Posts: 2
Joined: Wed Jul 19, 2006 9:29 am

### 10252 (TLE) Help me!!

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Dont open a new thread if there is one already. Check the following thread...
http://online-judge.uva.es/board/viewto ... ight=10252
Ami ekhono shopno dekhi...
HomePage

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm

### this problem can't be that difficult

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 letras1[256], letras2[256];
int len1, len2;

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

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

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm

### Oh my gO_od!

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
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka
i'm getting PE!!! can anyone help?

Code: Select all

``````
``````
Last edited by kana on Wed Sep 12, 2007 9:31 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

himanshu
New poster
Posts: 17
Joined: Mon May 15, 2006 12:24 pm