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

Post Reply
midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra »

thank you so much!!
I finally understand! :D :D :D

Byee!

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Hi

Post by sumankar »

Midra,

Good, now can you remove the code :wink:

mooseelkdog
New poster
Posts: 18
Joined: Fri Oct 10, 2003 8:46 am
Location: Airway Heights

10252

Post by mooseelkdog »

Can't seem to figure out why I get a wrong answer to this problem, I find the common letters to the words, and output the multiples of each letter occuring in both words, I output blank lines for neither word having common letters and for a blank input of the second word, IS IT POSSIBLE TO HAVE AN INITIAL BLANK LINE INPUT?

Thank you

mooseelkdog
New poster
Posts: 18
Joined: Fri Oct 10, 2003 8:46 am
Location: Airway Heights

Post by mooseelkdog »

for clarity I am posting my sample input:

<blank line>
icky
pretty
women
walking
down
the
street
meningitis
frontal
yelp
<blank line>
verbatim
greater
prettywoman
walkingdown
inging
singing
ab
ba
ab
cd
cat
bat

and my output generated:

<blank line>
e
nw
et
nt
<blank line>
aert
anow
ggiinn
ab
<blank line>
at

for extra clarity, <blank line> signifies carriage return

thanks again

tetuya
New poster
Posts: 14
Joined: Thu May 27, 2004 2:31 pm

Post by tetuya »

Hi mooseelkdog.
Your output is same with mine.
you may have other wrong code.

noren
New poster
Posts: 3
Joined: Tue Nov 18, 2003 1:07 pm
Location: Ume

Post by noren »

I'd say that case matters. After I added tolower() I got accepted. There must be something wrong either in the spec, or in the testdata. However you can print the letters in lowercase. Just convert the indata to lowercase.
/johan

Arm.Turbo
New poster
Posts: 21
Joined: Wed Aug 11, 2004 1:20 pm

Post by Arm.Turbo »

My outputs for all tests from this board the same with AC solutions. I try to use tolower() but it's WA anyway. What's the problem?

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int main ()
{
	char tmp1[1024];
	char tmp2[1024];
	char ttmp1['z'-'a'+1];
	char ttmp2['z'-'a'+1];
	int j, sl1, sl2, k;

	#ifndef ONLINE_JUDGE 
	freopen("Debug/input.txt", "r", stdin); 
	//freopen("Debug/output.txt", "w", stdout); 
	#endif 

	while(1)
	{
		if (gets(tmp1) == NULL)
			break;
		if (gets(tmp2) == NULL)
			break;
		sl1 = strlen(tmp1);
		sl2 = strlen(tmp2);
		for (j = 0; j < 'z'-'a'+1; j++)
		{
			ttmp1[j] = 0;
			ttmp2[j] = 0;
		}
		for (j = 0; j <sl1; j++)
		{
			ttmp1[tolower(tmp1[j])-'a']++;
		}
		for (j = 0; j <sl2; j++)
		{
			ttmp2[tolower(tmp2[j])-'a']++;
		}
		for (j = 0; j < 'z'-'a'+1; j++)
		{
			if (ttmp2[j] < ttmp1[j])
				ttmp1[j] = ttmp2[j];
		}
		for (j = 0; j < 'z'-'a'+1; j++)
		{
			for (k =0; k < ttmp1[j]; k++)
			{
				printf("%c", j+'a');
			}
		}

		printf("\n");
	}
	return 0;
}

burgerman
New poster
Posts: 1
Joined: Wed Oct 13, 2004 4:36 pm
Location: Bob Jones University

Post by burgerman »

I try to use tolower() but it's WA anyway.
Your problem is not upper-case input. The following code should cause a floating point exception should any uppercase letters occur:

[cpp]char c
if (c >= 'A' || c <= 'Z'){
int x = 6 / 0; //will cause fpe should a character from A to Z be encountered
}[/cpp]
and none occurred when I tried it.

