You are not logged in. Please login at www.codechef.com to post your questions!

×

SISLOVE - Editorial

0
2

PROBLEM LINK:

Practice
Contest
Author: Shivam Kapoor
Tester: Rishabh Prasad
Editorialist: Shivam Kapoor

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Implementation, Basic-Programming, Strings

PROBLEM:

You are given the incorrect spellings of number names (from zero to ten (inlusive)) with exactly one mistake. You need to print the numerical value of the correct spelling.

QUICK EXPLANATION:

This problem can be easily solved with brute-force in O(N2) time limit because of lower value of constraints. Maintain an array of strings with the correct spellings and one with the corresponding numerical values. Loop through the whole array for the given spelling. If more than 1 mismatch is found move to the next word. This problem can also be solved using Edit-Distance.

EXPLANATION:

We start off by creating an array of strings with the correct representation of the number names starting from 0-9. Note that an array of string is nothing but a Double dimensional array. Since we need to print the numerical value of the correct answer we also maintain an integer array with values 0-9. Next, we input the incorrect spelling and match it with every word in the array.NOTE : We only need to compare with those values which have the same length as that of the input because as per the question the length is not altered. So if input.length() != array[i].length() there is no point in proceeding further, we simply move to the next index in the array. Now once a match in length is found, we compare every corresponding character and once a match is found we increment a counter or flag variable every time. Once the value of this counter variable exceeds 1, we make it zero and move to the next word. This is because there is EXACTLY one mistake in the word. Once the answer is found, we store the INDEX of that word in the array and print the corresponding value in our integer array i.e integerarray[i] since they are correspondingly one and the same! Here is the pseudo-code of the above implementation.

string str[10]={"zero","one","two","three","four","five","six","seven","eight","nine"}
int arr[10]={0,1,2,3,4,5,6,7,8,9}
for(i=0 to 9)   
  count=0
  if(length of(str[i])==length of (word))
  for(j=0 to length(word))
   if(word[j]!=str[i][j]) //jth character of ith string
     count++
   if(count>1) //More than 1 mismatch has been found so this cannot be the answer
      count=0; //For the next iteration
      break
    if(count==1) //Reuired condition is met
    minpos=i //Store the index of this word in the array
    break
print arr[minpos] //Final answer

C users can use char* str[ ] in place of strings.

ALTERNATIVE SOLUTION:

This problem can also be solved via Edit Distance and requires the knowledge of Dynamic Programming. This is a pretty straightforward question in dynamic programming. You just have to check=> if(minEditDistance(incorrect spelling,correct spelling)==1) If so, then print the integral value of correct spelling. Here is a short pseudo code of the above implementation.

if(minEditDistance(x,"one")==1)
print 1
if(minEditDistance(x,"two")==1)
print 2
if(minEditDistance(x,"three")==3)
print 3

..and so on.This code can be optimized also but this is just to give the basic idea. NOTE This solution is also applicable if the question was extended to more than 1 mistake. In fact this would be more feasible.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here. (C++)
Tester's solution can be found here. (Python)

RELATED PROBLEMS:

http://www.codechef.com/problems/CHEFSTLT
https://www.codechef.com/problems/SEATSR

asked 01 Aug '15, 15:37

h1ashdr%40gon's gravatar image

3★h1ashdr@gon
2912320
accept rate: 10%

edited 01 Aug '15, 15:42

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×966
×850
×354
×47
×12
×3

question asked: 01 Aug '15, 15:37

question was seen: 1,265 times

last updated: 01 Aug '15, 15:42