DIGVIRUS - Editorial

Practice

Contest

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.

2 Likes

Where’s the editorial for closest point queries ? question link

1 Like

EDIT2:
Now I am getting full points, but still have a concern which I have posted in another comment below.
Thanks for helping!

EDIT:

I made few changes in the code and made it bit faster and now the answer is correct but still I am getting only 50 points and getting a RE (error) in subtask two.
Please help me out with that.

Also please give me tips for dos and donts in c++ 14 code submission in codechef compiler :slight_smile:

https://www.codechef.com/viewsolution/13414507


Please help me find the error in my code, when I run it on my machine it runs absolutely correctly and even the logic is correct. I dont understand why is it giving wrong answer every time, it happened even yesterday during contest and I could not submit my answer correctly :frowning:

Here is my solution https://www.codechef.com/viewsolution/13414391

Am I missing out on something that should not be used or be used when submitting for codechef’s compiler?? Thanks for the help!

in subtask2 ,we have 1 ≤ |S| ≤ 10^5,but you just initailize array pos[] 50 elements .

in my original solution I took care of that but I am not sure if I understand the subtasks and constraints for this question.
Can you please explain me the actual meaning of constraints and substaks in this problem.
(I initially thought that those are the constraints we must check, i.e why I had a check for the input of T should be less than 10 and greater than 1, so it means that the constraints will always be followed by the question and we dont have to check for those constraints?)
I am a new user here so I not very well acquainted with constraints and subtasks. So it would be great if you could clarify my this doubt also

Thank you very much @thidailoc

How to ask questions!?

this problem certains these constraints in all of testcase:
1 ≤ T ≤ 10
1 ≤ |S| ≤ 10^5 (here, |S| denotes the length of S)
so you needn’t check for the input of T.

50% testcases -> 1 ≤ |S| ≤ 50
50% testcases -> 1 ≤ |S| ≤ 10^5

you just got 50 points because you just solved 50% testcases with 1 ≤ |S| ≤ 50
if you want to get 100points ,you have to solve the biggest constraint (1 ≤ |S| ≤ 10^5)

how come the number of transitions taken as 20??

Why do we do b.push(i) when j is the position that has its value changed. Why it is not b.push(j)? Any help would be really appreciated

Here is the solution with the direct implementation of the above algorithm for subtask 4. https://www.codechef.com/submit/complete/13421491

Is N*10 passes a weak upper bound?
Considering the fact that finally the array will be equal to the largest number in the array and at each pass atleast one cell will be affected due to the largest element.
There shouldn’t be more than n passes right?
Please correct me if i am wrong!

i am a beginner and do not understand the last subtask. can anyone help me…thanks n advance :slight_smile:

Here: https://discuss.codechef.com/questions/97031/closestq-editorial

1 Like

Fixed, thanks