### yellow_13's blog

By yellow_13, history, 8 months ago, The following problems are from the Codenation coding round held on 12th June. I was not able to solve these problems, and it would be very helpful if you guys could give a rough idea of the solution.

Q1. You have two integer arrays $X$ and $Y$ of size $n$. Initially, all the elements in both these arrays are $0$. You have to process $q$ queries, each query can be of three types:

• $1$ $l$ $r$ : Flip all $0$ to $1$ and all $1$ to $0$ in the range $[l,...,r]$ in the array $X$

• $2$ $p$ : $Y_i = Y_i + p\cdot X_i$ for all $i \in [1,...,n]$

• $3$ $j$ : Find $Y_j$

Input: $n$, $q$, and all the queries, Output: For every query of type $3$, print $Y_j$

Constraints: $1 \leq n \leq 10^5$, $1 \leq q \leq 5\cdot 10^5$, $1 \leq l \leq r \leq n$, $1\leq p\leq 10^9$, $1 \leq j \leq n$

Q2. Given a number $n$, find the number of actual greater pairs. A pair $(a,b)$ is an actual greater pair if:

• $0 \leq a < b \leq n$
• sum of digits of $a <$ sum of digits of $b$

Since $n$ can be very large, you have to input it as a string. Return the number of actual greater pairs modulo $1e9+7$

Input: $n$, Output: number of actual greater pairs modulo $1e9 + 7$

Constraints: $1 \leq n \leq 10^{100}$ Comments (5)
 » 7 months ago, # | ← Rev. 5 →   Problem 2 is a standered digit dp problem. Note that maximum sum of digits is $909$. Index the digits of the number from right to left increasing order (rightmost digit having index $0$). From now on, I will denote $i^{th}$ digit of a number $k$ as $k[i]$ and sum of its digits as $D(k)$. Let $dp[i][d][t_b][t_a]$, denote the number of pairs of numbers $(a,b)$ of $(i+1)$ digits (its digits are indexed from $[0..i]$ with $D(b) - D(a) + 909 = d$. $t_b$ denotes the tight condition for number $b$. If $t_b = 1$ implies that due to constraint $b<=n$, I can't place any digit freely in $i^{th}$ position. I have to use digit such that $b[i]<=n[i]$. Similarly, $t_a$ denotes the tight condition on number $a$ due to constraint $a909$ and $len(n)$ denotes the number of digits of $n$.
•  » » Thanks a lot for taking the time to explain the transitions in such detail!
•  » » » You're welcome :)
•  » » » Wo
 » nice