Sherlock and the Ugly Flower
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Watson gives to Sherlock two strings S1 and S2 consisting of uppercase English alphabets. Next he wants Sherlock to build a flower in the following way:
He puts both strings perpendicular to each other in such a way that they overlap at the same character. For example, if he has two strings "ABCDEF" and "XXBCZQ", one possible way to make a flower is:
Length of petals in the above flower are 2, 2, 3 and 3.
A flower's ugliness is sum of absolute difference of adjacent petal lengths i.e. i.e. if adjacent petal lengths are L1, L2, L3, L4, then ugliness of flower is |L1 - L2| + |L2 - L3| + |L3 - L4| + |L4 - L1|.
Sherlock wants to find minimum value of ugliness if we consider all possible flower configurations. Note that a configuration is valid even if any of the petal length is 0.
First line contains T, number of test cases. Each test case consists of string S1 in one line followed by string S2 in the next line. It is guaranteed that there exists at least one possible way to make a flower.
For each test case, output in one line the required answer.
- 1 ≤ T ≤ 10
- 1 ≤ length(S1), length(S2) ≤ 105
Input: 2 ABCDE XXBCZQ BBB BBBBBB Output: 2 6
Test case 1:
If we keep the configuration shown in statement, the ugliness is 2, which is minimum possible.
Test case 2:
One of the best configurations is
B B B B B B B B where petal lengths are 1, 3, 1, 2.
|Tags||binary-search, cook75, darkshadows, easy-medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.