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] =$ ~dp[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^\text{th}~ digit is $0$ ~0~ we can skip the next 3 steps and copy $dp[i]$ ~dp[i]~ into $dp[i+1]$ ~dp[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])$ .

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

Comments

There are no comments at the moment.