(Это перевод оригинального текста, пожалуйста, старайтесь использовать английский в комментариях)
Всем привет.
Пока на Codeforces нет раундов, я подготовил тренировочное соревнование в новом проекте Codeforces::Тренировки. Будут использованы задачи с прошедшего в Стэнфорде контеста, который я помогал проводить в конце октября. Для нас этот контест был отборочным на полуфинал соревнования ACM-ICPC. Задачи будут сильно различаться по сложности, каждый найдет для себя что-нибудь интересное.
Контест начнется в субботу, 28 января 2012 в 08:00 утра (московское время). Продолжительность - 4 часа. Надеюсь, что вам понравятся задачи!
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