TANSWTCH - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Ayush Jaggi

Tester: Anurag Anand

Editorialist: Anurag Anand

DIFFICULTY:

CAKEWALK.

PREREQUISITES:

Ad Hoc

PROBLEM:

Given the configuration of a sequence of switches as a string, we need to toggle some of the switches such that all the ‘Off’ switches appear before ‘On’ switches.

QUICK EXPLANATION:

We can iterate over the number of ‘Off’ switches in the final sequence and find the number of toggles required to achieve that configuration.

EXPLANATION:

Let S be the input string. Let N be the length of S. Let us assume the characters of the string are indexed from 0 to N-1.

So, if S = “ONO”, then N =3, S[0] = ‘O’, S[1] = ‘N’ and S[2] = ‘O’.

‘O’ denotes ‘Off’ and ‘N’ represents ‘On’. We’ll use ‘O’ and ‘N’ from now onwards.

Let R be the string obtained from S after performing some toggles such that in R, all ‘O’ characters occur before ‘N’. Let us consider the count of ‘O’ in R after toggling some switches. It can be anything between 0 to N. If the count of ‘O’ is K, then R[i] = ‘O’ for 0 \le i < K and R[i] = ‘N’ for K \le i < N. So, if we fix the count of ‘O’ to be K, then for all index i where S[i] \ne R[i] we’ll require one toggle. So, the number of toggles required is number of index i such that 0 \le i < K and S[i] = ‘N’ or K \le i < N and S[i] = ‘O’. We can iterate over K=0 to K=N and find the number of toggles required for each K. The minimum among all will be answer. You can refer to the following pseudo code.


ans = INFINITY
for K = 0 to N
	count = 0
	for i = 0 to K - 1
		if S[i] == 'N' count = count + 1
	endfor
	for i = K to N - 1
		if S[i] == 'O' count = count + 1
	endfor
	ans = min(ans, count)
endfor

The time complexity of this solution is O(N^2) for each test case.

ALTERNATIVE SOLUTION:

There is also a solution with time complexity O(N). At each point of time, we only need the count of ‘N’ for some prefix and the count of ‘O’ for some suffix of S. Let countOff be the total count of ‘O’ and countOn be the total count of ‘N’ in S. For K=0, all ‘O’ must be converted to ‘N’, hence the number of toggles needed = countOff. Let us consider K>0 case. Now, we iterate over the characters of S from 0 to N-1. We maintain prefOff and prefOn which are the count of ‘O’ and ‘N’ respectively, encountered till now. Number of toggles needed for a given K = count of ‘N’ from i=0 to i=K-1 + count of ’O' from i=K to i=N-1 which can also be written as count of ‘O’ from i=0 to i=K-1 + countOff - count of ‘N’ from i=0 to i=K-1, or prefOn + countOff - prefOff.


countOff = 0, countOn = 0
for i = 0 to N - 1
	if S[i] == 'O' countOff = countOff + 1
	if S[i] == 'N' countOn = countOn + 1
endfor

ans = countOff
prefOff = 0, prefOn = 0
for i = 0 to N - 1
	if S[i] == 'O' prefOff = prefOff + 1
	if S[i] == 'N' prefOn = prefOn + 1
	ans = min(ans, prefOn + countOff - prefOff)
endfor

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.