【cf83E】Two Subsequences


On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.

Let {a1, a2, …, an} be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are of the same length and consist only of the digits 0 and 1. Let’s define the compression function:

  • f(empty sequence) = empty string
  • f(s) = s.
  • f(s1, s2) =  the smallest in length string, which has one of the prefixes equal to s1 and one of the suffixes equal to s2. For example, f(001, 011) = 0011, f(111, 011) = 111011.
  • f(a1, a2, …, an) = f(f(a1, a2, an - 1), an). For example, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Valera faces a real challenge: he should divide the given sequence {a1, a2, …, an} into two subsequences{b1, b2, …, bk} and {c1, c2, …, cm}, m + k = n, so that the value of S = |f(b1, b2, …, bk)| + |f(c1, c2, …, cm)| took the minimum possible value. Here |p| denotes the length of the string p.

Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences b and c don’t have to be consecutive in the original sequence a, i. e. elements of b and c can alternate in a (see samples 2 and 3).

Help Valera to find the minimum possible value of S.


The first line of input data contains an integer n — the number of strings (1 ≤ n ≤ 2·105). Then on n lines follow elements of the sequence — strings whose lengths are from 1 to 20 characters, consisting only of digits 0 and 1. The i + 1-th input line contains the i-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.


Print a single number — the minimum possible value of S.

Sample test(s)







Detailed answers to the tests:

  • The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
  • The best option is: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
  • The best option is: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 1




  1. Pingback: cheap wedding dresses china japan

  2. Pingback: coach poppy purse purple

  3. Pingback: louis vuitton duffle bag aliexpress

  4. Pingback: coach legacy purses

  5. Pingback: ray ban 3025 gold l0205

  6. Pingback: herve leger rainbow dress ebay

  7. Pingback: champagne colored ball gown wedding dresses

  8. Pingback: cheapest giuseppe zanotti shoes nordstrom

  9. Pingback: ray ban 4039 polarizado

  10. Pingback: lace wedding dresses for sale

  11. Pingback: giuseppe zanotti black and white stripe

  12. Pingback: mens louis vuitton wallet

  13. Pingback: louis vuitton mens bags china

  14. Pingback: ray ban original wayfarer asian fit

  15. Pingback: coach shoes loafers

  16. Pingback: authentic herve leger dress sale australia

  17. Pingback: nike coach catalog

  18. Pingback: coach usa soccer

  19. Pingback: vintage wedding dresses in london

  20. Pingback: nike air max 180 london

  21. Pingback: herve leger resort 2015

  22. Pingback: executive coach repair

  23. Pingback: wedding dresses 6th ave tacoma

  24. Pingback: ray-ban wayfarer folding sunglasses rb4105

  25. Pingback: gafas ray ban 4068

  26. Pingback: giuseppe zanotti nyc showroom address

  27. Pingback: mens louis vuitton resale

  28. Pingback: coach discount uk

  29. Pingback: halter camo wedding dresses

  30. Pingback: ray ban aviators black frame green lens kullananlar

  31. Pingback: backless wedding dresses cheap

  32. Pingback: giuseppe zanotti sneakers aliexpress hair

  33. Pingback: herve leger gold foil jewellery

  34. Pingback: new coach bags 2014

  35. Pingback: wedding dress patterns plus size free

  36. Pingback: ray ban 3025 hangover

  37. Pingback: giuseppe zanotti design outlet neum¨¹nster

  38. Pingback: clutch bottega veneta