PROBLEM LINK: BOMB
Setter: Blackrise (Saurabh Kishore Tiwari)
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Combinatorics.
EXPLANATION
Since the strength of each warrior will be between {0} - {9}, we can calculate the frequency of each digit.
Now, all we need to do is generate all different numbers and store its mod value with {Z}. For this, we consider a dp[n][z].
For every universe, you travel all 10 digits and use the mod value calculated in the previous state to find out the number of possible answers for the current state using the given loop
for (int i = 0; i < 10; i++) dp[1][i % z] += freq[i];
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
if (freq[j] == 0) continue;
for (int k = 0; k < z; k++) {
int temp = k * 10 + j;
temp %= z;
dp[i][temp] += (long) freq[j] * dp[i - 1][k];
}
}
}
Once we have done this, we know the power of all possible monsters. Print the number of monsters with power less than equal to {P}.
Time Complexity: {O} {(} {N} x {10} x {Z} {)}
Space Complexity: {O} {(} {N} x {Z} {)}
Problem Setter Code: Solution