11058 - Encoding

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

Moderator: Board moderators

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Aug 12, 2006 7:29 pm

ytsejam wrote:This problem looks simple, but with this code, I get RE.
Someone can explain me what's wrong?
The test case above gives correct result.
You have too short array for the input string.
ytsejam main() wrote:........char string[22]; ........<-- set it to something like 110
........char encoded[22];
........char subst[26][102];
........int c = 1;

........while(scanf("%s%*[\n]", string) == 1){
..............
........}


leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

Post by leocm » Sun Aug 13, 2006 5:57 am

The correct output:

Code: Select all

Case #1: The encoding string is aabbaa.

Your code outputs one 'a' less.
Martin, my output for this case it's the same that yours, "aabbaa".
Test again and look... What is wrong?
Anyone knows?

Thank you!

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Aug 13, 2006 2:59 pm

leocm wrote:Martin, my output for this case it's the same that yours, "aabbaa".
Test again and look... What is wrong?
Anyone knows?

Thank you!
I guess you are working on a windows machine, aren't you? If so, think about writing portable code as the OJ is running on linux. On linux your code throws away the last char of the input string. Note that while windows use "\r\n" to mark end of line all unixes use just "\n" to mark it.

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Wed Aug 16, 2006 2:51 pm

I got a lots of WA a on this easy looking problem ~x(
but cann't find the cause..
may be some of u can help me to find out the cause.
here is my code and some test cases...

Code: Select all

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;

#define All(X) X.begin(),X.end()
#define co continue
#define re return
#define ox 2147483647
struct ToCh{
	int f;
	char tc[28];
};
struct inCh{
	int i;
	char a, b;
};
bool comp(inCh a,inCh b){
	re a.i<b.i;
}
int main(){
	char word[110],toch[28],x[5],y[5];
	int i,j,n,siz,next,k,cas=1,l;
	vector<ToCh>update;
	vector<inCh>temp;
	inCh R;
	ToCh T;
	//freopen("11058.txt","r",stdin);
	//freopen("11058.out","w",stdout);
	while(scanf("%s",word)==1){
		for(i=0;i<26;i++){
			scanf("%s",x);
			toch[i]=x[0];
		}
		toch[i]='\0';
		scanf("%d",&n);
		update.clear();
		temp.clear();
		siz=0;
		for(j=0;j<n;j++){
			scanf("%d %s %s",&i, x,y);
			R.i=i;R.a=x[0];R.b=y[0];
			temp.push_back(R);
		}
		sort(All(temp),comp); //this sort may be unnecessay, but i consider it to sure
		k=-1;
		for(l=0;l<n;l++){
			//scanf("%d %s %s",&i, x,y);
			i=temp[l].i;
			x[0]=temp[l].a;
			y[0]=temp[l].b;
			if(i!=k){
				k=T.f=i;
				for(j=0;j<26;j++){
					T.tc[j]=-1;
				}
				T.tc[x[0]-'a']=y[0];
				update.push_back(T);				
				siz++;
			}else{
				update[siz-1].tc[x[0]-'a']=y[0];
			}
		}		
		if(k!=-1)
			next=update[0].f;
		else next=-1;
		k=0;
		for(i=0;word[i]!='\0';i++){
			if(i==next && k<siz){
				for(j=0;j<26;j++){
					x[0]=update[k].tc[j];
					if(x[0]!=-1){
						toch[j]=x[0];
					}
				}
				k++;
				next=update[k].f;
			}
			word[i]=toch[word[i]-'a'];
		}
		printf("Case #%d: The encoding string is %s.\n\n",cas++,word);
	}
	return 0;
}
I test this with the following inputs

Code: Select all

aaab
b
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a a
1 a b
2 a c
3 b d
4 x y

abcd
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a z
1 a y
2 a x
3 a w
4 x y

aaaa
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a z
1 a y
2 a x
3 a w
4 x y

baba
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
4
0 b a
1 a b
1 b x
2 a x

aaaaaa
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
2 
2 a b
4 a a

ufrn 
t
o
w
k
q
z
f
n
y
i
c
m
s
j
n
r
g
l
d
s
u
s
g
y
e
u
14
0 q t
0 j f
1 v d
1 r o
1 f d
1 r o
1 f a
2 e p
2 r w
2 v e
2 f x
3 y p
3 t m
3 u k

abcdisdbcaront
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
0

abcdisdbcaront
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
7
0 a x
0 a w
0 b h
1 d t
2 c a
4 c e
10 t g

the output of this code is:

Code: Select all

Case #1: The encoding string is abcd.

Case #2: The encoding string is zaaa.

Case #3: The encoding string is zyxw.

Case #4: The encoding string is abxx.

Case #5: The encoding string is aabbaa.

Case #6: The encoding string is uawj.

Case #7: The encoding string is abcdisdbcaront.

Case #8: The encoding string is whatisthewrong.


User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Wed Aug 16, 2006 10:03 pm

A1 wrote:I got a lots of WA a on this easy looking problem ~x(
but cann't find the cause..
may be some of u can help me to find out the cause.
here is my code and some test cases...
Your I/Os are correct, but your solution isn't working for the following input:

Code: Select all

wskghe
p
x
d
d
v
w
y
n
l
i
l
t
x
y
m
o
y
q
y
q
f
m
d
x
o
z
20
0 a l
0 f j
0 g u
0 g u
0 g w
0 g w
0 h p
0 i z
0 n f
0 n g
0 n q
0 p p
0 r w
0 u e
0 u o
0 u u
0 v i
0 w a
0 w e
0 w m

The correct output:

Code: Select all

Case #1: The encoding string is mylwpv.


User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Wed Aug 16, 2006 10:18 pm

Thanks Martin :D. I got AC..

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Wed Aug 16, 2006 10:20 pm

A1 wrote:Thanks Martin :D. I got AC..
After getting AC, please, remove the code from your previous post :)

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman » Wed Aug 23, 2006 3:41 pm

Thanks for Martin Macko. I got Ac now
The wrong was in my algo. [img][/img]

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Wed Aug 23, 2006 9:00 pm

Mushfiqur Rahman wrote:Thanks for Martin Macko. I got Ac now
The wrong was in my algo. [img][/img]
After getting AC, please, remove your code from your posts... :)

