Codeforces Round 964 Discussion stream (with hints)

$N/10$ will give you the digit at tenth place.

$N%10$ will give you the digit at ones place.

We can bruteforce all the possible rounds.

The possible pairings are:

• $A_1 - B_1$ and $A_2 - B_2$
• $A_2 - B_2$ and $A_1 - B_1$
• $A_2 - B_1$ and $A_1 - B_2$
• $A_1 - B_2$ and $A_2 - B_1$

Alex can shower on one of the following times:

• Before the first task
• Between any two tasks
• After all tasks

We should check if any of these break is $\ge S$

Solve for the case when there are no ?.

392. Is Subsequence

If you look closely at algorithm in hint 1, notice that whenever we get ? in S, we can replace it with the char we want to match in T.

For each no count the no of $\lfloor \frac{y}{3} \rfloor$ operations we will require to make it 0.

Make one of the nos 0. Then chose that no as $X$.

$3 \cdot 0 = 0$

Let $C$ be the no of operations we have done to get first $0$. Notice that we have multipled some other nos by $3$, $C$ times. So to make them equal to original no, we will have to do $C$ more operations with them as $Y$, and $X=0$

Notice that no of operations required to make $L$ equal to 0 $\le$ Notice that no of operations required to make $L+1$ equal to 0

So in optimal case, we should make $L$ equal to $0$ first, then make all the other nos $0$

To count the sum of no of operations required to make everything in range $L$ to $R$ equal to 0, use prefix sum

Notice that we only need the no of 0s and no of 1s in subsequence to find the median.

So fix the no of 0s and 1s in subsequence and count the no of subsequences.

What is the fastest way to check if a particular no exists in a sorted array or not?

Binary search FTW

Also notice that $\log_2(999) = 10$.

Notorious coincidence?

I think not.

Lets query for area of of $A \times A$ square instead of a rectangle.

If the checker returns $A \times A$, we know that the missing no $\gt A$

If the checker returns $(A+1) \times (A+1)$, we know that the missing no $\le A$

Looks similar to how we search in a sorted array?

Also notice that $\log_3(999) = 7$.

Notorious coincidence?

I think not.

Solution is similar to ternary search

Instead of one mid in binary search lets have 2 mids.

Divide $[L,R]$ range into almost 3 equal parts and see in which range missing no lies.

If we have 2 nos $A,B$ such that $L \lt A \lt B \lt R$.

Area of rectange will be $(A+1) \times (B+1)$ is missing no lies between $[0,A]$

Area of rectange will be $A \times (B+1)$ is missing no lies between $[A+1,B]$

Area of rectange will be $A \times B$ is missing no lies between $[B+1,1000]$