antontrygubO_o's blog

By antontrygubO_o, 7 months ago, In English

ICPC Logo

Hi everyone,

I am happy to announce that the 2020 Southeastern Europe Regional Contest will take place on May 23 at 10 am UTC+3. The link to the live results will be published here after the start of the competition.

Moreover, later this day, at 4 pm UTC+3, there will be the Grand Prix of Southeastern Europe based on these problems. Because of the Grand Prix, we are asking the official contestants not to discuss the problems in public.

After it, we will upload the contest to the gym and publish the editorial. We hope that you will enjoy the contest.

Good luck to all participants!

UPD. SEERC standings

UPD2. Congratulations to the winners!

Place Team Name Contestant 1 Contestant 2 Contestant 3 Problems Penalty
1 KhNU_OtVinta kilt_01 Stroustrup 13022001 8 1043
2 RAF Penguins Pajaraja milisav allllekssssa 8 1128
3 Echipa Dulce alexandra_udristoiu Stelutzu Usu 7 736
4 UAIC Endgame lungualex00 cristian1997 denis2111 7 837
5 KNU_stascool5 danya.smelskiy Sonechko stanislav.bezkorovainyi 7 1029
6 KhNU_GangBand dendi239 viskonsin Eikgrim 7 1230
7 cpu_goes_brrr muratt ykaya ekrem 7 1239
8 KhNURE_Energy is not over BigBag Barichek Mustang98 6 426
9 CodeBusters LucaSeri Hikori robxln 6 647
10 LNU Jackals BohdanPastuschak PetroTarnavskyi mshcherba 6 655

UPD3. Editorial

Thanks for your participation!

UPD4. The contest is available in gym:

2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020).

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

»
7 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Shouldn't it be 2021?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    No, SEERC 2020 was expected to be in Fall 2020. However, it was moved to Spring 2021.

    It is similar to the World Finals. World Finals 2020 will not be in 2020.

»
6 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve A, C, G?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    My solution to C:

    Make a triangle ABC, and a path of nodes 0..n with 0=A. Now connect each one of 1..n with one of A, B or C. The number of ways to color a prefix with color equal to A,B,C is in the form (x,y,0), and it transitions to (0,x,x+y) or (y,0,x+y), and 14 steps is enough to reach some (x,y,0) with x+y=k for all k <= 500.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    A can be solved by analyzing the DP as a convex hull: for each prefix, what's the maximum value such that the last stack has depth $$$d$$$? We need to support the following 2 operations: take $$$f(x) \to f'(x) = max(f(x-1), f(x), f(x+1))$$$ (with the special case that $$$f'(-1) = -\infty$$$) and $$$f(x) \to f'(x) = f(x) + a_i x$$$. Both of these preserve the fact that the function is concave.

    We can maintain the function as a set of segments with $$$\Delta x = 1$$$, sorted in decreasing order by $$$\Delta y$$$; the first operation is inserting 2 segments of slope 0, and then deleting the steepest segment for $$$f'(-1)$$$, and the second operation can be handled with a lazy increment to the slope. If we use a priority queue, this code is extremely short:

    Code

    Funnily enough, I wrote essentially the exact same code in 2015 for a USACO Camp problem (haybales, Day 3). The problem was as follows:

    Given an array of integers, find the minimum number of operations to make it non-increasing, where each operation can increment or decrement one value.

    Code

    In fact, the answer to SEERC A is exactly the answer to haybales on the $$$N+1$$$ prefix sums of the costs. Does anyone have an intuitive/combinatorial explanation? Is it LP duality or something?

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +20 Vote: I do not like it

      It's LP duality, indeed. We have mentioned that in the editorial, as well (although without much proof). The problem that you are mentioning is the classical problem for the "slope trick" technique (link). Also, this is a relevant problem (the same as you mentioned, maybe?).

      The two problems are actually equivalent. I think it's really interesting how different solutions to this problem leverage different ways to analyze and solve "slope trick", especially the reduction to minimum cost flow.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    G: Just walk along the outside of the region following right-hand-rule. You just need to be able to efficiently jump to the next left-turn along your current segment (if it exists), which you can get by preprocessing the perpendicular segments in a persistent data structure. This is efficient because the size of the boundary of the region is linear. The editorial mentions an upper bound of $$$O(n \alpha(n))$$$ segments on the outside, but I believe I have a tighter bound: each right-turn (convex vertex) must correspond to the end of the segment so there are at most $$$O(n)$$$ right-turns. Furthermore, we make exactly 4 more right turns than left turns, so the total number of turns/segments we use must be $$$O(n)$$$ as well.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've seen some solutions in K that have just one SOS pre-computation. Does anyone want to explain them?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm not sure about other solutions, but one observation we made (and didn't use) is that the problem guarantees the number of 0's is at most 9, so that directly gives you an upper bound of approximately $$$d/3$$$ without having to consider the other cases.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      That’s true, but doesn’t that change once you start replacing question marks with 0/1?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        You can avoid it, either replace the ? with 1 or keep it as ?, but knowing that any solution should have a 0 there.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        (Assuming the number of 0's is at most 9)

        Try to replace each question mark with 1 if possible, but otherwise just keep it a question mark. After that, just replace all the remaining question marks with 0, because if we can't replace any question mark with 1, they must all be 0.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        We can prefer replacing ?s with 1s. If it's not possible, we can leave it as ? instead of changing it to 0, because those will be equivalent. That way, the number of 0s you have to casework over doesn't increase.

»
6 months ago, # |
  Vote: I like it +27 Vote: I do not like it

There's also a sweet interactive table provided by BigBag

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Why is aleksa purple in the table

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone help me on Problem F? I cannot understand why dp transition on editorial makes sense.

let dp[i][j] = (the number of output sequences b such that bi = hj)

why dp[i][j] = sum(dp[i-1][0], ... , dp[i-1][j]) ?

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

The editorial says that the problem H can be solved by "divide & conquer" in $$$O(n\log n + (q + n)\cdot b)$$$.

Could anyone give me some details of the solution?

(Sorry for my poor English.)

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    Probably I have the idea.

    Based on the conclusion we got before, to get the answer we can just divide the numbers in two part by the number of '1' bits.

    Consider how we answer all the queries completely included in the range $$$[l,r]$$$. Let $$$\textit{mid}=\lfloor(l+r)/2\rfloor$$$ and recursively solve the queries that completely included in $$$[l, mid]$$$ or $$$[mid+1,r]$$$, then the remaining queries we divide them into two parts. For the left part we record $$$b$$$ information at each position, and for the right part we process left to right by the right point of queries and keep the $$$b$$$ information during scanning. Because we record each position $$$O(\log n)$$$ times and each time we cost $$$O(b)$$$ time, so total complexity is $$$O(nb\log n)$$$.

    Actually if we want to reach the better time complexity, all we need is just one more thing. Notice that "record $$$b$$$ information at each position" is no need, because we just wonder the left points of the queries. So record the position we need instead of all of them. Now we get the $$$O(n\log n+(q+n)\cdot b)$$$ solution.

    My Code Here