Aldas25's blog

By Aldas25, 4 weeks ago, In English

Hello Codeforces!

The Baltic Olympiad in Informatics 2024 is coming soon!

We are inviting everyone to take part in the Mirror Contest. It will consist of two competitions, each lasting five hours:

These times are given in the current Vilnius time zone. It is UTC+3!

The winners are announced here: https://boi2024.lmio.lt/news/mirror-contest/

Online (anonymous) ranking: https://mirror.cms.lmio.lt/ranking/ (will be open for a few days).

Onsite results: https://boi2024.lmio.lt/results/

Tasks: https://boi2024.lmio.lt/tasks/

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

»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

I wish you all the best of luck.

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

will there be live standings?

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

    There won't be any public live standings. However, we will try to put some scoreboard after the contests.

»
3 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Collides with Orthodox Easter.

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Excited!

»
3 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

Is there any information about the registration published?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    There are less than 30 minutes left until the start of the contest, but I can't find any link yet :"

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

      They could have problems with the actual competition, as currently the second contest day is running.

»
3 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

Mirror link?

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

    Will be posted in a few minutes. (EDIT: now live at the website)

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Mirror registration and contest link updated at: https://boi2024.lmio.lt/news/mirror-contest/

»
3 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

How to solve Jobs for subtasks?

Btw, Trains and Jobs were interesting tasks!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For S = 10^18, you can just do simple DP, because you just need to choose maximal sum of elements in tree, and some DP[node] = maximal profit if I choose that node, would pass.

    When tree is chain, then greedy like take node which you can take that would increase profit. You can simulate this easily.

    Full solution is to consider DP[node][minimal starting sum] = max profit. You can look how function f(minimal starting sum) = max profit changes. Main idea is to use slope trick. All you have to do now is some casework when you add positive/negative element. You should also use small to large to maintain slope points.

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

      Nice solution and the explanation! Aprreciate it.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 6   Vote: I like it +11 Vote: I do not like it

      My solution was simulating this greedy strategy:

      For each node store (min starting sum, profit) = $$$(v_i, d_i)$$$.

      Start with $$$d_i = x_i$$$, $$$d_0 = s$$$, $$$v_i = max(0,-x_i)$$$

      If for some node $$$i$$$ condition $$$d_i \geq 0 \land v_{p_i} + d_{p_i} \geq v_i$$$ holds, merge with parent to form $$$(v_{p_i}, d_{p_i} + d_i)$$$.

      Otherwise, find the node $$$i$$$ with min $$$v_i$$$ and $$$d_i\geq 0$$$ and $$$p_i\neq 0$$$ and merge with parent to form $$$(v_i - d_{p_i}, d_{p_i} + d_i)$$$.

      Answer will be $$$d_0$$$.

      Used small to large/dsu and priority queues for implementation.

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

        The intended solution was also a greedy strategy. But the slope trick solution also sounds very nice!

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

when will it be ok to discuss day1 problems?

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Where can we find results of mirror contest?

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Portal?

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

    My solution was to calculate the density of the n-1 vectors (in 2d) in Z^2, where the n-1 vectors are (a[i+1].x-a[i].x,a[i+1].y-a[i].y)

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

      Could you explain how did you calculate that?

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

        If you have 3 vectors, you can reduce it to 2.

        Notice, that you can change vector $$$v$$$ to $$$-v$$$ and vector pair $$$(a, b)$$$ to $$$(a, a+b)$$$ without changing the answer.

        Using this, reduce $$$2$$$ of the $$$3$$$ vectors to have $$$x = 0$$$ (euclidean algorithm), then you can change those 2 to $$$(0, gcd(a_y, b_y))$$$

        Somehow this needs __int128 precision

        EDIT: Doesn't need __int128, forgot some %= to keep the vectors small.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          That's what I thought about, but didn't manage to find the value of the second vector when I reduce the first one to x=0. I forgot about the Euclidian algorithm. Thanks! .

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Where is the scoreboard ?

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

    Hopefully, we will upload soon :D

    EDIT: now it's published.

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

      Thanks, and when will results from official contest be uploaded?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        High probability that after the closing ceremony.

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Aldas25 When will the analysis open?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It's open

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

      Yes, we opened it quite recently. It should be open until tomorrow.

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Surprising fact about B:

The answer is 2 * gcd of areas of all NC3 triangles. I have no proof (good luck if you want to try). Unfortunately, I wasn't able to solve beyond N <= 2000 using this.

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If your claim is true, than this can easily be done in O(n): fix a point in the set P_0, and return twice the gcd of all areas of triangels of the form P_0 P_i P_i+1. any area of triangle p_i p_j p_k can represented as a linear combination of such areas, and therefore if a number g divides all areas P_0 P_i P_i+1, it will divide all areas P_i P_j P_k.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i dont think this is correct (from experience since i submitted this too i think along with other heurestics). But, it is true that you only need to consider triangles passing through P_0

