4 ms·
In the university, we had a team for ACM ICPC. We helped our professor organize a local competition, to encourage more people to practice. We participated in th
by aljgz 1y ago
In the university, we had a team for ACM ICPC. We helped our professor organize a local competition, to encourage more people to practice. We participated in that competition, of course.
One question would give you a few numbers no greater than 13, and you would output the number of ways to put N queens on the cheeseboard of those sizes. Not a difficult problem, but our first implementation, needed 2 minutes while time limit was 1 minute. We could optimize, but we decided to run it for all possible numbers, write a new program with just a switch-case. This was q perfectly legal move. We could see his face while judging our submission, his huge surprise when code ended in milliseconds, his look of admiration at us, the curiosity about the solution, and finally his reaction when he checked out our code. Priceless.
- ivan_gammel 1y agoFun enough, in commercial software engineering your solution won’t raise eyebrows as something routine and expected, but an efficient algorithm could do.
- ape4 1y agoIts called https://en.wikipedia.org/wiki/Memoization https://en.wikipedia.org/wiki/Memoization
- pvitz 1y agoMore like "precomputed table" and "table lookup"...
- marcosdumay 1y agoMemoization is the kind of dynamic programming the first post on the thread is talking about.
- TheJoeMan 1y agoHad a similar problem in a highschool comp. sci. class with a maze-following algorithm where you got points off for back-tracking. Turns out your code could pre-fetch the entire maze before making a move, which I think goes against the spirit of the exercise.