Eli Bendersky's website I've always been fascinated with solving programming problems. There are lots to be found online, from various ACM college championships, int-l CS championships, etc.
Finally, I found a great page with many problems to solve and an online judge system. You pick a problem, solve it, and submit the solution. The website automatically compiles your code and runs it with some test inputs, and tells you if your solution is accepted/compilation failed/exceeded time/memory limit/wrong answer, etc.
So, I opened an account (# 30363) and already solved 8 problems. All pretty simple, but I plan to move to more interesting problems next.
The problems I solved so far:
Note, for a direct access to a problem, point the browser to
http://acm.timus.ru/problem.aspx?space=1#=PROBLEM_NUMBER
- 1000 - The basic first problem, just add two input numbers A+B, to get a feel of the online judge system. No comments needed.
- 1025 - Democracy in Danger. The trick is sorting all the groups, from smallest to largest. Then, I must pick the first K/2 + 1 groups and calculate what it takes to be a majority in them, which is of course N(i)/2 + 1 for group i.
- 1044 - Sometimes you have to be dirty. I didn't think of any nice solution, so I just brute-forced it and then hard coded the answers for submission (which is time limited). Brute-force solution is (of course) trivial - go over all numbers with N digits, and increment a counter if they're lucky.
- 1068 - The trick is the negative value. It can be solved with a formula, or with a loop.
- 1082 - I admit I was lost here. But I noticed that sequences of rising integers cause the right answer, so I hard coded it... Again, sometimes you must be dirty.
- 1196 - First read the teacher's years, shove'em in a vector. Then, for each read student's number, use STL's binary_search on the vector. Overall O(n log(m)). Guess it could be made better with a hash, but it was good enough in performance and was accepted.
- 1197 - Not really a challenge for someone who writes a full chess program. I solved this the dirty way, just to get over with it. Start with 8, reduce 2 for each rank 2 and 7 and file b and g, etc...
- 1264 - One of those problems where you can either see the trick or waste tons of time. Obviously, the answer is simply N * (M + 1) for every input.
That's it, for now. Hopefully I will get to solving the more challenging problems later, and will write about them more in length.