Author: Diego Vizia
| Little Knights is IMPOSSIBLE without a table|
Date: 2012-12-10 18:45:10
I've been struggling with 225 - Little Knights for many days. After doing many optimizations on my program, I managed to get up to Test Case 186 with a DP algorithm with lots of prunes. But that's as far as I can go.
I decided to google the problem, and I found some chinese pages with solutions to the problem similar to my own, but ALL of them used a table to give the answer when N = 10.
So, in other words, NOBODY solved this problem in the time limit of 500ms LEGALLY. They all used a precomputed table of answers for N = 10.
If there's anyone out there who has managed to get all test cases accepted without a precomputed table, I'd like to know, please.
Thanks in advance.
| 22.10.12 - The problems from the Southern Subregional Programming Contest 2012 added to the problemset archive (542 - 553). |
22.10.12 - After the start of the contest the statements in PDF will be available by the link.
23.10.11 - The problems from the Southern Subregional Programming Contest 2011 added to the problemset archive (530 - 541).