This year I prepared problems for ACM-ICPC regional Asia Jakarta 2014. I have been creating problems for competitive programming, let say since 2010 for national level. But this was the first time I prepared for international level competition. I submitted 3 problems and 2 of them were accepted. One problem called Lagged Speed was for INC (National level selection before go to ACM-ICPC) and Maze Mayhem for ACM-ICPC regional Asia Jakarta.
Lagged Speed is a problem about pattern. The best way to solve this problem is to code brute-force solution and interpolate the output. You should find constant O(1) solution in no time. I got inspiration for this problem while taking a bath. You know, sometimes you want to set your shower’s temperature to certain amount, but you ended up set it too hot (or too cold). Then you change it a little bit, but after a while you realised you changed too much, and had the temperature too cold. Then you change it again, and so on. You repeat that steps (change, wait, change, wait) until finally you are satisfied with the temperature. Now, change the shower with a car, change the temperature with the car’s speed, and add some (not so) random math function. Voila, You have an ACM-ICPC problem
In Maze Mayhem problem, we must compute all N x M grid-maze configurations with at most K obstacles placed where there is no valid path from top-left panel to bottom-right panel. We can simply calculate it via dynamic programming approach. By the time I created the problem, I was thinking that there might exists O(NM) dynamic programming solution. The idea should be similar to 2D DP sum problem. However after 2 days full with sketching, coding, and testing, those approach is impossible (at least I can’t find it in 2 days :D). So I decided that the O(2(N+M)) approach is the expected solution. This problem become somewhat standard DP bitmasking problem, with some tweaking on its DP-state formulation. Shockingly, only 4 teams managed to solve the problem during the competition.
One thing about this problem is, initially there was no K (total obstacles) constraint. However, because NxM were too small ( 1 <= N,M <= 100), one can precompute the solutions using slower approach, as there are only 100 different maze size. Contestant then simply use 100 if-cases based on pre-computed solution. Thus, new constraint K is added.
Overall, I am happy to be able to contribute in ACM-ICPC as problem setter. After 4 years participating as contestant, I myself found that take a role as problem setter is fun. Looking forward for next problem setting opportunity.