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

×

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.

This question is marked "community wiki".

asked 24 Oct '15, 18:57

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 25 Oct '15, 14:02

admin's gravatar image

0★admin ♦♦
19.8k350498541


https://www.codechef.com/viewsolution/8632174 why wrong in 2nd sub task??

link

answered 25 Oct '15, 14:05

vishalrox's gravatar image

2★vishalrox
111
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) dushsingh19954★

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

link

answered 25 Oct '15, 14:15

akshayv3's gravatar image

3★akshayv3
1578
accept rate: 4%

For LTIMLTIME it gives NO.

(25 Oct '15, 16:18) pkacprzak ♦♦5★

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

link

answered 25 Oct '15, 15:28

radeonguy's gravatar image

1★radeonguy
1449
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) pkacprzak ♦♦5★

already got it bro .!!...but thanks for your time and further clarification :D

(26 Oct '15, 17:16) radeonguy1★

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

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

link

answered 25 Oct '15, 16:30

r4huln's gravatar image

2★r4huln
11
accept rate: 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 :)

link

answered 25 Oct '15, 16:46

raunak_parijat's gravatar image

4★raunak_parijat
8726
accept rate: 0%

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

link

answered 25 Oct '15, 17:03

sectumsempra_'s gravatar image

2★sectumsempra_
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) raunak_parijat4★

Thank You very much. Accepted. :)

link

answered 25 Oct '15, 17:21

sectumsempra_'s gravatar image

2★sectumsempra_
1
accept rate: 0%

@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

link

answered 25 Oct '15, 17:44

r4huln's gravatar image

2★r4huln
11
accept rate: 0%

edited 25 Oct '15, 19:39

@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) raunak_parijat4★

I am sorry but did you check the old link this one outputs NO for LTIMETIME

(25 Oct '15, 19:31) r4huln2★

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

link

answered 25 Oct '15, 17:54

idk_anything's gravatar image

3★idk_anything
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) raunak_parijat4★

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

link

answered 26 Oct '15, 21:46

emerald_19's gravatar image

2★emerald_19
1
accept rate: 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

link

answered 26 Oct '15, 21:47

emerald_19's gravatar image

2★emerald_19
1
accept rate: 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

link

answered 26 Oct '15, 21:48

emerald_19's gravatar image

2★emerald_19
1
accept rate: 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 !!

link

answered 27 Oct '15, 16:29

vampy9's gravatar image

1★vampy9
1
accept rate: 0%

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

link

answered 27 Oct '15, 17:31

adityank007's gravatar image

5★adityank007
12
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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