### PROBLEM LINK:

**Author:** Sajal Agrawal

**Tester:** Alexey Zayakin

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

Euclidean algorithm

### PROBLEM:

You’re given string S which starts with 1 and ends with 0. You have to flip minimum possible number of characters in the string to make it containing exactly X humongous subsequences (i.e. such that they’re of form 1010\dots10).

### QUICK EXPLANATION:

If you consider number of (10)^k1 subsequences A and number of (10)^k subsequences B, you can unwind all possible strings having B=X+1 and proper length |S| via Euclidean algorithm.

### EXPLANATION:

Consider some 10-string. How many humongous subsequences does it contain? Let’s keep number of (10)^k 1-subsequences A and number of (10)^k subsequences B. Note that empty string is counted in B as (10)^0. We can see that if we add 1 at the end of the string, we will have \begin{cases}A'=A+B,\\B'=B\end{cases} and if we add 0, we will have \begin{cases}A'=A,\\B'=A+B\end{cases}. Now if we fix A and B, it will be possible for us to recover the initial string.

We should note by now that recovering string given A and B is similar to Euclidean algorithm. While A is greater then B we will subtract B from A, we can compress that steps by making \begin{cases}A'=A-\lfloor A / B \rfloor \cdot B\\B'=B\end{cases} and adding \lfloor A / B \rfloor ones at the end of string. Everything is similar for the case B > A. We should do it until we reach empty string for which A=0, B=1. That means that we should use co-prime A and B and since last digit is necessarily zero, we will have A < B at the end so we can consider every possible A which is co-prime with B=X+1. One is added since we consider empty string now. And since basic case is A=0,B=1 you should be careful when you reach A=1 to not fall in A=1,B=0 instead. Here is code which generates a string given A and B:

```
string gen(int a, int b) {
if(a == b) {
return "1";
} else if(a < b) {
return gen(a, b % a + (a == 1)) + string(b / a - (a == 1), '0');
} else {
return gen(a % b + (b == 1), b) + string(a / b - (b == 1), '1');
}
}
```

This one is slow however you should rewrite it in non-recursive way and consider the case when string gets too long. Now you need to brute every single A, there are O(X) of them and generate a string in O(\log X + |S|). This will solve the problem.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.