### Errichto's blog

By Errichto, 8 years ago,

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.

• +66

 » 8 years ago, # |   0 That was a bit of spoiler.
 » 8 years ago, # |   +19 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).
•  » » 8 years ago, # ^ |   +29 Problem 600 can be solved with maximum matching (with vertices on each side).
•  » » » 8 years ago, # ^ |   0 Nice, I didn't expect that. How to do it with matching?
•  » » » » 8 years ago, # ^ |   +18 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!!!
 » 8 years ago, # |   0 What's wrong with the solution using bfs for the 250 pointer ?
•  » » 8 years ago, # ^ |   +8 There could be O(N2) edges, so the complexity could be O(N3) right?
•  » » » 8 years ago, # ^ |   +51 This can be overcome by breaking out of the BFS as soon as all vertices are visited.
•  » » » » 8 years ago, # ^ |   0 Did that in last minute but failed systest because of integer overflow -_-
•  » » » » 8 years ago, # ^ |   +3 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?
•  » » » » » 8 years ago, # ^ |   +4 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.
•  » » 8 years ago, # ^ |   +24 Lol there's nothing wrong when you do a bit of optimization such as returning when all of the vertices are in the queue = ))
 » 8 years ago, # |   0 Why did you set the time limit for the 800-pointer two times the usual 2s?
•  » » 8 years ago, # ^ |   +31 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.
 » 8 years ago, # |   +7
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 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)
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +5 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).
 » 8 years ago, # |   +38 qualify to TCO round 3 (from 39th place where top40 advance, so that's neat) read up that this year, FOUR PEOPLE PER ROUND (3a/3b) advance to onsite ...profit?
 » 8 years ago, # |   0 In your code for BearCircleGame, I believe that is a geometric series not an arithmetic series. Please correct me if I'm wrong.
•  » » 8 years ago, # ^ |   0 Thanks, corrected now.