PROBLEM LINK:
Author, Tester & Editorialist: Devanshu Garg
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
https://www.codechef.com/problems/GESSCODE
EXPLANATION:
The answer may be rather large, because it grows exponentially with the growth of n. Indeed, there are 10 ways to choose the first digit, then 1 or 2 ways to choose the second one, 1 or 2 ways for the third one, and so on. So the number of ways doesn’t exceed 10 * 2^{n - 1}.
The problem can be solved by dynamic programming. Let d_{ij} be the number of ways to get first i digits of the correct code with the i^{th} digit equal to j. From such part of the code we can obtain a part of size i + 1 with (i+1)^{th} digit equal to (j + a_i + 1) / 2 or (j + a_{i + 1} + 1) / 2, where a_i is the i^{th} digit of Mr. Garg’s code. So if we have d_{ij} for all j, we can obtain d_{i + 1, j}.
Do not forget to subtract 1, if Mr. Garg can obtain his own code. It will happen in case when each two successive digits in the given code differs at most by 1.
SOLUTIONS:
Setter's Solution
num = list(map(int, input()))
n = len(num)
dp = [[0] * 10 for i in range(n + 1)]
for i in range(10):
dp[0][i] = 1
for i in range(n - 1):
for j in range(10):
dp[i + 1][(num[i + 1] + j) // 2] += dp[i][j]
if (num[i + 1] + j) & 1:
dp[i + 1][(num[i + 1] + j) // 2 + 1] += dp[i][j]
own_code = 1
for i in range(n - 1):
if abs(num[i + 1] - num[i]) > 1:
own_code = 0
print(sum(dp[n - 1]) - own_code)
Editorialist's Solution
num = list(map(int, input()))
n = len(num)
dp = [[0] * 10 for i in range(n)]
for i in range(10):
dp[n - 1][i] = 1
for i in range(n - 2, -1, -1):
for j in range(10):
if (num[i + 1] + j) % 2 == 0:
dp[i][j] = dp[i + 1][(num[i + 1] + j) // 2]
else:
dp[i][j] = dp[i + 1][(num[i + 1] + j) // 2] + dp[i + 1][(num[i + 1] + j + 1) // 2]
own_code = 1
for i in range(n - 1):
if (num[i] + num[i + 1]) // 2 != num[i + 1] and (num[i] + num[i + 1] + 1) // 2 != num[i + 1]:
own_code = 0
print(sum(dp[0]) - own_code)
Well this was my approach, feel free to share your approach here. Suggestions are always welcomed.