 # TYPING - EDITORIAL

Tester: Misha Chorniy
Editorialist: Taranpreet Singh

### DIFFICULTY:

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:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. I want to share my code for help.
I am not getting whats wrong in my code…where and how to share?

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 {
try {

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

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

while (t > 0) {
int timecnt = 0;
while (y > 0) {

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

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.

3 Likes

Can anybody please provide TEST CASES for this problem ??

1 Like

Python 3

``````lh = ['d','f']
rh = ['j','k']
for _ in range(int(input())):
n = int(input()) # no. of words
d = {None: None}
total = 0.2*n
for x in range(n):
word = input()
if word in d.keys():
total += d[word]/2
else:
curr_time = 0
for i in range(1,len(word)):
if (word[i] in lh and word[i-1] not in lh) or (word[i] in rh and word[i-1] not in rh):
curr_time += 0.2
else:
curr_time += 0.4
d[word] = curr_time
total += curr_time
print(int(total*10))``````

Answer is 14…u are mistaken…  Can somebody explain me the test cases
The given test case is

``````1
5
fdjkd
dfjdk
dfd
fdjkd
kkjjk
``````

This calculates as
f(2) + d(2) + j(4) + k(2) + d(4) = 14
d(2) + f(2) + j(4) + d(4) + k(4) = 16
d(2) + f(2) + d(2) = 6
f(2) + d(2) + j(4) + k(2) + d(4) = 14/2(repeated) = 7
k(2) + k(2) + j(2) + j(2) + k(2) = 10
========================================
Total = 53
========================================

Then how is the test case is result 61?

you took the question wrong on changing the hand the time is 0.2 not 0.4 so it will be
2+4+2+4+2=14
2+4+2+2+2=12
2+4+4=10
7
2+4+4+4+4=18
total 61

Thanks @apurv001 for clarifying.

can someone help me out with my solution

There are some precision errors when dealing with `floating numbers` in python for this problem.
For example:
print the cur_ans and see the errors. @taran_1407 Any comment on such ?
test case :

``````2
5
dfjk
dfjk
kjkk
dddddd
dkjfk
1
jkjfjjkjdfd
``````
``````
hand = dict(
[('d','left'),
('f','left'),
('j','right'),
('k','right')]
)

def solve():
global hand
ans = 0
words = int(input().strip())
typed_words = dict()

for word in range(words):
cur_word = input()
cur_ans = 0.000
if cur_word in typed_words.keys():
cur_ans += typed_words[cur_word]/2
else:
cur_ans += 0.2000 # for first char
for i in range(1, len(cur_word)):
ch, prv_ch = cur_word[i], cur_word[i-1] # if typing with same hand
if hand[ch] == hand[prv_ch]:
cur_ans += 0.4000
else: # different hand
cur_ans += 0.2000

if cur_word not in typed_words.keys(): # if current word wasn't typed earlier
typed_words[cur_word] = cur_ans
ans += cur_ans
print(cur_ans)
print(int(ans*10))

def main():
tests = 1
tests = int(input().strip())
for test in range(tests):
solve()

if __name__== "__main__":
main()
``````

Can Anyone explain me which test cases I am missing??

import java.io.;
import java.util.
;
class Typing {
public static void main(String[] args) throws IOException{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int count=0;
int sum=0;
char a1[]= {‘d’,‘f’};
char a2[]= {‘j’,‘k’};
int flag1=0,flag2=0;
int tempsum=0;

``````	while(t!=0)
{
int n=sc.nextInt();
ArrayList<Integer> list=new ArrayList<>(n);
String s[]=new String[n];

for(int i=0;i<n;i++)
{
s[i]=sc.next();
}
for (int i = 0; i < s.length-1; i++)
{
for (int j = i+1; j < s.length; j++)
{
if( (s[i].equals(s[j])) && (i != j) )
{
}
}
}
for(int i=0;i<n;i++)
{
char c1[]=s[i].toCharArray();
for(int j=0;j<c1.length;j++)
{
for (int element : a1) {
if (element == c1[j]) {
if(flag1==0)
{
count=1;
sum=sum+count*2;
tempsum=tempsum+count*2;
flag1=1;
flag2=0;

}
else {
count=2;
sum=sum+count*2;
tempsum=tempsum+count*2;
flag2=0;

}

}
/*
* else { continue; }
*/
}
for (int element : a2) {
if (element == c1[j]) {
if(flag2==0 )
{
count=1;
sum=sum+count*2;
tempsum=tempsum+count*2;
flag2=1;
flag1=0;

}
else {
count=2;
sum=sum+count*2;
tempsum=tempsum+count*2;
flag1=0;

}
}
/*
* else { continue; }
*/
}

}
if(list.contains(i)==true)
{
tempsum=tempsum/2;
sum=sum-tempsum;
}
tempsum=0;
flag1=0;
flag2=0;

}

t--;
}
System.out.println(sum);
}
``````

}