TYPING - EDITORIAL

PROBLEM LINK:

Practice
Contest

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

Dynamic Programming

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. :slight_smile:

I want to share my code for help.
I am not getting whats wrong in my code…where and how to share?

Please help me out with my Solution. Which test case am I missing here?

Can some one give me some complex test cases where the code fails if it isn’t perfect?I did try the one given with question and some made up test cases,my code works well with them,but the code is gettting rejected when submitted

my solution
package streams;

/* package codechef; // don’t place package name! */

import java.util.;
import java.io.
;

/* Name of the class has to be “Main” only if the class is public. */
class typing {
public static void main(String[] args) throws java.lang.Exception {
// your code goes here
try {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		Map<String, Integer> mapwrd = new HashMap<String, Integer>();

		int t = Integer.parseInt(br.readLine());
		while (t > 0) {
			int y = Integer.parseInt(br.readLine());
			int timecnt = 0;
			while (y > 0) {

				String word = br.readLine();
				if (!mapwrd.containsKey(word)) {
					timecnt=timecnt+2;
					for (int i = 1; i < (int)word.length(); ++i) {

						if ((word.charAt(i - 1) == 'd' || word.charAt(i - 1) == 'f')
								&& (word.charAt(i) == 'd' || word.charAt(i) == 'f')) {
							timecnt = timecnt + 4;

						}
						else if ((word.charAt(i - 1) == 'j' || word.charAt(i - 1) == 'k')
								&& (word.charAt(i) == 'j' || word.charAt(i) == 'k')) {
							timecnt = timecnt + 4;

						}
						else {
							timecnt = timecnt + 2;
						}



					}
					mapwrd.put(word, timecnt/2);
				} else {

					timecnt = timecnt + mapwrd.get(word);

				}

				y--;
			}
			System.out.println(timecnt);

			mapwrd.clear();

			t--;
		}
	} catch (Exception e) {
		return;
	}
}

}

pls help me accepted this soluion

@Vaibhavraj10
Try
1
2
dfjk
f
Answer should be 13

My friend’s solution got accepted and it’s output is 14. Stop trying to make people’s lives harder by posting wrong test cases.

2 Likes