726 - Decode

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

flavio
New poster
Posts: 11
Joined: Sun Mar 06, 2005 4:07 pm
Location: Porto Alegre - RS (Brazil)
Contact:

HELP!!!

Post by flavio »

Hi people...

I need some help...
I have been trying this question about a week...

I really don't know what is the problem! :(
Could anybody help me!?

Here is my C code:

Code: Select all

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

#define MAX_CHAR 256
#define MAX_LINHA 800

void zeraArrayInt(int array[], int size) {
	int i;
	for (i = 0; i < size; i++) {
		array[i] = 0;
	}
}

void zeraArrayChar(char array[], int size) {
	int i;
	for (i = 0; i < size; i++) {
		array[i] = 0;
	}
}

void ordenaArray(char array[], int freq[], int size) {
	int i, j;
	for (i = 1; i < size; i++) {
		for (j = size -1; j >= i; j--) {

			if (freq[array[j]] - freq[array[j - 1]] > 0) {
				char aux = array[j];
				array[j] = array[j - 1];
				array[j - 1] = aux;
			}

		}
	}
}

int main() {

	int i, cont;

	char conversor[MAX_CHAR];

	int knownFreq[MAX_CHAR];
	int encodedFreq[MAX_CHAR];

	char knownOrdem[MAX_CHAR];
	char encodedOrdem[MAX_CHAR];

	char linha[MAX_LINHA];

	char *texto[400000];
	int nLinhas;

	zeraArrayChar(conversor,MAX_CHAR);

	zeraArrayInt(knownFreq, MAX_CHAR);
	zeraArrayInt(encodedFreq, MAX_CHAR);

	zeraArrayChar(knownOrdem, MAX_CHAR);
	zeraArrayChar(encodedOrdem, MAX_CHAR);

	/* calcula as frequencias do texto conhecido */
	cont = 0;
	while (strlen(gets(linha))) {
		for (i = 0; i < strlen(linha); i++) {
			char ch = linha[i];
			if (ch < 'a') ch = ch + 32;
			if (ch >= 'a' && ch <= 'z') {
				if (knownFreq[ch] == 0) {
					knownOrdem[cont++] = ch;
				}
				knownFreq[ch]++;
			}
		}

	}

	/* calcula as frequencias do texto codificado */
	cont = 0;
	nLinhas = 0;
	while (gets(linha) != NULL) {
		texto[nLinhas] = (char *) malloc(MAX_LINHA);
		strcpy(texto[nLinhas++], linha);

		for (i = 0; i < strlen(linha); i++) {
			char ch = linha[i];
			if (ch < 'a') ch = ch + 32;
			if (ch >= 'a' && ch <= 'z') {
				if (encodedFreq[ch] == 0) {
					encodedOrdem[cont++] = ch;
				}
				encodedFreq[ch]++;
			}
		}

	}

	/* ordena arrays */
	ordenaArray(knownOrdem, knownFreq, cont);
	ordenaArray(encodedOrdem, encodedFreq, cont);

	/* faz mapeamento */
	for (i = 0; i < cont; i++) {
		conversor[(char)encodedOrdem[i]] = knownOrdem[i];
	}

	/* processa texto */
	for (i = 0; i < nLinhas; i++) {
		char *aux = texto[i];
		int j;
		for (j = 0; j < strlen(aux); j++) {
			if (aux[j] >= 'a' && aux[j] <= 'z') {
				aux[j] = conversor[aux[j]];
			} else if (aux[j] >= 'A' && aux[j] <= 'Z') {
				aux[j] = conversor[aux[j] + 32] - 32;
			}
		}

		printf("%s\n", aux);
	}

}
Input and output are welcome...

Thanks in advance...
Hugs :-?
Fl

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

I tried to compile and run your code on my computer using VC++, but it crashed. Something wrong with your code or is it my computer ? Anyways, here are some test cases

case1:

Code: Select all

the quick brown fox jumped over the lazy dog.

thE quicK browN foX jumpeD oveR thE lazY doG.

