Crack the Safe
All submissions for this problem are available.
Being in a possession of an information so valuable, Irene Adler decides to lock it up in her safe. Sherlock using his detective and charming skills, finds out the place where Irene has hid the data. Irene knew that this day would come, so she had locked the safe up with a secret pass phrase. Since she wanted to be extra secure she had used a sequence of N passwords of length M each. In order to unlock the safe, one has to type in all N passwords in the exact sequential order. However the lock has a major security flaw - it can accept a password or any of its anagrams.
The lock has a display and a keypad that contains only lower case alphabet keys and a backspace button. When Sherlock hits the keys, the text is shown in the display and when he fills the display with M characters, the lock will automatically check if the typed in text is an anagram of the expected password. Then, Sherlock may proceed to type in the next password by removing the last character/characters he has pressed by using the backspace key. When Sherlock has typed in the last password, the lock will release and the safe will open.
Even if 2 adjacent passwords in the sequence is the same, Sherlock has to hit the backspace key and retype the last character again to make the lock accept both the passwords.
Sherlock finds this job too tedious for him and he wants to get this done as soon as possible. Can you help him find the minimum number of keystrokes(includes backspaces also) needed to type in all the passwords in the given sequential order?
The first line of the input has 2 integers N and M denoting the number of password strings and the length of each.
N lines follow, each having a string of M characters. The strings are given in the exact order in which they have to be typed in the keypad.
Print a single integer denoting the minimum number of keys that Sherlock has to press to type in all the pass phrases in the given sequential order.
- 1 ≤ N ≤ 700
- 1 ≤ M ≤ 700
Input: 3 3 aab aac bde Output: 11
Input: 2 3 abc cba Output: 5
For the first test case, Sherlock has to type in the following sequence of characters a, a, b, <-, c, <-, <-, <-, b, d, e thereby typing in 11 characters.(<- denotes the backspace key)
In the second test case, Sherlock can follow the sequence a, b, c, <-, c to type in all the pass phrases.
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.