paladin8's blog

2011-2012 Stanford Local Contest
By paladin8, 12 years ago, In English

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.
  • Vote: I like it
  • +92
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
12 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Online registration for the 2011 Stanford Local Programming Contest is now closed!


→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it
    Sorry, the actual contest was held months ago. This is a training in the CodeForces gym :)
    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I would preffer 8PM :-D
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Unfortunately, that means 8am for me...
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it
      Oh..
      It is 6am in Ukraine.
      Not good..

      I prefer to sleep till 7am at least =)
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it
        You can still register and come late. Still good practice and no need to worry about rating and such things :)
        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      yeah, but 8am in Moscow is 5am in Prague, but never say never :-D On the other hand I was 65 minutes late in last contest and it was at 7am here...

      I know, there is always someone around the world who wants to sleep no matter what the time is, but when I'm getting up at 3am for TopCoder maybe I'll wake up at 5am too, thanks for the contest ;-)
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Yes, it's too bad I'm on the other side of the world from most CF contestants, so scheduling is quite difficult.
        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    virtual contest....
    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are first testcases the same with those in problem statements?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    No, there is only 1 test for each problem (all cases at once).

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can anybody explain me solution for B?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    find a regular pattern

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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 :)

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C,is the shortest path on the MST of the graph? And, how can I get the solutions?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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)).

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the idea behind G?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody provide a general editorial for this contest? if it's too much trouble a general summary would do fine as well

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    -_- why necro bump this when you can make your own blog post

    → Reply