Errichto's blog

TCO16 Round 2C — with Editorial
By Errichto, 9 years ago, In English

Remember to register.

--- EDIT, the contest is over ---

BearBall, 250 points

There is a special case when all points are in one line. Otherwise, for any pair of bears the number of throws is 1 or 2.

So, for each points you should count how many points are directly reachable from this one. You achieve it by sorting other points. The complexity should be .

Proof that 2 throws are enough
code for BearBall

BearGridRect, 600 points

Hint: use flows, maybe mincost.

what graph?
code for BearGridRect

BearCircleGame, 800 points

Dynamic programming. Iterate over the number of remaining players, from n to 1. In each moment, you need an array of size with probabilities — for each number of bears what is the probability that Limak is this far from the starting bear. Then, for each bear we need probability that he loses and thus we will know the next array (for remaining - 1 remaining bears).

a loses with probability .

Try to first write O(n3) approach — find cycle in a sequence of indices a + 1 - k, a + 1 - 2k, a + 1 - 3k... and then over indices in the cycle sum up where c is the size of cycle and d says which place this index has in the cycle.

To make it faster, notice that the answer for a and for a + k will be similar. It's enough to multiply (or divide, whatever) by the sum by two, and then add one value.

code for BearCircleGame

WINNERS

  1. liymsheep, who solved all three problems
  2. ACRush
  3. kriii

And congratulations to Petr for solving all problems and thus winning the parallel round.

  • Vote: I like it
  • +66
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That was a bit of spoiler.

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

Btw, problem 600 can be solved without using mincost-flow, but using an LR-max-flow algorithm (for finding maximum flow when there are lower bounds of flows for each edge).

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

    Problem 600 can be solved with maximum matching (with vertices on each side).

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

      Nice, I didn't expect that. How to do it with matching?

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

        As I see, the first part contains N rows and cnt[i] vertices for each rectangle -- placeholders for columns that are supposed to cover by marked cells in rectangle.
        The same holds for the second part, but for columns and rows' placeholders.

        Btw, thanks for such interesting problems!!!

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

What's wrong with the solution using bfs for the 250 pointer ?

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

    There could be O(N2) edges, so the complexity could be O(N3) right?

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

      This can be overcome by breaking out of the BFS as soon as all vertices are visited.

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

        Did that in last minute but failed systest because of integer overflow -_-

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

        Small clarification, this would only speed up BFS in practice right?

        I mean, consider some graph with N / 2 nodes with all pairs of edges connected. the rest N / 2 nodes connected as a chain with this main component. Here BFS from any of those nodes in main component will be still O(N2) right?

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

          Yeah, it does not help the asymptotic behavior in the general case. But in this problem, BFS becomes O(N) instead of O(N2), for the same reason the more clever solution works.

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

    Lol there's nothing wrong when you do a bit of optimization such as returning when all of the vertices are in the queue = ))

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

Why did you set the time limit for the 800-pointer two times the usual 2s?

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

    I tried to write my Java solution to be as slow as reasonably possible. It requires ~2s for the current constraints so I chose 4s to be TL.

    But you may ask why I chose high constraints. Well, to not be afraid about O(n3) approach. In hard problems it's a disaster when people get worse complexity accepted so it's very convenient for me to set high constraints. I think that everything would be fine today with lower constraint for n but I also don't see important pros.

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

My screencast

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Slightly unrelated, but what tool are you using for opening problem statement in browser and coding in Dev C++ instead of the arena?

    It is really tough to use the arena(UX wise)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Actually, I just started to use Greed and I like it. Previously I used KawigiEdit. There are some nice posts about Greed on Vexorian's blog. For what it's worth, my config is the following:

      greed.codeRoot = "./../.."
greed.language.cpp {
  longIntTypeName = ll
  templateDef {
    source.templateFile = "template3500.cpp"
    source.afterFileGen {
      execute = "C:/Program Files (x86)/Dev-Cpp/devcpp.exe"
      arguments = ["DOLLAR{GeneratedFilePath}"]
    }
    problem-desc.afterFileGen {
      execute = "C:/Program Files (x86)/Mozilla Firefox/firefox.exe"
      arguments = ["DOLLAR{GeneratedFilePath}"]
    }
  }
}

      (replace DOLLAR with dollar signs).

      → Reply
»
9 years ago, # |
  Vote: I like it +38 Vote: I do not like it
  1. qualify to TCO round 3 (from 39th place where top40 advance, so that's neat)
  2. read up that this year, FOUR PEOPLE PER ROUND (3a/3b) advance to onsite
  3. ...profit?
→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In your code for BearCircleGame, I believe that is a geometric series not an arithmetic series. Please correct me if I'm wrong.

→ Reply