Hello, Codeforces!
The 25th Balkan Olympiad in Informatics takes place in Chișinău, Republic of Moldova, from July 02 (arrival day) to July 08 (departure day) 2017. The most gifted students from the Balkan region of Europe will have the opportunity to prove their knowledge and skills in informatics.
CS Academy will host the online mirrors of both competition days. The second contest starts on Thursday, July 06, 11:00:00 UTC, right after the onsite competition ends. The round will be rated on CS Academy. The problem statement will be available in English.
Contest format
- You will have to solve 3 tasks in 5 hours.
- There will be full feedback throughout the entire contest.
- The tasks will have partial scoring. The maximum score for each problem will be 100 points.
- There will be no tie breaker, so two users having the same total score at the end of the contest will share the same place in the standings.
If you find any bugs please email us at contact@csacademy.com
Don't forget to like us on Facebook, VK and follow us on Twitter.
Is there any solution to Q1 and Q3?
Q1: We can delete cats/dogs instead of moving them: just move them next to one of the remaining cats/dogs. The only tricky case is when we delete all cats or dogs, we will process it separately. Let's calculate dp[processed prefix][cat or dog][balance] = number of moves. Balance is the difference between number of "free" lions and number of cat-dog borders. Lion is free if it doesn't stay between a cat and a dog. All transitions are straightforward, answer is minimal value of dp for nonnegative balance. But i don't know any easy way to work with cases when we delete all cats or dogs, my implementation is really ugly.
Q3: subtree dp. For any vertex v we can find vertex x in the subtree of v with maximal ax - d(x, v). Now let's run dfs from the root and find the vertex with maximal ax - d(x, v) among all vertices. If it's in subtree, we know it. Otherwise we can use answer for the parent. For any vertex we know next vertex on our path. If k is small. we can just simulate it. But the path will quickly become a periodic! So let's find a cycle and get the answer.
Deleting all cats: we can move them all between 2 lions or to the beginning/end if there's are 2 adjacent lions or a lion at the beginning/end, with cost ncats; otherwise, we can move all cats and one lion to the beginning with cost ncats + 1. This can be checked separately.
My DP had states [prefix][last animal we kept][did we keep some cat?][did we keep some dog?][balance], the only relevant states are the ones where we kept at least one cat and dog.
I'm the author of this task. This was my exact solution, the only exception being that I grouped "did we keep some cat?" and "did we keep some dog?" in a single bit mask.
I think this is a good problem, I very like it. Thank you^^
"Otherwise we can use answer for the parent." how could u guarante that the answer is in his direct parent's subtree?
No, it's not in his parent's subtree. If optimal vertex for v is not in subtree of v, it's also optimal for parent cause path from v to this vertex goes through it's parent. But we need to find not the best city but best city different from the current, yeah? For example, we can find two best cities.
There is another O(NlogN) solution for Q3: Write all the vertices in dfs order, so that every subtree is a subarray in that array of vertices. Now, make a RMQ(with segment tree) over that array(with value being cost[i] — dist(root, i), and for each node, we get the maximum of all the vertices. We do a simple dfs from root(1), and when we enter a node we update all the values in subtree with 1, and all the vertices that don't belong to the subtree with -1. Queries of this type could easily be done with segment tree + lazy propagation.
How to solve B problem? I'm not sure how to modify number of empty submatrices algorithm to solve it.
There is a relatively simple O(N^3) algorithm that I'm not sure if it's supposed to get 100 points on the competition, but it did. Our goal is to calculate number of rectangles of 1s containing that field for every field. If we fix lower-right corner of the rectangle, and its width, we can get height of that rectangle in O(1). When we have some rectangle of that type, we will have to update first row of that rectangle with +1, second row with +2, and etc..(Can be shown using some easy maths) Updates of this type can be handled with several cumulative sums over rows/columns, we have O(N^3) such updates, and O(N^2) for calculating sums and calculating the matrix, so the algorithm has O(N^3) complexity. Finally, our solution is number of rectangles before deletion — maximum value of the calculated matrix.