Problem Overview:
Name: UVa 12532 - Interval Product
Link: http://uva.onlinejudge.org/external/125/12532.html
Time Limit: 2s
Memory Limit:
My suggested solution:
Difficulty: Medium
Hint: This problem can also be solved by IT algorithm, but BIT is chosen because it's easy and fast to code. Obviously, there are an observation: the result of a product command of all integers between I and J will be zero if at least one of them is zero, it will be positive if the number of negative integers is divisible by 2, and it will be negative otherwise. There are 2 initial binary indexed trees, one stores the number of zeros (zero-tree) and other keeps the number of negative integers (nega-tree). With every integer read from input, the zero-tree should be adjusted by +1 at its position if it is a zero, and if it is a negative integer, the nega-tree should be updated. The changing query can be divided into 2 steps: removing an array element and inserting another element right there. The trees should be updated right after each step. Now, every product command from I to J can be easily calculated by counting the number of zeros and negative integers between I and J based on the observation above.
Complexity: There are K commands, each of which is a change or a product command. The update function and the range sum function can be done in O(logN). So the complexity is O(K * logN)
Algorithm: BIT
Related problem:
Showing posts with label UVa. Show all posts
Showing posts with label UVa. Show all posts
Friday, January 25, 2013
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:
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:
Subscribe to:
Posts (Atom)