[CODING] PermutationForces solution codeforces

[CODING] PermutationForces solution codeforces

 

You have a binary string 𝑎a of length 𝑛n consisting only of digits  and 11.

You are given 𝑞q queries. In the 𝑖i-th query, you are given two indices 𝑙l and 𝑟r such that 1𝑙𝑟𝑛1≤l≤r≤n.

Let 𝑠=𝑎[𝑙,𝑟]s=a[l,r]. You are allowed to do the following operation on 𝑠s:

  1. Choose two indices 𝑥x and 𝑦y such that 1𝑥𝑦|𝑠|1≤x≤y≤|s|. Let 𝑡t be the substring 𝑡=𝑠[𝑥,𝑦]t=s[x,y]. Then for all 1𝑖|𝑡|11≤i≤|t|−1, the condition 𝑡𝑖𝑡𝑖+1ti≠ti+1 has to hold. Note that 𝑥=𝑦x=y is always a valid substring.
  2. Delete the substring 𝑠[𝑥,𝑦]s[x,y] from 𝑠s.
ALSO READ:-   Unequal Array solution codeforces

For each of the 𝑞q queries, find the minimum number of operations needed to make 𝑠s an empty string.

Note that for a string 𝑠s𝑠[𝑙,𝑟]s[l,r] denotes the subsegment 𝑠𝑙,𝑠𝑙+1,,𝑠𝑟sl,sl+1,…,sr.

Print 𝑞q lines, the 𝑖i-th line representing the minimum number of operations needed for the 𝑖i-th query.

Examples
input

[CODING] PermutationForces solution codeforces

Copy
5 3
11011
2 4
1 5
3 5
output 

Copy
1
3
2

 PermutationForces solution codeforces

input 

Copy
10 3
1001110110
1 10
2 5
5 10
output 

Copy
4
2
3

[CODING] PermutationForces solution codeforces

In the first test case,

  1. The substring is 𝟷𝟶𝟷101, so we can do one operation to make the substring empty.
  2. The substring is 𝟷𝟷𝟶𝟷𝟷11011, so we can do one operation on 𝑠[2,4]s[2,4] to make 𝟷𝟷11, then use two more operations to make the substring empty.
  3. The substring is 𝟶𝟷𝟷011, so we can do one operation on 𝑠[1,2]s[1,2] to make 𝟷1, then use one more operation to make the substring empty.
ALSO READ:-   Controlled Inflation solution codejam

Leave a Comment