Your problem would probably be found in the statement,
The input file contains several cases, each case consisting of two consecutive lines.
(tolower may even cause further problems, depending on the judge's implementation)

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

10252

Post by midra »

Why this qsort function doesn't work

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince »

hi
i have changed ur code and got AC
but u have to understand what were the problems in your code

MAP

Code: Select all

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

int funcion(const void *a,const void *b){ 
return *(char*)a-*(char*)b; 
} 

int main() 
{ 
  char a[1002],b[1002],x[1002]; 
  int i,j,len1,len2,ind; 
  while(gets(a)){
	  gets(b);
	  if ( strlen(a) == 0 || strlen(b) == 0 ){printf("\n");continue;}
      for (i=0;i<=ind;i++)  x[i]=0; 
      len1=strlen(a);len2=strlen(b); 
      ind=0; 
      for(i=0;i<len1;i++) 
          for(j=0;j<len2;j++){ 
              if(a[i]==b[j]){ 
                  x[ind]=b[j];              
                  b[j]=0; 
                  ind++; 
                  break; 
              } 
          } 
		  x[ind] = NULL;
		  qsort(x,ind,sizeof(x[0]),funcion); 
		  printf("%s\n",x); 
  }    
  return 0; 
}

Kentaro
New poster
Posts: 19
Joined: Thu Feb 05, 2004 4:41 am
Location: Canada, eh?

Something wrong with judge?

Post by Kentaro »

Important Edit: A straight LCS-based solution worked like a charm and I've finally gotten AC for this problem. But I wonder what was wrong with this program?

The Programming Challenges judge accepts my program just fine, which seems to work exactly according to the problem specification (it assumes it is working with 0-1000 lowercase letters in each string and is correct for every single test case I could throw at it) but the UVa judge won't accept it.

I think the UVa judge is playing a terrible trick on all of us and I'm trying to get to the bottom of it... :-?

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

const bool DEBUG = false;

int main() {
	string word1, word2;
	while (getline(cin, word1) && getline(cin, word2)) {
		
		if (DEBUG) {
			cout << "First line is: " << word1 << endl;
			cout << "Second line is: " << word2 << endl;
		}
		
		// Sort the letters in each word
		sort(word1.begin(), word1.end());
		sort(word2.begin(), word2.end());
		
		// Make sure that the shortest word is word1
		if (word1.size() > word2.size()) {
			string temp = word1;
			word1 = word2;
			word2 = temp;
		}
		
		if (DEBUG) {
			cout << word1 << endl;
			cout << word2 << endl;
		}
		
		int w1_place = 0;
		int w2_place = 0;
		int w2_last = 0;
		while (w1_place < word1.size() && w2_last < word2.size()) {
			if (word1[w1_place] == word2[w2_place]) {
				cout << word1[w1_place];
				w1_place++;
				w2_place++;
				w2_last = w2_place;
			}
			else {
				if (w2_place < word2.size()) w2_place++;
				else {
					w1_place++;
					w2_place = w2_last;
				}
			}
		}
		cout << endl;
	}
}
Edited to remove some extra emoticons that appeared in the post.
Another fixes a minor issue in the code. I didn't submit the code with any syntax errors, but I have been changing it a lot trying to get AC, so in revising the code and reverting it back again I've made some small mistakes.
Computer Science is no more about computers than Astronomy is about telescopes.
-- E. W. Dijkstra

AhlyM
New poster
Posts: 3
Joined: Thu Mar 16, 2006 10:22 pm

10252 compiler error

Post by AhlyM »

hi programmers.
This code take compiler error i need someone to tell me where is the error?

Code: Select all

program str (input,output);
uses strings;
type
   arr=array of char;
var
   x,y,r,z:arr;
   s1,s2:string;
   i,l1,l2,b,g,c,v,s:integer;
function bubble (r:arr;s:integer):arr;
var
   i,j:integer;
   t:char;
begin
     for i:= 1 to length(r) do
     begin
          for j:= 1 to length(r)-1 do
          begin
               if r[j] > r[j+1] then
               begin
               t:=r[j];
               r[j]:=r[j+1];
               r[j+1]:=t;
               end;
          end;
     end;
     bubble:=r;
end;
begin
     while not eof(input) do
     begin
     c:=1;
     s:=1;
     readln(s1);
     readln(s2);
     l1:=length(s1);
     l2:=length(s2);
     setlength(x, l1);
     setlength(y, l2);
     setlength(r, 0);
     setlength(z, 100);
     for i:=1 to l1 do
     begin
          x[i]:=s1[i];
     end;
     for i:=1 to l2 do
     begin
          y[i]:=s2[i];
     end;

     if l1>l2 then
     begin
          for g:=1 to l1 do
          begin
               for v:=1 to l1 do
               begin
                    if y[c]=x[v] then
                    begin
                         z[s]:=x[v];
                         s:=s+1;
                         break;
                    end;
               end;
               c:=c+1
          end;
     end
     else
     begin
     for g:=1 to l2 do
          begin
               for v:=1 to l2 do
               begin
                    if x[c]=y[v] then
                    begin
                         z[s]:=y[v];
                         s:=s+1;
                         break;
                    end;
               end;
               c:=c+1
          end;
     end;
     setlength(r, s);
     for b:=1 to s do
     begin
         r[b]:=z[b];
     end;
     r:=bubble(r,s);
     for b:=2 to s do
     begin
          write(r[b]);
     end;
     setlength(z, 0);
     setlength(r, 0);
     setlength(x, 0);
     setlength(y, 0);
     writeln;
     writeln;
     end;
end.

mosaick2
New poster
Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

10252 - I got TLE..

Post by mosaick2 »

Actually, I can't understand what's wrong in my method.
Who can give advice to me?

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int CHARSIZE = 26;

void checkMap(char *lCase, int *map);

int main()
{
	char lCase1[1000] = {0,};
	char lCase2[1000] = {0,};
	int map1[CHARSIZE] = {0,};		// for masking flags.
	int map2[CHARSIZE] = {0,};		// for masking flags.

	do {
		/* Clear */
		memset(map1, 0x00, CHARSIZE*4);
		memset(map2, 0x00, CHARSIZE*4);
		memset(lCase1, 0x00, 1000);
		memset(lCase2, 0x00, 1000);

		/* Input */
		cin.getline(lCase1, 1000);
		cin.getline(lCase2, 1000);

		/* Processing */
		checkMap(lCase1, map1);
		checkMap(lCase2, map2);

		/* Output */
		for(int i=0; i < CHARSIZE; i++) 
		{
			if((map1[i] >= 1) && (map2[i] >= 1)) {
				int small = (map1[i] > map2[i]) ? map2[i] : map1[i];
				for(int j=0; j < small; j++) 
					printf("%c", i+97);
			}
		}
		cout << endl;

	} while(!cin.eof());

	return 0;
}

void checkMap(char *lCase, int *map)
{
	int ix=0;
	while(lCase[ix] != 0)
	{
		switch (lCase[ix])
		{
			case 'a': map[0] += 1; break; case 'b': map[1] += 1; break;
			case 'c': map[2] += 1; break; case 'd': map[3] += 1; break;
			case 'e': map[4] += 1; break; case 'f': map[5] += 1; break;
			case 'g': map[6] += 1; break; case 'h': map[7] += 1; break;
			case 'i': map[8] += 1; break; case 'j': map[9] += 1; break;
			case 'k': map[10] += 1; break;case 'l': map[11] += 1; break;
			case 'm': map[12] += 1; break;case 'n': map[13] += 1; break;
			case 'o': map[14] += 1; break;case 'p': map[15] += 1; break;
			case 'q': map[16] += 1; break;case 'r': map[17] += 1; break;
			case 's': map[18] += 1; break;case 't': map[19] += 1; break;
			case 'u': map[20] += 1; break;case 'v': map[21] += 1; break;
			case 'w': map[22] += 1; break;case 'x': map[23] += 1; break;
			case 'y': map[24] += 1; break;case 'z': map[25] += 1; break;
		}
		ix++;
	}
}

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani »

try to change
char lCase1[1001] = {0,};
char lCase2[1001] = {0,};
In checkMap, you go till a 0 is meeted, what if the inputs string's length are exactly 1000. you missed the trailing 0.

mosaick2
New poster
Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

Thx, But it's not the reason.

Post by mosaick2 »

Amir Aavani wrote:try to change
char lCase1[1001] = {0,};
char lCase2[1001] = {0,};
In checkMap, you go till a 0 is meeted, what if the inputs string's length are exactly 1000. you missed the trailing 0.
I've got your advice.
I think It's also my mistake.
But, I got TLE until now.
I think I have the other problem in my code.

Post Reply

Return to “Volume 102 (10200-10299)”