User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post by algoJo » Sat Feb 03, 2007 1:18 am

can anybody give me some hints, I've got WA all the times... :roll:
I've checked my program with I/O sets in this board and it's OK.

Code: Select all

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

char kata[max];
char enc1[max];
char arr[27];

void compute(void){
	int i,len;
	len=strlen(kata);
	for(i=0;i<len;i++)
		enc1[i]=arr[kata[i]-'a'];
}

void init(void){
	memset(kata,0,sizeof(kata));
	memset(enc1,0,sizeof(enc1));
	memset(arr,0,sizeof(arr));
}

void main(){
	int i,len,R,p,k,cas=0;
	char a,b,line[max];
	while(gets(kata))
	{
	if(strlen(kata)==0) gets(kata);
    if(cas) printf("\n");
	cas++;
	len=strlen(kata);
	for(i=0;i<26;i++)
	{
		gets(line);
		sscanf(line,"%c",&arr[i]);
	}
	compute();
	memset(line,0,sizeof(line));
	gets(line);
	sscanf(line,"%d",&R);
	memset(line,0,sizeof(line));
	for(i=0;i<R;i++)
	{
		gets(line);
		sscanf(line,"%d %c %c",&p,&a,&b);
		for(k=0;k<len;k++)
			if(k>=p)
			{
				if(kata[k]==a) enc1[k]=b;
			}
	}
	enc1[len]=0;
	printf("Case #%d: The encoding string is %s.\n",cas,enc1);
	init();
	}
}

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman » Sat Mar 03, 2007 3:23 pm

Thanks for Martin for his helpful sample. Lastly I found my bug and got AC

GoLuckyBall
New poster
Posts: 1
Joined: Sun Mar 02, 2008 9:01 am

Post by GoLuckyBall » Sun Mar 02, 2008 9:07 am

The following is my code.

In Online Judge, it must run 3's.But limit of the time is 1's, please help me what should I improve my code. Thanks!!

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

