Tuesday, December 25, 2012

UVa 11472 - Beautiful Numbers | Solution

Problem Overview:

Name: UVa 11472 - Beautiful Numbers
Link: http://uva.onlinejudge.org/external/114/11472.html
Time Limit: 3s
Memory Limit:

My suggested solution:

Difficulty: Medium
Hint: This problem can be solved with dp and bitmask technique. A 3D array of size 100 * 2 ^ 10 * 10 (about 1M), which is acceptable in memory limit, is needed to store the results. Then, the array can be filled by a recursive formula called f(i, j, k) - number of ways to make a number with i digits, using j as a mask and k is the last digit. The mask is definited as usual, i.e. if i-th digit from right to left of the mask value in binary notation is 1, digit i was used before and was not otherwise. Now f(i, j | (1 << k), k)  = sum of all f(i - 1, j, k - 1) if(k - 1 >= 0), plus sum of all f(i - 1, j, k + 1) if (k + 1 < n). Remember to handle the special case when i = 1, i.e. no leading zero is allowed in beautiful numbers. The final answer is sum of all f(i, (1 << n) - 1, j), i = 1..m, j = 0..n-1
Complexity: M * N * 2 ^ N
Algorithm: dp + bitmask
Related problem:


My accepted code: