Hey everyone,
There are no CodeForces rounds coming up, so I thought I would set up a training round in the new Gym. The problems are from our local contest which I helped organize last October. We used it to select our team for the ACM-ICPC. There is a large range of problem difficulties, so I am sure everyone will have interesting problems to solve.
It will be held on Saturday, 1/28 at 8am Moscow time (4-hour contest) in the CodeForces Gym. I hope you enjoy the problems!
Update: The contest is over. Thanks for participating! If you didn't, please check out the problems anyway :) Feel free to discuss the problems in the comments below; I can outline solutions but I don't have a formal editorial.
Online registration for the 2011 Stanford Local Programming Contest is now closed!
Are first testcases the same with those in problem statements?
No, there is only 1 test for each problem (all cases at once).
can anybody explain me solution for B?
find a regular pattern
The easiest way in my opinion is to consider a DP on width of currently covered rows and number of currently painted balls (figure out why width works and why you don't need left + right). This would work even for a n × m grid.
However, some solutions are based on counting arguments, and some people just noticed a pattern :)
For problem C,is the shortest path on the MST of the graph? And, how can I get the solutions?
If you remove one edge, you get a tree. Then you can compute shortest path efficiently via LCA (segment tree) as d(u, v). Suppose the edge you removed was (a, b). Then the shortest distance in the graph is min(d(u, v), d(u, a) + w(a, b) + d(b, v), d(u, b) + w(a, b) + d(a, v)).
What's the idea behind G?
We can turn it into a set of difference constraints rather than sum constraints (e.g. replace bi with - ci). Then look at using Bellman-Ford for determining whether a set of difference constraints can be satisfied.
can anybody provide a general editorial for this contest? if it's too much trouble a general summary would do fine as well
-_- why necro bump this when you can make your own blog post