EMITL - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Cakewalk

PREREQUISITES:

Adhoc, Strings

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.

SUBTASK 1

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.

SUBTASK 2

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.

2 Likes

CodeChef: Practical coding for everyone why wrong in 2nd sub task??

For which test case it is wrong?
https://www.codechef.com/viewsolution/8627116

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 …

Sorry I am a noob to competitive programming and programming in general, but why wouldn’t this work

https://www.codechef.com/viewsolution/8634075

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

1 Like

https://www.codechef.com/viewsolution/8635535
Why this code gives WA?
Please rectify my mistake. Thanks in advance.

Thank You very much. Accepted. :slight_smile:

@raunak

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

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

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

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

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

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

@emerald_19 Check your if i==9 line, there should be “==” not “=”

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.

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.

For LTIMLTIME it gives NO.

@sectumsempra_
Your code does not give any output for TIMELTIME. The output should print NO. Please check your code and try again.

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