gen's blog

ACM ICPC 2015-2016, Baltic Selection Contest (Online Mirror)
By gen, 9 years ago, In English

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:

  1. LU: 64428b862de0207ba0385b1ed2df43e1 (Alex_2oo8, zmad)
  2. VU: 2B||!2B (vstrimaitis, jDomantas, JustasK)
  3. LU: 0x7DF (Pakalns, Candyman, A_Le_K)
  4. LU: leet (Instasamka, how_to_become_purple, JustN)
  5. 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!

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

Comments Comments (54)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

When I saw pictures I thought this is live LOL competition :D

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

.

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

    Thanks, wasn't sure about that myself, got lost in translation. :D

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

Assassin's Creed — Coderhood

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

The cakes look so tasty!

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

    those are called doughnuts, they are really good.

    → Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it
What a name... "64428b862de0207ba0385b1ed2df43e1". As if "2B||!2B" or "0x7DF" weren't good enough

Imagine how would their team's name would be announced at the closing ceremony

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

    They could say md5("zaykarta") :)

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

      How did you figure it out? By the way, 0x7DF also reads easily, as 2015.

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

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

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

"She's beautiful"

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

Is there a way to do J without treaps ?

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

    Yes. It can be solved online using almost any other self balancing binary tree or offline using Fenwick tree.

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

      Can you elaborate ? My only idea was to use the swap thing from treaps.

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

        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.

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

          Cannot understand the solution. Can you please show with an example?

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

    sqrt decomposition

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

      Can you please elaborate?

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

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

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

How to Solve B?

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

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

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

      The solution is clear, and it just needs careful computing.

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

tfw your nickname is on the front page of Codeforces

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

How to solve K — Profact ?

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

    There are only about 10k valid numbers from 1 to 10^18, so you just generate all of them.

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

How to solve H ?

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

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

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

      Thanks. But could you explain why we should find the minimum of (number of horizontal, number of vertical) ?

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

        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.

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

          I see, thank a lot

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

          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.

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

How to solve C — Minimax Tree? Please!!!!!!!!

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

    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.

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

How to solve E. Permutation Polygon?

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

    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.

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

    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.

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

Instead of having people asking about every single problem's solution, seeing editorial (even a simple and a short one) would be much better.

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

Is there any way to solve I — Shell's game without binary search? Thanks

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

    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.

    — side of trapeze

    Answer is as there could be not enough space for ball that touches both sides.

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

      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!

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

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

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

Need some hint for K (Profact).
(Thanks in advance)

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

    There are only a few thousands of such numbers. We can generate them using BFS, and putting the numbers in a set.

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +44 Vote: I do not like it

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.

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

Can any one point the problem of my code in problem D

i get WA in test 11

→ Reply