snarknews's blog

Three Regionals Cup-2021
By snarknews, history, 3 years ago, translation, In English

Three Regionals Cup — 2021 on the tasks of Moscow Regionals 2021, Belarus and Baltic Regionals 2021, and Northwestern Russia Regionals 2021 is traditionally running at the Yandex.Contest platform in the format of three virtual contests. On the cup page, you may register for those contests.

You may use the plain Yandex logins or OpenCup or other pre-generated logins (choose the appropriate link at the top of the page).

The regionals results will be included in the cup standings. The result of the Cup is the sum of the Grand Prix 100 (similar to Opencup) scores for all three regionals at 0:00 Jan 15 2021.

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

Comments Comments (25)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you have any plans to use the problem set in opencup or other places?

If not, I'd like to participate in the contest. (I'm worried because there is a button that says "opencup login”.)

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

    "Opencup login" link is the way to login using the pre-generated logins (for example, for Opencup, MW camp etc), so if you (or your team) prefer to use this type of login instead of personal credentials of Yandex, the "opencup login" link shall be used.

    The contests are already in use on Three Regionals Cup, so they will not be used at Opencup etc.

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

Can somebody share a link to the task analysis of the Belarus and Baltics Regional Contest?

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

will there some tutorial for moscow contest?

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

Thank you for these three wonderful contests!

By the way I want to ask whether we can still virtually participate these contests after Jan 15th or not? I am not sure if they are only available by Jan 15th or only the scores are only counted by Jan 15th.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

Thanks for the beautiful contests. We really had fun solving them. Are there any editorials?

Since Jan 15, 2021, 0:00 (Moscow time) is over. I hope it's fine to discuss the problems now.

Anyways, how to solve -

Regional 3. Moscow 2021 — I. 1%-Euclidean, K. Efficient Interception, O. Treeshop
Regional 2. Northwestern Russia 2021 — E. Extreme Problem and J. Journey in Fog
Regional 1. Belarus and Baltics 2021 — M. There could be your problem name and K. Split Circles

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

    I'm not sure if the "0:00 Jan 15 2021" cutoff is accurate, as the virtual contests are running until Jan 17.

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

    My py solution for M

    For Belarus and Baltics 2021 — M. There could be your problem name you can refer to this similar problem. My comment explains a solution with $$$O(|n|^3)$$$ complexity.

    Also, ftiasch reduces the complexity to $$$O(|n|^2)$$$ by amortizing the big integer calculation. She used this problem with $$$|n|=5000$$$ in CCPC Final 2020.

    At last, if you have gotten official editorials, could you share them with me? Or we can share solutions with each other.

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

    I'm still interested in seeing a solution to 1% Euclidean, if anyone knows how to solve it.

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

      Pick $$$5\cdot 10^7$$$ random pairs of points, find average distance. I don't know why but it gets OK.

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

      In fact, this task was discussed in an olympiad training camp in Shandong, China last year, but I didn't know how it was done until recently.

      First, this problem can be easily solved in $$$O(n \log n)$$$ if all points satisfy $$$y_i = 0$$$. The answer will be $$$\sum_{1 \leq i < j \leq n} |x_i - x_j|$$$.

      Note that for any two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$, the distance of these two points $$$\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2} = |x_1 - x_2| \cdot |\cos(\theta)|$$$, then we have:

      $$$\int_{0}^{2\pi}\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2} \mathrm d \theta = \int_0^{2\pi} |x_1 - x_2| \cdot |\cos(\theta)| \mathrm d\theta = 4 \cdot |x_1-x_2|$$$

      Let $$$f(\theta)$$$ denote the value of $$$\sum_{1 \leq i < j \leq n} |x_i-x_j|$$$ after rotating all points counterclockwise by $$$\theta$$$. Then the answer is just $$$4 \cdot \int_0^{2\pi} f(\theta) \mathrm d\theta$$$. If we take $$$T$$$ values $$$\xi_i = \frac{i}{T} \cdot 2\pi$$$ and use $$$\frac{1}{2\pi T} \sum_{i=0}^{T-1} f(\xi_i)$$$ to estimate the value of the integral above, then the error is $$$O(T^{-2})$$$ which is acceptable for $$$T =\frac{1}{\sqrt \varepsilon}$$$. The time complexity is $$$O\left(\frac{n \log n}{\sqrt{\varepsilon}}\right)$$$.

      Code

      By the way, it seems the test cases are really weak. It can be passed by taking about $$$10^7$$$ random pairs of points and using the average distance to estimate the answer...

      Take 1.4*10^7 random pairs of points
      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Several teams asked to allow to run the contests at the current weekend, so the deadline is moved forward to Jan 17 10:00 Moscow Time.

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

    Bump. Since Jan 17 10:00 Moscow Time is over. I hope it's fine to discuss problems now. Also are there any editorials?

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

      You just cannot wait eh :P

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

        Sorry. Idk why I wrongly remembered that vc time on Yandex ended ~12 hrs ago. So I assumed thats Moscow time 10:00 .

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

Will there be any editorials?

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

Hello! How to solve Baltic Stage F, H, M, N; Northwestern Russia Stage F, G, I, J; Baltic Stage B, C, K, L, O?

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

    I only happened to solve Moscow L (which I assume you're asking about since you said "Baltic" twice?), and the answer for that might be frustrating... Maximum Flow :)

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it
    Baltic H
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you y'all solve Northwest Russia problem D (Day Streak)? Are you using Implicit Segment Tree (that I just happened to read about in https://mirror.codeforces.com/blog/entry/99074), or some other data structure?

During the contest, I tried implementing something that would track the set of non-overlapping intervals, and recalculate them in logarithmic time when a problem moves across timezones, but I quickly got bogged down in details (e.g., did an interval break up? did two intervals merge? etc.). Is there a known data structure that maintains the data in this fashion?

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

    If Data Structure had only insert queries then finding maximum length segment is a known problem. here

    My soln was along the lines of Implicit Segment Tree (or similar things only) but it just uses std::set and std::map.

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

      I see, always removing an interval before adding it seems to eliminate a lot of complexity. Neat trick!

      (That said, C++ has more palatable map interface for this than Java's TreeSet provides, so I think overall I'll stick with implicit segment trees over TreeSet implementation :|)

      → Reply