CBOJ Exec Selection Contest Problem 4 - Bob and Books

Submit solution

Points: 15 (partial)
Time limit: 1.5s
Java 4.0s
Python 4.0s
Memory limit: 512M

Problem types

Bob is reading his first fairytale book! Unfortunately, Bob will often find a word that scares him. To overcome his fear, he will play a game he invented.

The scary word can be represented as a string of \(N\) lowercase letters. To start the game, Bob will first put his finger on some position of the string and write the letter from that position on a piece of paper. He then performs one of the following moves an arbitrary number of times:

  • He moves his finger to a position that is one place to the left or to the right of the current position (if that position exists). After moving his finger, Bob will then write down the letter from the new position, right after the previously written letter.

  • He moves his finger to any position with the same letter as the current one. However, Bob will not write anything on the paper in this case.

For either moves it will take Bob \(|x - y|\) seconds to move his finger from position \(x\) to position \(y\).

Bob will overcome his fear of the word if, at the end of the game, his favourite word is written on the paper after the series of moves. Bob wants to finish the book as soon as possible, can you tell him the minimum number of seconds it will take him to write down his favourite word?

For this problem, Python users should submit their submissions in PyPy over CPython.


The first line contains two integers \(N\) and \(M\) \((1 \le N, M \le 300)\), representing the length of the scary and favourite word respectively.

The second line contains \(N\) lowercase letters, representing the word that scares Bob.

The third line contains \(M\) lowercase letters, representing Bob's favourite word.


Output one integer, representing the shortest possible time in seconds Bob needs to write his favourite word on the paper.

If it is not possible, output -1 instead.


Note that you will be required to pass the sample input to receive points for the subtasks.

Subtask 1 [5%]

\(1 \le N, M \le 5\)

Subtask 2 [25%]

\(1 \le N, M \le 50\)

Subtask 3 [70%]

No additional constraints.

Sample Input 1

2 2

Sample Output 1


Sample Input 2

5 4

Sample Output 2


Sample Output 2 Explanation

Bob can put his finger on the last character first and note l down. He can then perform the following moves to write out the word lmog:

  1. Move his finger to the left and write down m,
  2. Move his finger to the leftmost character and take \(|4 - 1| = 3\) seconds (the indices are 1-indexed),
  3. Move his finger to the right and write down o,
  4. Move his finger to the right and write down g.

In total this requires \(1 + 3 + 1 + 1 = 6\) seconds.


There are no comments at the moment.