RGPC '17 P5 - Scrabble Nuts

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Nutter is a weird kid. As an infant, he was obsessed with the prefixes of "nutt" ("nut", "nu", and "n"), but hated the word "nutt" itself. When his parents bought him a box of Scrabble, he realized that the board already contained a single word: "putt", which got him thinking. He wondered how he could add, swap, or remove blocks from a word A to make all the prefixes of another word B.

Nutter has access to an infinite supply of Scrabble blocks, and can only add, swap, or remove blocks to form his desired prefixes. Each operation takes 1 move, but since he's quick with his hands, he isn't worrying about shifting blocks (you can add, swap, or remove non-terminal blocks). Nutter wants to know how he can turn word A into word B's prefixes (not including word B itself) using the minimum number of moves.


Subtask 1 [20%]: \,1 \le N, M \le 10.
Subtask 2 [80%]: \,1 \le N, M \le 10\,000.

Input Specification

The first line of input will contain two integers N and M separated by a single space. The second line will contain a single string A of length N, and the third line will contain a single string B of length M.

Output Specification

Output a single integer representing the minimum number of moves to change word A to all of word B's prefixes.

Sample Input

4 4

Sample Output



The prefixes of "putt" are "put", "pu", and "p", and Nutter wants to try and make them all from the word "nutt".

To get "put" from "nutt", swap the "n" with a "p" and remove a "t" from the end (2 operations).
To get "pu", do the same operations as "put", but remove another "t" (3 operations + 2 = 5 total).
To get "p", do the same operations as "pu", but remove the "u" at the end (4 operations + 5 = 9 total).

Since Nutter doesn't want to make "putt" itself, he uses 9 operations in total.


  • 0
    NeatMuffin  commented on Feb. 17, 2017, 9:50 p.m. edit 6

    Words ARE case-sensitive.

    Swap = Replace 1 character from word A WITH another character to MAKE word B.

  • 4
    percywtc  commented on Feb. 17, 2017, 2:30 p.m. edited

    What can be swapped? Is it allowed to...

    • swap blocks within the word A
    • swap block from the word A and a block taken from the supply

    Also, are the words case-sensitive?

    I hope these can be clarified. Thank you.