Here's a short list of some mixed geometry flavored problems from POJ.
There is a possibility that some of these may not be geometry problem at all, tried my best to sort them out though. Also, some of these problems are not solvable by only geometry knowledge. Graph, dynamic programming, and understanding of advanced data structure may also be required.
Here is a short list of network flow and bpm problems that I managed to solve from SPOJ and HDU. This is not much and there are other sources of these kinds of problems, but I think these are some good starting points. Also I did not classify them on the types of flow or bpm, that would be up to the reader.
| ANGELS | BABY | DIVREL | FASTFLOW | MATCHING |
| MSE06I | MTOTALF | MUDDY | PCPC12H | PROFIT |
| PT07X | QUEST4 | SCITIES | STEAD | TAXI |
| 1532 | 1533 | 1853 | 2448 | 2686 |
| 2732 | 2833 | 3081 | 3277 | 3315 |
| 3376 | 3395 | 3416 | 3419 | 3435 |
| 3468 | 3472 | 3488 | 3491 | 3572 |
| 3667 | 3987 | 3998 | 4183 | 4309 |
Note: UVa has a lot of flow and bpm problems, please visit uHunt for guidelines.
Note: It is very possible that there are many other problems from these online judges which can be solved by flow or bpm algorithms. And, some problems here could be mistakenly added as flow or bpm category due to copy paste errors. Please feel free to leave a note on the comment section, add more links if you like to. Happy coding \m/
Sphere Online Judge a.k.a. SPOJ is a very good online judge. Still, beginners face a lot of trouble when they first come to SPOJ, mainly because SPOJ is not as well categorized as some other judges out there. Recently SPOJ is trying to offer problem hints, but due to being community driven, this is still a long shot. Classification hints for SPOJ problems are not commonly available in the internet as well. So far I have managed to solve a few dynamic problems from SPOJ and I think for someone who is trying to practice dynamic programming problems from SPOJ, this short list might come handy.
Please feel free to add more in the comments. Thanks
Problem link: SPOJ Problem Set (classical): 9952. 111…1 Squared
Interesting and fun problem. This is one of those problems that you can sense a pattern from miles away. Just do some bruteforce and print the patterns. You can use pen and paper too, but Python is surely a better option when you have it. All I did is write some bruteforce in my python interpreter, and the pattern is instantly visible, here is the output of f(n)2 for n = 1 to 50:
1 121 12321 1234321 123454321 12345654321 1234567654321 123456787654321 12345678987654321 1234567900987654321 123456790120987654321 12345679012320987654321 1234567901234320987654321 123456790123454320987654321 12345679012345654320987654321 1234567901234567654320987654321 123456790123456787654320987654321 12345679012345678987654320987654321 1234567901234567900987654320987654321 123456790123456790120987654320987654321 12345679012345679012320987654320987654321 1234567901234567901234320987654320987654321 123456790123456790123454320987654320987654321 12345679012345679012345654320987654320987654321 1234567901234567901234567654320987654320987654321 123456790123456790123456787654320987654320987654321 12345679012345679012345678987654320987654320987654321 1234567901234567901234567900987654320987654320987654321 123456790123456790123456790120987654320987654320987654321 12345679012345679012345679012320987654320987654320987654321 1234567901234567901234567901234320987654320987654320987654321 123456790123456790123456790123454320987654320987654320987654321 12345679012345679012345679012345654320987654320987654320987654321 1234567901234567901234567901234567654320987654320987654320987654321 123456790123456790123456790123456787654320987654320987654320987654321 12345679012345679012345679012345678987654320987654320987654320987654321 1234567901234567901234567901234567900987654320987654320987654320987654321 123456790123456790123456790123456790120987654320987654320987654320987654321 12345679012345679012345679012345679012320987654320987654320987654320987654321 1234567901234567901234567901234567901234320987654320987654320987654320987654321 123456790123456790123456790123456790123454320987654320987654320987654320987654321 12345679012345679012345679012345679012345654320987654320987654320987654320987654321 1234567901234567901234567901234567901234567654320987654320987654320987654320987654321 123456790123456790123456790123456790123456787654320987654320987654320987654320987654321 12345679012345679012345679012345679012345678987654320987654320987654320987654320987654321 1234567901234567901234567901234567901234567900987654320987654320987654320987654320987654321 123456790123456790123456790123456790123456790120987654320987654320987654320987654320987654321 12345679012345679012345679012345679012345679012320987654320987654320987654320987654320987654321 1234567901234567901234567901234567901234567901234320987654320987654320987654320987654320987654321 123456790123456790123456790123456790123456790123454320987654320987654320987654320987654320987654321
Beautiful, isn't it?
