TYPING - EDITORIAL

taran_1407 · October 19, 2018, 4:38am

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.

pratik5155 · October 22, 2018, 4:13pm

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

vaibhavraj10 · October 23, 2018, 1:19am

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

prasanna4992 · November 27, 2018, 12:34pm

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

pradeepk105 · March 20, 2019, 3:01pm

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

upintheair · October 23, 2018, 1:32pm

@Vaibhavraj10
Try
1
2
dfjk
f
Answer should be 13

harcasticbeing · May 30, 2019, 7:48am

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.

codes0of0rishi · September 9, 2019, 11:26am

Can anybody please provide TEST CASES for this problem ??

codes0of0rishi · September 9, 2019, 9:12pm

Python 3
Can anybody please help me, in knowing, why the program is not being accepted ??

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))

david_codes · December 24, 2019, 11:58am

Answer is 14…u are mistaken…

ankurparihar · January 24, 2020, 4:44pm

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?

apurv001 · February 1, 2020, 1:19pm

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

ankurparihar · February 2, 2020, 5:11am

Thanks @apurv001 for clarifying.
I had not read it carefully and my natural instinct led me to wrong answer.

aadiupadhyay · March 19, 2020, 7:31pm

can someone help me out with my solution
thanks in advance

harshraj22 · April 19, 2020, 7:44am

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()

rounaksuthar · December 20, 2020, 4:03pm

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) )
                {
                    list.add(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);
}

}