Hello, Codeforces!
I'm glad to invite you to participate in the online mirror of the Baltic Selection Contest for ACM ICPC 2015–2016 that will take place in Gym on the 22nd of October, 13:00 UTC.
This competition determines the best teams throughout the universities of Latvia, Lithuania and Estonia that will participate in ACM ICPC NEERC Western subregional contest in Minsk, Belarus. The onsite contest was held on the 12th of October. The participating universities were University of Latvia, Vilnius University, Kaunas University of Technology, Vilnius Gediminas Technical University, Estonian Information Technology College and others.
As a bonus, I'm posting some photos of the onsite action at University of Latvia. :)
The top 5 teams at the onsite competition were:
- LU: 64428b862de0207ba0385b1ed2df43e1 (Alex_2oo8, zmad)
- VU: 2B||!2B (vstrimaitis, jDomantas, JustasK)
- LU: 0x7DF (Pakalns, Candyman, A_Le_K)
- LU: leet (Instasamka, how_to_become_purple, JustN)
- KTU #1 (wi_lius, lukgar, ASBusinessMagnet)
The detailed onsite standings will be posted after the contest.
The problems were prepared by a group of authors from University of Latvia: gen, KarlisS, andreyv, cfk.
Good luck & have fun!
When I saw pictures I thought this is live LOL competition :D
.
Thanks, wasn't sure about that myself, got lost in translation. :D
Assassin's Creed — Coderhood
Yeah...Hacker+Gamer in a single pic of coder :-)
The cakes look so tasty!
those are called doughnuts, they are really good.
Imagine how would their team's name would be announced at the closing ceremony
They could say md5("zaykarta") :)
How did you figure it out? By the way, 0x7DF also reads easily, as 2015.
I just used one of those online MD5 crackers.. They have precomputed tables up to a certain length.. that's why it's important to salt before hashing! :)
"She's beautiful"
If you look more carefully you should notice that it's a dude.
She also haven't shaved!
Yes she is
Is there a way to do J without treaps ?
Yes. It can be solved online using almost any other self balancing binary tree or offline using Fenwick tree.
Can you elaborate ? My only idea was to use the swap thing from treaps.
We can use that the cyclical order of the people does not change when somebody gets out at the stop. So:
First, pre-process all the queries. Maintain a cyclic linked list that contains all the people, and a pointer to the first person in the bus. When a person enters the bus, add him to the list, change the pointer to him if he used the fron door. When a person x leaves the bus, change the pointer to the person next to him in the linked list, and KEEP x in the linked list. At the end, we have a linked list that contains all the people: the order of the people in the bus at any moment is the order of these people in the linked list.
Since we know the order of the people, make a Fenwick tree where the i-th cell corresponds to the i-th person in the order. When a person enters the bus, +1 that cell, if a person leaves, -1 that cell. Then, when a person leaves, we just sum the number of people between him and the ends of the bus using this Fenwick tree. Note that we can know which person is in the front from pre-processing.
Cannot understand the solution. Can you please show with an example?
sqrt decomposition
Can you please elaborate?
Let's treat the bus as a deque, but instead of one deque, let's break it down to sqrtN deques. And maintain another deque for the indices of these deques in thier current order in the bus. Now we can answer each query online in O(sqrt(N)).
How to Solve B?
So, a single leaked box covers a smaller triangle of boxes. In short, we maintain a set that contains the vertices of such triangles that have not been covered by any other triangle yet. When a box leaks (i.e., a new triangle is added), we find the vertices of the triangles that are inside the new one, and subtract the area that was first covered by this box and is inside the new triangle. Then we can remove them from the set and insert the new triangle vertex in the set. This results in
solution (for each new triangle, there can be also two vertices that are not inside the new triangle, but overlap with it: these vertices remain in the set, but that does not change the complexity).
The solution is clear, and it just needs careful computing.
tfw your nickname is on the front page of Codeforces
How to solve K — Profact ?
There are only about 10k valid numbers from 1 to 10^18, so you just generate all of them.
How to solve H ?
Count number of horizontal lines which is
(row + 1) * col;Then count number of vertical lines which is
row * (col + 1);Desired answer is the minimum of above two numbers,
row * col + min(row, col).Thanks. But could you explain why we should find the minimum of (number of horizontal, number of vertical) ?
Because every connected corner needs to consume one horizontal line and one vertical line, so optimal solution can't be better than
min(No. of horizontal lines, No. of vertical lines).I manually checked several cases, this is a reachable optimal upper bound, though I can't prove it mathematically.
I see, thank a lot
Split the grid in diagonal lanes as shown in the picture:
Notice that each lane can be filled with corners independently, and that at most one border will be left in each lane. Now you can show that either all horizontal or all vertical borders will be used in such layout, thus achieving the optimal value.
How to solve C — Minimax Tree? Please!!!!!!!!
You do a binary search for the answer (one binsearch for min and one binsearch for max) and then after this is fixed you can do a best[node]= minimum number of signs you need to use to get that element (or better) to the node.
How to solve E. Permutation Polygon?
For every edge (x<->y), we need to calculate how many edges (p<->q) intersect it. In order to make sure that we are not overcounting, we'll only consider such edges (p<->q) where x < p < y < q [They surely intersect each other]
We can do that in O(log n). Maintain a segment tree where a node in the segment tree having range [i..j], holds the end points of the such edges (u <-> v) such that i <= min(u,v) <= j, in sorted order.
Now suppose we want to know how many edges (p <-> q) intersects with (x<->y) where x < p < y < q. To get this, we'll query on the range [x+1..y-1]. As we have the end points in sorted order in the segment tree, we'll binary search on y to get the answer.
Thanks! I get it, very clever idea.
It can also be solved using two Persistent segment trees. For each edge a-b, the edges which intersect it are formed between the vertices [a+1, b-1] and one of the two intervals [1, a-1] and [b+1, N]. So we maintain two persistent segment trees inc[i] and dec[i]. Inc[i] stores the other end points of the edges formed by vertices [1, i] and dec[i] stores the other end points of the edges formed by vertices [i, N]. To find out the number of edges which intersect the edge a-b we query inc[a-1] and dec[b+1] for the interval [a+1, b-1]. Note that each edge will be counted twice so we divide the answer by 2 at the end.
Instead of having people asking about every single problem's solution, seeing editorial (even a simple and a short one) would be much better.
I think there is no editorial in Gym's contest.
Is there any way to solve I — Shell's game without binary search? Thanks
Yes
It's rather easy to get formula of this radius. You know that sum of opposite sides should be equal and top side of needed size can be found using Pythagorean theorem. There will be two functions — one that describes sum of right and left sides and other for sum of top and bottom ones. Then you equalize them to get radius.
Answer is
as there could be not enough space for ball that touches both sides.
Thabks for your reply! Just to get this clear, problem asks us for biggest ball size that touches only inner surface and not necessarily bottom of the cup? I may of have rushed into solving it woth wrong assumptions, anyway, thabks for your reply!
It doesn't have to touch neither bottom, nor top of the cup, though the largest radius comes from touching top and all the inside(if possible).
Need some hint for K (Profact).
(Thanks in advance)
There are only a few thousands of such numbers. We can generate them using BFS, and putting the numbers in a set.
gen could u plz tell me what's wrong with my solution?
http://codeforces.net/gym/100796/submission/13962168
In function
gen, you check for overflow byn*fact[i] > 0but I think you still can get an overflow that doesn't violate this condition. The correct way to check would ben<=1e18/fact[i].Thanks, gen. I learnt something new :)
It's AC now.
I've collected the editorials in a single comment here, thanks for writing the solutions. I don't have much free time now, so mine explanations are very short. :|
A: Solve for each digit separately. Don't forget the case when the answer is 0, not to output an empty line.
B: #comment-258052
C: #comment-258117
Another solution: Say we need to compute the maximum. Suppose there is a labelling where a vertex u is a parent of a vertex v, u has at least two children, u is labelled max and v is labelled min. We can prove that swapping the two labels cannot increase f(1). If u had only child, it would be beneficial not to swap the two labels.
We can assume there are no vertices that have only one child, since they don't matter in the end result. Let's just put a max sticker in each such vertex, because the min stickers are more beneficial.
Another observation: if a vertex has two children with min stickers, one of them is redundant and we can change it to the max sticker.
Thus, a linear solution: with a single DFS for each subtree calculate the value that is obtained by placing only stickers max in this subtree. Then, with another DFS examine the paths from the root to each vertex; try to put all the min stickers in that path (except the vertices with only one child), and at the lowest vertex labelled with min pick the minimum value at its children from the first DFS.
D: Note that each move swaps the type of the land we are currently at. Thus it only matters to find the shortest path (in steps), we can do it with BFS. If its length is len, then the answer is
.
E: #comment-258093
F: Observe that
. Thus we can telescope the sum:
G: Hold a pointer to the current cell.
H: #comment-258085 #comment-258096
I: #comment-258126
J: #comment-258060 #comment-258077
K: #comment-258228
L: Just check all substrings of length 2.
Can any one point the problem of my code in problem D
i get WA in test 11