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

×

# EMITL - Editorial

Author: Pavel Sheftelevich
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak

Cakewalk

# PROBLEM:

Given a string $S$ of $n$ uppercase Latin letters, your task is to decide if it is possible to rearrange letters in $S$ in such a way that the resulting string will have a string LTIME as a prefix and a string EMITL as a suffix.

# QUICK EXPLANATION:

It is sufficient to check if $S$ contains enough letters to form the required strings as its prefix and its suffix.

# EXPLANATION:

In both subtasks, you have to handle some number of test cases.

You have to handle up to $100$ test cases, but the good news is that each one contains a string $S$ of length at most $9$. In this case, we can try any possible arrangement of letters of $S$, in other words, every permutation of its letters, and for each one, check if it has the required strings as a prefix and as a suffix. The total time complexity of this method is $O(T \cdot n! \cdot n)$ and it is enough, because $n$ is at most $9$ and we have at most $100$ test cases to handle.

The above method is only sufficient when dealing with such small inputs like we have in the first subtask. For the second subtask, it is way too slow, not only because we have up to $1000$ test cases to handle, but mainly because $n$ can be much larger here, up to $100$. It is clear that we need a completely different approach here.

Let's think for a second, do we need to consider any permutation of letters of $S$? Of course we don't to do that. Notice that if there not enough letter to form both the required prefix and the required suffix, the answer is clearly NO. On the other hand, if there are enough letters in $S$ to form the required prefix and the required suffix, the answer is YES.

First, we can notice that the shortest string containing required prefix and required suffix has length $9$. This is true, because a string LTIMEMITL has length $9$ and has the required prefix and suffix. Moreover, there is no such shorter string, because the longest prefix of EMITL which is also a suffix of LTIME has length $1$.

Based on this observation, there are three cases to consider. If $n = 9$ then the answer is YES if and only if S contains two L, two T, two I, two M and one E. If $n > 9$, then the answer is YES if and only if S contains at least two L, at least two T, at least two I, at least two M and at least two E. If $n < 9$, then the answer is clearly NO.

The total complexity of this solution is $O(n)$, because the only thing we have to do is to count occurrences of $5$ different letters in $S$.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 24 Oct '15, 18:57

74485097
accept rate: 12%

19.8k350498541

 0 https://www.codechef.com/viewsolution/8632174 why wrong in 2nd sub task?? answered 25 Oct '15, 14:05 11●1 accept rate: 0% It's giving YES for LTIMEMITLQ but answer is NO i.e. it is failing for case where length of string is greater than 9 and contains one E. (25 Oct '15, 14:15)
 0 For which test case it is wrong? https://www.codechef.com/viewsolution/8627116 answered 25 Oct '15, 14:15 3★akshayv3 157●8 accept rate: 4% For LTIMLTIME it gives NO. (25 Oct '15, 16:18)
 0 please help for this solution !!! https://www.codechef.com/viewsolution/8633042 anybody its been messing up with my mind for like 1 hour !!!! save me .... answered 25 Oct '15, 15:28 144●9 accept rate: 0% It fails for the following string LTIMXMITL, because assumed in your solution that if counters for L, T, I and M are at least 2 and the length of a string is 9, then the answer is YES. You have to check the count of E also. (25 Oct '15, 16:04) already got it bro .!!...but thanks for your time and further clarification :D (26 Oct '15, 17:16)
 0 Sorry I am a noob to competitive programming and programming in general, but why wouldn't this work https://www.codechef.com/viewsolution/8634075 answered 25 Oct '15, 16:30 2★r4huln 1●1 accept rate: 0%
 0 @r4huln Your code gives a YES for LTIME and EMITL. As mentioned in the above editorial since the smallest string possible is LTIMEMITL has a length of 9 characters, all the strings which are of lengths lesser than 9 should output NO as an answer. Happy Coding :) answered 25 Oct '15, 16:46 87●2●6 accept rate: 0%
 0 https://www.codechef.com/viewsolution/8635535 Why this code gives WA? Please rectify my mistake. Thanks in advance. answered 25 Oct '15, 17:03 1 accept rate: 0% @sectumsempra_ Your code does not give any output for TIMELTIME. The output should print NO. Please check your code and try again. (25 Oct '15, 17:09)
 0 Thank You very much. Accepted. :) answered 25 Oct '15, 17:21 1 accept rate: 0%
 0 This time it works for all 3 example test cases but it still isn't accepting my answer can you help me? thanks https://www.codechef.com/viewsolution/86371177 answered 25 Oct '15, 17:44 2★r4huln 1●1 accept rate: 0% @r4huln Your code still outputs "YES" for the test case LTIMETIME which should correctly output "NO". Try to improve upon your logic or read the editorial for a proper insight. :) (25 Oct '15, 19:19) I am sorry but did you check the old link this one outputs NO for LTIMETIME (25 Oct '15, 19:31) r4huln2★
 0 Can you please help me with this?? It was giving answer to all the test cases, still it was not accepted... https://www.codechef.com/viewsolution/8632953 answered 25 Oct '15, 17:54 4 accept rate: 0% @idk_anything As mentioned in the above editorial, the smallest such string possible is LTIMEMITL. The output for this should be YES while your code outputs NO. Hence the WA :) (25 Oct '15, 19:22)
 0 In my computer it is working but showing wrong answer in Codechef............please help me out...I am a beginner........... https://www.codechef.com/viewsolution/8630365 answered 26 Oct '15, 21:46 1 accept rate: 0%
 0 In my computer it is working but showing wrong answer in Codechef............please help me out...I am a beginner........... https://www.codechef.com/viewsolution/8630365 answered 26 Oct '15, 21:47 1 accept rate: 0%
 0 In my computer it is working but showing wrong answer in Codechef............please help me out...I am a beginner........... https://www.codechef.com/viewsolution/8630365 answered 26 Oct '15, 21:48 1 accept rate: 0%
 0 This is my solution in Python. It runs correctly for the test cases. But while submitting shows an error. https://www.codechef.com/viewsolution/8633170 Please help out !! answered 27 Oct '15, 16:29 1★vampy9 1 accept rate: 0%
 0 @emerald_19 Check your if i==9 line, there should be "==" not "=" answered 27 Oct '15, 17:31 1●2 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,680
×1,652
×947
×832
×643
×27

question asked: 24 Oct '15, 18:57

question was seen: 3,920 times

last updated: 27 Oct '15, 17:31