yellow_13's blog

By yellow_13, history, 6 months ago, In English

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}$$$

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
5 months ago, # |
Rev. 5   Vote: I like it +14 Vote: I do not like it

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 $$$a<b$$$.

I think transitions will look like this, once you know $$$dp[i][d][t_b][t_a]$$$, iterate over all $$$b[i+1]$$$ and $$$a[i+1]$$$ and update the next state accordingly (by placing the $$$(i+1)^{th}$$$ digit):

For all $$$b[i+1]$$$ and $$$a[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][0][0] += dp[i][d][0][0]$$$

Only if $$$a[i+1] = b[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][0][1] += dp[i][d][0][1]$$$

Only if $$$a[i+1] < b[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][0][1] += dp[i][d][0][0]$$$

Only if $$$b[i+1]=n[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][1][0] += dp[i][d][1][0]$$$

Only if $$$b[i+1]<n[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][1][0] += dp[i][d][0][0]$$$

Only if $$$b[i+1]=a[i+1]=n[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][1][1] += dp[i][d][1][1]$$$

Only if $$$a[i+1]<b[i+1]=n[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][1][1] += dp[i][d][1][0]$$$

Only if $$$a[i+1]=b[i+1]<n[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][1][1] += dp[i][d][0][1]$$$

Only if $$$a[i+1]<b[i+1]<n[i+1]$$$:

$$$dp[i+1][d+b[i+1]-a[i+1]][1][1] += dp[i][d][0][0]$$$

Answer will be the sum of all $$$dp[len(n)-1][k][1][1]$$$ such that $$$k>909$$$ and $$$len(n)$$$ denotes the number of digits of $$$n$$$.

»
5 months ago, # |
  Vote: I like it -10 Vote: I do not like it

nice