int main() {
int count = 1;
string S;
cin >> S;
while ( S != "EOF" ) {
char Letter[26];
for ( int i=0; i<26; i++ )
cin >> Letter;

int CaseNum;
string rule2[1000][3];
cin >> CaseNum;
for ( int i=0; i<CaseNum; i++ )
for ( int j=0; j<3; j++ )
cin >> rule2[j];

for ( int i=0; i<S.length(); i++ ) {
char temp;
temp = Letter[int(S)-97];
for ( int j=i; j>=0; j-- )
if ( atoi(rule2[j][0].c_str()) <= i )
if ( rule2[j][1][0] == S )
temp = rule2[j][2][0];
S = temp;
}
cout << "Case #" << count << ": The encoding string is " << S << "." << endl << endl;
count++;
cin >> S;
}

system("pause");
return 0;
}

Fahim
New poster
Posts: 1
Joined: Sat Oct 02, 2010 5:58 pm

Re: 11058 - Encoding

Post by Fahim » Sat Oct 02, 2010 6:08 pm

I don't know why everyone is saying this problem is easy :o . I have been trying to understand the given sample I/O for 2 days and still don't get it .Could anyone please explain the sample I/O
:oops: :oops: :oops:

User avatar
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

Re: 11058 - Encoding

Post by outsbook » Fri Jul 06, 2012 2:27 am

I explain the sample input output, then the problem is very clear for understand.

Original string: ufrn

a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: q
f replace by: z
g replace by: f
h replace by: n
i replace by: y
j replace by: i
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: g
r replace by: l
s replace by: d
t replace by: s
u replace by: u
v replace by: s
w replace by: g
x replace by: y
y replace by: e
z replace by: u

1. encoding the first char 'u'. Now position is: 0
a. Apply the rules which p=0 to encoding strategy. (i.e use the rule [0 q t], [0 j f]
After use the rule the encoding strategy like this.
a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: q
f replace by: z
g replace by: f
h replace by: n
i replace by: y
j replace by: f
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: t
r replace by: l
s replace by: d
t replace by: s
u replace by: u
v replace by: s
w replace by: g
x replace by: y
y replace by: e
z replace by: u
b. Now encode the character 'u' using encode strategy. In encode strategy 'u' replace by 'u'.

2. Encoding the second char 'f'. Now position is: 1
a. Apply the rules which p=1 to encoding strategy. (i.e use the rule [1 v d], [1 f d], [1 r o])
After use the rule the encoding strategy like this.
a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: q
f replace by: d
g replace by: f
h replace by: n
i replace by: y
j replace by: f
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: t
r replace by: o
s replace by: d
t replace by: s
u replace by: u
v replace by: d
w replace by: g
x replace by: y
y replace by: e
z replace by: u
b. Now encode the character 'f' using encode strategy. In encode strategy 'f' replace by 'd'.

3. Encoding the second char 'r'. Now position is: 2
a. Apply the rules which p=2 to encoding strategy. (i.e use the rule [2 e p], [2 v e])
After use the rule the encoding strategy like this.
a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: p
f replace by: d
g replace by: f
h replace by: n
i replace by: y
j replace by: f
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: t
r replace by: o
s replace by: d
t replace by: s
u replace by: u
v replace by: e
w replace by: g
x replace by: y
y replace by: e
z replace by: u
b. Now encode the character 'r' using encode strategy. In encode strategy 'r' replace by 'o'.

4. Encoding the second char 'n'. Now position is: 3
a. Apply the rules which p=3 to encoding strategy. (i.e use the rule [3 y p], [3 t m], [3 u k])
After use the rule the encoding strategy like this.
a replace by: t
b replace by: o
c replace by: w
d replace by: k
e replace by: p
f replace by: d
g replace by: f
h replace by: n
i replace by: y
j replace by: f
k replace by: c
l replace by: m
m replace by: s
n replace by: j
o replace by: n
p replace by: r
q replace by: t
r replace by: o
s replace by: d
t replace by: m
u replace by: k
v replace by: e
w replace by: g
x replace by: y
y replace by: p
z replace by: u
b. Now encode the character 'n' using encode strategy. In encode strategy 'r' replace by 'j'.
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Post Reply

Return to “Volume 110 (11000-11099)”