Editorial for BPC 1 J4 - Assignment of the Year - Olympiads Online Judge

Editorial for BPC 1 J4 - Assignment of the Year

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: squishybanana04

Hint 1

This is a DP problem. You can use $dp[i][j] =$ $d p [i] [j] =$ whether or not it is possible to produce $j$ $j$ using the first $i$ $i$ digits.

Hint 2

You only need to test numbers that are up to $5$ $5$ digits long. All numbers with $6$ $6$ digits or more are guaranteed to be greater than $M$ $M$ .

Solution

Starting from the left, apply the following process starting from each digit:

If the $i^\text{th}$ $i^{th}$ digit is $0$ $0$ we can skip the next 3 steps and copy $dp[i]$ $d p [i]$ into $dp[i+1]$ $d p [i + 1]$ .
Use $X$ $X$ digits, where $X$ $X$ is $1$ $1$ greater than the amount used in the previous iteration, and $X = 1$ $X = 1$ on the first. Let $Y$ $Y$ be the number made out of these digits.
Stop if $Y > M$ $Y > M$ .
For all $j$ $j$ , set $dp[i+X][j+Y] = \max(dp[i][j], dp[i+X][j+Y])$ $d p [i + X] [j + Y] = max (d p [i] [j], d p [i + X] [j + Y])$ .

At the end of this process, you can count the number of values that you've created in $dp[i]$ $d p [i]$ .

Comments

There are no comments at the moment.