PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk to Simple (Anyone please help xD).
Okay, Decided. Cakewalk.
PREREQUISITES:
Mapping, Basic Implementation.
PROBLEM:
Given N works, we have to find minimum units of time to type all words, given following conditions. (I am taking tenth of a second as unit throughout the editorial)
*
- Typing First character take two unit of time.
- Typing Next character with same hand as previous character takes 4 unit of time, while typing with different hand takes 4 unit of time.
- If a word is typed before, It takes exactly half time it took to type word First time.
SUPER QUICK EXPLANATION
- Calculate time for each distinct word, say c and assuming word occur x times, total time of typing this word x times is c+(x-1)*c/2.
- To calculate time of each distinct word, just keep a variable, indicating which hand was used to type previous character. If same hand is used for both and current character, increase time by 4, otherwise increase time by 2.
EXPLANATION
This problem is fairly simple, so, expect a lot of implementation detail. Those who can implement, read only upper half and bonus problem.
First of all, we can handle each distinct word separately, since time taken by different distinct words is independent.
Suppose we have x occurrence of a word, and it takes 2*c units of time to type it for first time. Then, We can see
Typing same word two times take 2*c+c = 3*c, three times take 2*c+c+c, … x times take 2*c+c*(x-1).
So, in just one line, we know how to calculate time taken to type single word multiple word x times. Now, If we know time taken to type each distinct word, we have solved the problem.
Now, Let’s calculate time taken to type a word.
First character always take 2 units of time, as given in problem statement.
For other character, the only factor, which decides whether it will take 2 unit or 4 unit of time to type current character is the fact whether previous character is typed by same or different hand.
So, The only thing we store is, whether last character was typed by left or right hand.
If both current and previous character are to be typed by same hand, increase time by 4 unit of time, else increase tome by 2 unit of time.
Turns out we have solved the problem.
For implementation, two ways are possible.
One is to make a String to Integer mapping storing number of times current string occurs in test case. Then, calculate time for each distinct word and handle multiple occurrences as explained above.
Other is to make a String to Integer mapping storing time taken to type this word first time. Whenever we see a word already typed before, just add half the time it took to type word first time.
Bonus problem
Harder version of this problem. (Basic problem to practice a well known technique)
Left hand can type f,g and h, while right hand can type g,h and j Find minimum time to type words, if all other things remains same. All strings consist of these characters only.
PS: Try some general technique, not case based solution.
Idea in secret box.
Click to view
Time Complexity
Time complexity is O(N*C*logN) where C is time taken to compare strings (required for map get method as well as for sorting, if used, depending upon implementation.)
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 