NOCODING - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Greedy Algorithm

PROBLEM

Find the fewest number of instructions needed by a program to print a given word.
The only three instructions available are

  1. Load a character in memory
  2. Increment the character in memory - increment wraps around, i.e. z increments to a. a increments to b. b increments to c and so on.
  3. Print the character in memory

You can only use the Load Instruction in the beginning of the program.

EXPLANATION

Since you can load a character in memory only in the beginning, you always load the first character of the word in memory and print it.

Each subsequent character has to be printed in order.

For printing each subsequent character you must increment the current character in memory to match the next character and then print it.

To understand why this is correct, we can consider the state (n, c) where
n = number of letters printed till now

c = character in memory

After printing the k characters we are always going to encounter the state (k, c') where c' is the k’th character (1 based indexes). Also, we are going to encounter each of these states in order from k = 1 to k = N.

The only operation that does transitions in states is the Increment instruction, since the Load instruction can only be used in the beginning. Hence, the remaining program can, and must only do

  • Increment memory until character in memory is same as next character.
  • Print character.

The length of the program would thus be equal to

  1 => Initial load instruction
+ N => Print instructions for each letter in the word
+ I => Number of increment instructions needed

I can be calculated by iterating through the word and adding the pairwise circular difference. Circular difference between two characters p and q is

(q - p + 26) modulo 26.

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

1 Like
2

can anyone explain me the difference in the two solution. I believe approach is same in both the cases but my solution gave Wrong answer while this was accepted

My Solution
http://www.codechef.com/viewsolution/1272060

The other guy’s solution
http://www.codechef.com/viewsolution/1272505

3

I think your problem is here:
if(instr_count<(leng*11))

try changing to:
if(instr_count<=(leng*11))

4

@ayusun
You’ve missed one =
logical error at line 27

instead of

	`if(instr_count<(leng*11))
		printf("YES\n");
	else
		printf("NO\n");`

write

	`if(instr_count<=(leng*11))
		printf("YES\n");
	else
		printf("NO\n");`
5

http://www.codechef.com/viewsolution/1273398

it didn’t work…

6

The size of char array should be at least 1001. Because the number of English character can be 1000 and a NULL character also must be stored.

3 Likes
7

oh yeah null value…it worked