»
3 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Is there any official solutions of problems?

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

    We will probably upload the solutions (and the task themselves) to the website after the olympiad.

    However, you are also free to share and discuss the solutions here. (note: after the mirror contest ends, of course)

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

How to solve wall?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Count the amount of water as $$$n$$$ — (open space) — (buildings) instead. Buildings are very easy to count (linearity of expectation, so to say). To count the open spaces (to the left), you use the formula $$$\sum_{i=1}^n (\prod_{j=1}^{i} a_j) 2^{n-i}$$$ or likewise, this can be counted with segment trees.

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

      Hmm, thinking about empty spaces is a lot easier lol. I was maintaining $$$dp_i[h] = \text{# ways of prefix 0...i max} = h$$$ in a segment tree for prefix/suffix. Then I updated the answer with $$$\sum_{i=1}^{n} i \times \sum_{h=0}^H min({a \lor b}_i, h) \times dp_{i-1}[h] \times 2^{n-i} $$$ and similarly with a negative sign from the other side.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the answer.

        I see you are from Lithuania, did you participate onsite?

        If you did, can you tell what were the medal cutoffs.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I participated online.

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Are there any simple implementation approaches to problem "tiles"?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Change polygon to $$$x$$$ coordinate events $$$[y1, y2, open]$$$, then do sweepline.

    Start tiling the polygon from the left, then you will have some tiles with $$$x_2=x$$$ and some tiles with $$$x_2=x+1$$$. Store the y coordinate ranges for those. Treat the outside of the polygon as a tile.

    If the set $$$x_2 = x+1$$$ is empty, set the answer to $$$x$$$.

    To process an opening event insert it to the $$$x_2=x$$$ set.

    To process a closing event, the range must be contained within the $$$x_2=x$$$ set. Cut out the closing event range.

    After events, the $$$x_2=x$$$ ranges must have $$$y_1 = y_2 \mod 2$$$.

    After processing events increment $$$x$$$ and swap sets $$$x_2=x$$$ and $$$x_2=x+1$$$.

    My terrible code:

    Spoiler
  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    I implemented the algorithm from this paper and it was reasonably simple.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Day 1 rankings now show rankings for day 2, please update the post

»
2 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

Why does the ranklist not contain usernames?

It is more fun to look at a non-anonymous leaderboard :D

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We did not collect the consent for showing names. We didn't want to deal with that legally, and also there could have been inappropriate names filled.

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Official mirror results with names, when?

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve problem B in both days. I managed to solve every thing else except these two (I really hate geometry lol)

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

is there any scoreboard with names?

»
2 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve day2 p3 ?

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve full fires? I managed to solve the first 4 subtasks subtask using O(n^2) solution and add some randomization to pass the fifth one.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Is there is interval i where Si > Ei, you change Ei to M + Ei.

    Observation 1: If there are more than 1 intervals equal Si, we will always choose the one with greatest Ei.

    Observation 2: If we are currently at interval i, we will jump to interval j, such that Si <= Sj <= Ei and Ei < Ej and Ej is maximal. If there are more best j, we take the one with smallest S.

    Now, we can build directed graph using the observations above.

    For each interval i, we will use binary search and binary lifting to find the first interval j, such that Ej >= Si + M.

    Note that we should build the graph in NlogN which can be achieved using segment tree.

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

    Choosing around 100 random starting points and checking each in O(n) also works.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      why is it true?

      imagine 2 segments that cover the whole space and the rest are small not optimal segments. what is the probability that you choose exactly one of those 2 segments out of 1e5 segments

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

        I forgot to say that you choose that random starting segments from the first 1000 longest segments.

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

          I think the test cases were very weak, such a solution have passed during contest only fixing the largest segment, it obviously should not pass.

          how have you figured out that your solution is right. it is not clear to me, assume we have one large segment with length 10000 and inside that large segment we have 1000 segments with length 2. assume the optimal answer contains the largest segment, but we are picking 100 elements out of 1000 there is very low probability that we select exactly that largest one:

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there something wrong with the following algorithm for d2p2? Or am I just too incompetent to implement it?

Spoiler
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Didn't read the whole thing but your second sentence is already suspicious to me, consider a polygon like

    .xx
    .xx
    xx.
    xx.
    
»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anybody know the official medal cutoffs?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will tasks be published?

»
12 days ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

ojuz

Will you add these problems on oj.uz?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I submit code somewhere? Also the tasks zip file in the website doesn't work

»
10 days ago, # |
  Vote: I like it -11 Vote: I do not like it

good luck for all participants

»
10 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

The problems can be solved on Eolymp.

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems the test data link is broken. Could you take a look? Aldas25

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

    Hi! The website will be moved to a permanent place, and then the link will be fixed. Hopefully, we will do this soon :)