White to move and mate in 3
Monday, December 31, 2012
Sunday, December 30, 2012
Saturday, December 29, 2012
Thursday, December 27, 2012
Wednesday, December 26, 2012
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:
Sunday, December 23, 2012
Aeroflot Open 2013
After a period of speculation that the Aeroflot Open might be canceled, the Russian Chess Federation finally announced that the 2013 edition will take place from 12th to 17th February at the exhibition center InfoProstranstvo in Moscow.
The next edition will be dedicated to the 90th anniversary of the leading Russian airline company. The total prize fund of all tournaments is 150 000 USD.
Aeroflot Open is starting immediately after the International Chess Festival Moscow Open-2013.
The novelty is that the classical time control is abandoned and all events will be played with rapid and blitz time controls. Last winner of the “classical” Open was Polish Grandmaster Mateusz Bartel.
Exhibition Center Info Prostranstvo in Moscow
Subscribe to:
Posts (Atom)