Editorial for Another Contest 5 Problem 2 - Great Graffiti

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The first observation to make here is that the answer is at most $3$ ~3~. This is because we are guaranteed to start out with some letter in DMOJ, and we can always just add the $3$ ~3~ missing letters.

With this observation, there are two approaches. One is to enumerate all scenarios where the answer is $0$ ~0~, $1$ ~1~, or $2$ ~2~ - these correspond respectively to all subsequences of DMOJ of length $4$ ~4~, $3$ ~3~, and $2$ ~2~. Another is to brute force all possible ways of inserting $0$ ~0~ characters, $1$ ~1~ character, and $2$ ~2~ characters.

Comments

0

daveys commented on Feb. 9, 2024, 9:38 a.m.

Very interesting problem. I actually only passed all test cases once I generated all the permutations from D to JJJJ and spotted what I'd missed. There were 4 scenarios that I'd not covered, which are actually mentioned above in the editorial text. As usual, me not reading fully enough! Thanks for an interesting problem!!

-11

chrisjjfrancis commented on March 5, 2020, 2:24 a.m.

I have the first 8 correct, but WA for the ninth. It would be helpful to see the data for the wrong answer.

This comment is hidden due to too much negative feedback. Show it anyway.

-11

chrisjjfrancis commented on March 5, 2020, 2:16 a.m.

Also, are the blanks always at the end of the line, or can you have DM J ?

This comment is hidden due to too much negative feedback. Show it anyway.

-9

chrisjjfrancis commented on March 5, 2020, 2:15 a.m.

It would be helpful to have a more complex example or multiple examples. Can the letters ever be out of order?

This comment is hidden due to too much negative feedback. Show it anyway.

6

chika commented on March 5, 2020, 5:18 a.m.

Responding to all of your concerns:

It would be helpful to have a more complex example or multiple examples.

You can write your own test cases. Problems frequently do not contain complex examples and you should not expect problems to include edge cases in the examples.

Can the letters ever be out of order?

The input constraints do not say anything about the order of the letters, so you should not assume that they come in any specific order.

Also, are the blanks always at the end of the line, or can you have DM J?

The problem statement does not mention anything about blanks.

I have the first 8 correct, but WA for the ninth. It would be helpful to see the data for the wrong answer.

We will not provide the test case that you fail on. You may find it helpful that $4^1 + 4^2 + 4^3 + 4^4 = 4 + 16 + 64 + 256 = 340$ , which is the number of test cases for this problem.

Does the solution work for Python 3? Should I try Python 2?

There are 28 correct submissions to this problem in Python 3. There are 9 correct submissions to this problem in Python 2. Therefore, the problem is solvable in both versions of Python, so you are welcome to pick whichever version of Python you are more comfortable with.

4

chrisjjfrancis commented on March 22, 2020, 6:36 p.m.

Thanks Chika. I made some incorrect assumptions. Your answered helped.