Author: Kamil Debowski
Tester: Lewin Gan
Editorialist: Misha Chorniy
Difficulty:
Medium
Pre-Requisites:
bfs
Problem Statement
Given a string S, each character of S can be digit from ‘0’ to ‘9’ and denoting strength of virus. Consider the following process that will be repeated till the string consists of only 1 digit repeated N times: For the current string, we say that index i affects index j if S[i] - S[j] >= |i - j| here, for example, a digit ‘4’ affects a letter ‘2’ if and only if the distance between them is at most 2. simultaneously, for each digit X we find the biggest digit that affects this X and we replace X by that biggest digit. How many iterations will we get the string with all equal letters?
Subtask 1
Let’s simulate process described above, if in some moment we’ll get same string, then we find out required number of iterations. How to estimate expected number of iterations? Each virus won’t be mutate more than 10 times(‘0’->‘1’->‘2’->…‘9’). Longest time of changing the row is 10*N. We can estimate this algorithm in O(10*N^3)
int ans = 0
while True:
ns = s //string after mutation
for i = 1..N:
for j = 1..N:
if s[i]-s[j] >= abs(i-j):
ns[j] = max(ns[j], s[i]) //choose maximal digit which affects ns[j]
if s == ns:
break
ans += 1
print ans
Subtask 2
In this subtask is
guaranteed that answer is not more than 10. But one iteration of the cycle above takes a lot of time, crucial optimization is to iterate j not in a range 1…N, because if |j-i|>10 s[i] doesn’t affect on s[j]. Instead terate j in a range max(1,i-10)…min(N,i+10). Now algorithm takes O(N*20*10) time, what is enough to pass.
Subtask 3
We have a problem with only with zeroes and ones. After one operation some zeroes become ones. For instance, 0010 -> 0111 -> 1111. If we don’t have any ‘1’, in this case answer is 0, otherwise let’s consider all consecutive groups of zeroes, call arbitrary group as T, if group has ‘1’ from the left side and ‘1’ from the right side, then time when this group become equal “1111…1” is (size(T) + 1) / 2, if group hasn’t ‘1’ from some side, time will be size(T). We need to get maximum over all such values. A complexity of this algorithm is O(N)
ans = 0
for i = 1..N:
if S[i]=='1':
continue
j=i
while j + 1 <= N and S[j + 1] == '0'
j += 1
if i == 1 and j == N
break
len = j - i + 1
if i == 1 or j == N:
ans = max(ans, len)
else:
ans = max(ans, (len + 1) / 2)
i = j + 1
print ans
Subtask 4
Key observation is that every digit won’t change more than 10 times, total number of changes won’t be more than 10*N. We can use something like bfs, after first iteration keep in mind all positions where virus was changed, and try to go from those positions(where something changes in 1 step), find new positions where something changes in 2 steps, after that in 3 steps and so further.
queue a, b
for i = 1..N:
a.push(i)
vis[i] = 0
ns = s
cleaner = 0 //wise cleaning of array, because we can have n iterations, and every time cleaning of the array vis can be very long process
//vis[i] != cleaner <-> vis[i] == 0
//vis[i] == cleaner <-> vis[i] == 1
while True:
cleaner += 1
b.clear()
for i in a:
for j = max(1,i-10)..min(i+10,N):
if s[i]-s[j] >= abs(i-j) and ns[j] < s[i]:
ns[j] = s[i]
if vis[j] != cleaner //don't need to add j more than one time
vis[j] = cleaner
b.push(j)
if b.empty(): //if we can't change anything
break
a.clear()
for i in b
s[b[i]] = ns[b[i]] // copying value of positions where something changes
a.push(i)
ans += 1
print ans
Total complexity of this algorithm is equal O(number of changes * number of transitions) = O(N * 10 * 20) = O(200 * N)
Solution:
Setter’s solution can be found here
Tester’s solution can be found here
Please feel free to post comments if anything is not clear to you.