Code: Select all

thE quicK browN foX jumpeD oveR thE lazY doG.
case2:

Code: Select all

the quick brown fox jumped over the lazy dog.
the lazy brown dog jumped over the quick fox. ;)

thE quicK browN foX jumpeD oveR thE lazY doG.
the quick brown of R jumped ovex THE lazy do G :(

Code: Select all

thE quicK browN foX jumpeD oveR thE lazY doG. 
the quick brown of R jumped ovex THE lazy do G :(
case3:

Code: Select all

the quick brown fox jumped over the lazy dog.

abc ??? any idea ???

Code: Select all

eod ??? eua thre ???
case4:

Code: Select all

123abbccc654987the remaining letters are gone :O

the quick brown fox jumped over the lazy dog

Code: Select all

tne qbmod iravk haw sbjpec auer tne fgyx cal
case5:

Code: Select all

[O ] <- this is our national flag. I love BANGLADESH
bangladesh is our motherland. we love her. this is our flag -> [O ]

[O ]**[O ] xyz (1+2)^3=9 xyz xyz xyz xxx yyy zzz ppp ppp qqq

Code: Select all

[S ]**[S ] aol (1+2)^3=9 aol aol aol aaa ooo lll eee eee iii

flavio
New poster
Posts: 11
Joined: Sun Mar 06, 2005 4:07 pm
Location: Porto Alegre - RS (Brazil)
Contact:

Ordering problem...

Post by flavio »

Well... my program ran only the first and second cases correctly... The case 3 is a little confusing...
The letter 'Y' maps to 'A' and I don't know why. Look at my table for case 3:

Frequencies in KNOWN text:
a = 1
b = 1
c = 1
d = 2
e = 4
f = 1
g = 1
h = 2
i = 1
j = 1
k = 1
l = 1
m = 1
n = 1
o = 4
p = 1
q = 1
r = 2
t = 2
u = 2
v = 1
w = 1
x = 1
y = 1
z = 1

Frequencies in ENCODED text:
a = 3
b = 1
c = 1
d = 1
e = 1
i = 1
n = 1
y = 1

(ordering them... I've got:)

KNOWN sorted:
4 = e
4 = o
2 = t
2 = h
2 = u
2 = r
2 = d
1 = q
1 = i
1 = c
1 = k
1 = b
1 = w
1 = n
1 = f
1 = x
1 = j
1 = m
1 = p
1 = v
1 = l
1 = a
1 = z
1 = y
1 = g

ENCODED sorted:
3 = a
1 = b
1 = c
1 = n
1 = y
1 = i
1 = d
1 = e

Making the mapping:
e <=> a
o <=> b
t <=> c
h <=> n
u <=> y
r <=> i
d <=> d
q <=> e

A mapped the most frequently letters each other as the problem said.
But I think that the problem is my ordering algorithm.
What is this algorithm idea? I really don't know

I thought that only character in ENCODED text could map to character in KNOWN text.. but it doesn't happen in case 4.

The leter 'K' in "quick" maps to 'D' in which doesn't exist in KNOWN text:
"123abbccc654987the remaining letters are gone :O"


Could you help me? I'm getting crazy...
Thanks in advance!
Fl

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

my ordering is like this :

Code: Select all

If two chars have different frequency
   then they are ordered accordig to the frequencly.
else ( they have same frequency )
   they are ordered lexicographically
To arrange according to frequency, the char with higher frequency comes before the char with lower frequency. For example, if 'x' appears 3 times and 'k' appears 2 times, then 'x' comes before 'k'.

I used the ASCII values of the chars to do the lexicographic ordering. For example, if 'a' and 'b' has same frequency, then 'a' comes before 'b'. i.e. the char with smaller ASCII value comes first.

flavio
New poster
Posts: 11
Joined: Sun Mar 06, 2005 4:07 pm
Location: Porto Alegre - RS (Brazil)
Contact:

Accepted!

Post by flavio »

Thanks Raiyan!!

I did this and got ACCEPT!!
I've got confused because your case 4 was wrong:

Input:

Code: Select all

123abbccc654987the remaining letters are gone :O

the quick brown fox jumped over the lazy dog
Output:

Code: Select all

tne qbmod iravk haw sbjpec auer tne fgyx cal
I've ignored it. All the other cases were correct after the lexicographic ordering!
Thanks!!

Hugs
Fl

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

Congratulations !

You are welcome.

Are you sure this case is wrong ? This output is generated by my accepted code. I assumed that if a char does not appear then its frequency is zero. So i order and then map the chars with zero frequency too, did not ignore them. But i think, the judge input has all the chars of English alphabet at least once in the first part. So it does not make any difference if you assume this or not.

flavio
New poster
Posts: 11
Joined: Sun Mar 06, 2005 4:07 pm
Location: Porto Alegre - RS (Brazil)
Contact:

Post by flavio »

I think that the judge just input values following this rule:

"The mapping that defines the encoding is one-to-one." :)

So, both the answers are correct! \o/

Best regards!!
Flavio
Fl

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

how do you know that the KNOWN text has no blank lines?

If KNOWN has blank line, how do you know where to break KNOWN and ENCODE?

Thx.

flavio
New poster
Posts: 11
Joined: Sun Mar 06, 2005 4:07 pm
Location: Porto Alegre - RS (Brazil)
Contact:

Post by flavio »

Because the blank line is used only to separate the encoded and decoded texts.

The decoded text has to be readen until find a blank line...
Imediately after the blank line, the encoded text has to be readen....

That is it!
Thanks
Fl

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

So the KNOWN text contain no blank lines? The FIRST blank line separate the KNOWN and ENCODE text? In the spec. it only said they are separated by a blank line, but does not speciaify which blank line.

flavio
New poster
Posts: 11
Joined: Sun Mar 06, 2005 4:07 pm
Location: Porto Alegre - RS (Brazil)
Contact:

Post by flavio »

Exactly... the unique blank line is used to separate the KNOWN and the ENCODED texts. For example:

Code: Select all

your known text here
another line from known text
and other...

(encoded texto here)
See ya!
Fl

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

726_WA

Post by mohsincsedu »

Hi all....................

I faced a problem again!!!!!!


Why i got WA?????


May be my code is ok!!!!!!!!

But what is the problem???


here is my code:

Code: Select all

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

#define M 40000
#define MAX 100

int table[2][30],index[2][30];

void make_table(char s[],int n)
{
	int i = 0;
	while(s[i])
	{
		if(isalpha(s[i]))
		{
			table[n][tolower(s[i])-'a']++;
		}
		i++;
	}

}

void sort_table(int t[],int n)
{
	int i,j,temp;
	for(i = 0;i<26;i++)
		index[n][i] = i;
	for(i = 0;i<25;i++)
	{
		for(j = 25;j>=i+1;j--)
		{
			if(t[j]>t[j-1])
			{
				temp = index[n][j];
				index[n][j] = index[n][j-1];
				index[n][j-1] = temp;

				temp = t[j];
				t[j] = t[j-1];
				t[j-1] = temp;
			}
		}
	}

}

int search_pos(int n)
{

	int i = 0;
	while(1)
	{
		if(n==index[1][i])
			break;
		i++;


	}
	return index[0][i];
}

void main()
{
	char input1[MAX],input2[M][MAX];
	long i,j,num,temp,len;
	memset(table[0],0,sizeof(table[0]));
	while(1)
	{
		gets(input1);
		if(input1[0]=='\0')
			break;
		make_table(input1,0);
	}
	i = 0;
	memset(table[1],0,sizeof(table[1]));
	while(gets(input2[i])!=NULL)
	{

		if(input2[i][0]=='\0')
			break;
		make_table(input2[i],1);
		i++;
	}

	len = i;
	sort_table(table[0],0);


	sort_table(table[1],1);
	for(j = 0;j<=len;j++)
	{
		for(i = 0;input2[j][i];i++)
		{
			if(isalpha(input2[j][i]))
			{
				num = tolower(input2[j][i])-'a';
				temp = search_pos(num);
				if(islower(input2[j][i]))
					printf("%c",temp+'a');
				else
					printf("%c",temp+'A');
			}
			else
				printf("%c",input2[j][i]);
		}
		printf("\n");
	}
}
Why way i get input?? plz tell me!!!
Thanks in advanced!!!!
Amra korbo joy akhdin............................

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

726_WA

Post by mohsincsedu »

Hi all....................

I faced a problem again!!!!!!


Why i got WA?????


May be my code is ok!!!!!!!!

But what is the problem???


here is my code:

Code: Select all

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

#define M 40000
#define MAX 100

int table[2][30],index[2][30];

void make_table(char s[],int n)
{
	int i = 0;
	while(s[i])
	{
		if(isalpha(s[i]))
		{
			table[n][tolower(s[i])-'a']++;
		}
		i++;
	}

}

void sort_table(int t[],int n)
{
	int i,j,temp;
	for(i = 0;i<26;i++)
		index[n][i] = i;
	for(i = 0;i<25;i++)
	{
		for(j = 25;j>=i+1;j--)
		{
			if(t[j]>t[j-1])
			{
				temp = index[n][j];
				index[n][j] = index[n][j-1];
				index[n][j-1] = temp;

				temp = t[j];
				t[j] = t[j-1];
				t[j-1] = temp;
			}
		}
	}

}

int search_pos(int n)
{

	int i = 0;
	while(1)
	{
		if(n==index[1][i])
			break;
		i++;


	}
	return index[0][i];
}

void main()
{
	char input1[MAX],input2[M][MAX];
	long i,j,num,temp,len;
	memset(table[0],0,sizeof(table[0]));
	while(1)
	{
		gets(input1);
		if(input1[0]=='\0')
			break;
		make_table(input1,0);
	}
	i = 0;
	memset(table[1],0,sizeof(table[1]));
	while(gets(input2[i])!=NULL)
	{

		if(input2[i][0]=='\0')
			break;
		make_table(input2[i],1);
		i++;
	}

	len = i;
	sort_table(table[0],0);


	sort_table(table[1],1);
	for(j = 0;j<=len;j++)
	{
		for(i = 0;input2[j][i];i++)
		{
			if(isalpha(input2[j][i]))
			{
				num = tolower(input2[j][i])-'a';
				temp = search_pos(num);
				if(islower(input2[j][i]))
					printf("%c",temp+'a');
				else
					printf("%c",temp+'A');
			}
			else
				printf("%c",input2[j][i]);
		}
		printf("\n");
	}
}
Why way i get input?? plz tell me!!!
Thanks in advanced!!!!
Amra korbo joy akhdin............................

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

TLE 726

Post by jjtse »

I know this thread has been closed for a while. I tried solving this problem, and it seems ridiculously easy. I tried all the sample input provided, and they all worked. When I submit, I get TLE. I don't know why it should do that though. I sort an array of size 26 using bubble sort. That shouldn't cause it to TLE. And I have no other big time loops anywhere else. Does anyone see why I get TLE?


Code: Select all


code cut after accepted.  Main speedup:  

change sytem.out.print to system.out.write
change Character.tolower/toupper to  c +- 32
use arrays instead of vectors.
bubble sort ok for this problem

thanks Darko!



Last edited by jjtse on Sat Oct 07, 2006 3:42 am, edited 1 time in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

I am not sure what Character.toLower() does, but I think (char)(c+32) would be faster.

Oh, and going the other way - Character.toUpper() is (char)(c-32).

And you want to use System.out.write() instead of print().

And Vector is slow, too.

When you fix those, and if it's still TLE I'll take another look.

[EDIT] I don't think any of the above is the reason - I just tried it and it keeps looping for the second string for some reason (like it never reads null). Now I'm puzzled, too :(

Post Reply

Return to “Volume 7 (700-799)”