Recently Vadik had to say goodbye to yet another member of Team.GOV. Vadik
had to find the new team member to participate in the Ural Championship.
Suddenly Vadik thought that mixed teams are allowed, and he had a
good Chinese friend — Xiaohong Hao, a participant of the ACM ICPC World
Finals. A perfect choice!
And Vadik is now sitting in front of a computer and is typing a letter.
I need a team member for the Ural Championship. Would you like to
play in Team.GOV? If interested, send me a solution of the test task by
A Hamming distance between two strings of equal lengths is the number of
characters that are not same in these two strings. Let's say that distance
between s1 and a shorter s2 is the sum of Hamming distances between
s2 and all substrings of s1 with length equal to the length of s2.
We'll call a string to be partial one if it may contain a character “?”
apart from alphabet characters. Two partial strings are given. You're
asked to replace question marks with alphabet characters in such a way
that distance between transformed strings is minimal.
You have to solve this problem for the case when the first string is cyclical.
Best of luck!
P.S. Oh, the string is called to be cyclical one if except for regular
substrings is also has the substrings that are a concatenation of a suffix and a
prefix. For instance, a regular string “abcd” has two
substrings of length 3: “abc” and “bcd”. A cyclical string “abcd” in
addition to those two ones has two more substrings of length 3: “cd” +
“a” = “cda”, “d” + “ab” = “dab”.
Specially for Xiaohong Vadik made tests with hieroglyphs instead of
Latin letters in both strings.
The input data consist of two blocks two lines each. The first block
describes the cyclical string s and the second block describes the
string t. In the first line of each block you are given the number n
that is a length of string (1 ≤ n ≤ 100 000). In the second line
of the block you are given n non-negative integers separated with a
space. Positive integers denote hieroglyphs and zero denotes the question
mark. Numbers denoting hieroglyphs don't exceed 100 000.
Replace question marks in s and in t with hieroglyphs in such a way
that distance between the strings that are obtained by replacement is
minimal. Output the resulting distance.
2 1 1 0 2
3 0 3 0
You need replace the question mark in s with the third hieroglyph, and
question marks in t with the first and the second hieroglyphs respectively.
Cyclical string “21132” has substrings “2113”, “1132”, “1322”,
“3221” and “2211”. Hamming distance from string “3132” to these
substrings is equal to three, one, three, three, four respectively. The sum
of these distances is equal to fourteen.
Problem Author: Mikhail Rubinchik
Problem Source: Ural Regional School Programming Contest 2011