lumibons's blog

By lumibons, 2 weeks ago, In English

This weekend, the Baltic Olympiad in Informatics 2022 (BOI 2022) is going to take place! BOI is a programming contest for secondary school students from countries around or close to the Baltic sea. This year, around 70 contestants from Denmark, Estonia, Finland, Germany, Iceland, Latvia, Lithuania, Norway, Poland, Sweden and our guest countries Israel and Ukraine will compete against each other, solving difficult problems of algorithmic nature. Each participating country sends 6 contestants from their national olympiads which take place in the months beforehand.

The contest consists of two days, Saturday and Sunday, on each of which the contestants have 5 hours to solve 3 problems of varying difficulty. Each problem is worth 100 points that are distributed into multiple subtasks with different constraints that allow the participants to earn partial scores. During the contest, each participant receives the verdict of the execution of their solutions on all tests.

While BOI 2020 and BOI 2021 were virtual only, we are excited to meet most BOI contestants this year in-person! BOI 2022 is hosted onsite in the beautiful city of Lübeck, a historical German town on the Baltic Sea, member of the „Hanse“ trade union of cities. Only the contestants from Israel participate from their own country in a proctored online setting. For more information about the contest, visit the official website at boi2022.de.

Furthermore, we hope to be able to host an online mirror of BOI 2022 for all those who are waiting for a sequel to the story of the BOI contestant turned art thief. However, the online mirror will be held at least one week later than the actual contest. We will publish more details about the mirror in the coming week.

We wish all BOI contestants an enjoyable onsite contest and hope that the coming olympiads can be hosted in-person, too!

-- BOI 2022 committee

Update: The official contests are now over. Congratulations again to all the medalists and in particular to the overall winner of BOI 2022, antekb! In the end, 36 medals were awarded to official contestants, with the guest delegation of Ukraine winning 4 out of 7 gold medals. We will publish the official results of this year's BOI after the online mirror.

Speaking of the online mirror, we are happy to invite you to participate in the online mirror of BOI 2022 on Saturday, May 7, 2022 at 8:00 UTC and Sunday, May 8, 2022 at 8:00 UTC! The mirror will be held on CMS which was also used for the official contest. To register for the online mirror, visit contest.boi2022.uni-luebeck.de. You need to register there, before participating.

Update: The official results are now published here, but without the task-wise scores for now. They will be added after the online mirror is over. We hope you enjoy the problems in the mirror tomorrow!

Update: The online mirror of the first day is over! We hope you liked the problems. You can see the scoreboard of the online mirror here, and you can compare your results with the results of the official contestants on this scoreboard.

Note: If you want to know how the story of the hypothetical art heist continues, we highly recommend that you also participate in the online mirror of day 2. However, note that if you have already created an account for day 1, you still have to join the mirror of day 2. This works by going to the registration page and using the option "Join contest" there.

Update: The mirror of day 2 is now over, too. We hope that the tasks, especially communication, were a challenge for you ;-) You can see the combined results of day 1 and day 2 on the same scoreboards as before, the ranking of the online mirror here and the official results here. We will publish all tasks together with their spoilers and the test data in coming days on the official website.

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

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

Each participating country sends 6 contestants from their national olympiads which take place in the months beforehand.

I wouldn't be so sure about that

»
13 days ago, # |
  Vote: I like it +109 Vote: I do not like it

We will publish the official results of this year's BOI after the online mirror.

As someone who follows the competition outside of delegation, I want to know how my country did. I want to know who is going to IOI from my country. I don't think withholding this information because someone might estimate task difficulty in an unofficial mirror is acceptable to be honest, especially when that mirror is almost a week later. If someone really wants to cheat in an unofficial mirror they can always get the tasks from an actual competitor. Or are you going to ban people from the actual competition if they do that?

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

    +1 to that. I find this situation pretty ridiculous. An obvious solution would be just not to wait a whole week to host the mirror.

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

    Due to the popular demand we have now published the official results here, but without the task-wise scores for now. Unfortunately, this took longer than expected due to organizatorial issues.

    However, we also feel that the wording of your message was somewhat disrespectful and that your request could have been phrased more politely.

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

      Thank you.

      I apologize if you felt that the message was disrespectful and appreciate the feedback. It was however strongly worded because I strongly disagreed with the original decision.

      To me your announcement basically stated that you believe that not letting unproctored online mirror participants figure out the difficulty of tasks if they really wanted to is more important than celebrating the achievements of BOI 2022 participants which I took offence at.

      Organizational issues happen. I have absolutely no problems if the publishing of results is delayed due to that. But that was not what was communicated I believe.

      Given that the results still aren't published in full (although I do not have any issues with that at this point), it seems to me that maybe I'm completely missing some other benefits of intentionally delaying results. Please let me know if that's the case.

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

        Most of the scientific committee, including me, agree that publishing the official results of BOI is more important than keeping the task difficulties secret for the online mirror. In fact, this is what we did last year as well.

        However, this year there were a number of issues which lead to the original decision. For example, many BOI countries use BOI as a selection contest for IOI. This can also include students which are not part of the official BOI team and who might not be able to participate unofficially online during the actual competition. Indeed, two such students were writing a mirror of day 1 on Monday, which is why no results were published immediately after each respective contest day. Originally, there were also plans for a few such students to only participate in the online mirror, which was the reason for the original decision to only publish the results later.

        While these plans were not realized, we didn't bring the publication of the results forward because the organizatorial difficulties that we ran into were forseeable and because we also thought that most BOI countries communicate the results of their own contestants clearly via their own channels so that we didn't expect the official results to be as eagerly awaited as they apparently were. Also, we know of at least one country which actually uses the online mirror as a selection contest for IOI, which is why the results are still not published in full.

        You are right, of course, that the announcement didn't state these reasons for the delayed publication of the results which probably created a false impression :-)

»
12 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Registered :D cant wait

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

Mirror of first day seems to intersect with AGC by one hour :(

»
9 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Seems the day1 mirror has been finished.

How to solve task VAULT?

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

    I tried some greedy + dp, but had only one hour for that problem... Tried to first take all elements, and then remove largest elements until sum <= L, and then try to add one element and do dp[S] -> max number of elements resulting with sum S. Probably not correct : )

»
9 days ago, # |
  Vote: I like it +19 Vote: I do not like it

When will you publish results of mirror day 1?

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

How to solve "Events"?

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

    Sort all events by their end time and then for every event $$$i$$$ find range $$$[L_i, R_i]$$$ such that for every event $$$j, L_i \le j \le R_i$$$ you can jump from $$$j$$$ to $$$i$$$, and with that you can use binary lifting to find number of jumps to reach other event.

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

      How to use binary lifting here?

      1. we can have n^2 edges
      2. graph isn't functional
      • »
        »
        »
        »
        9 days ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        The key is to iterate from the $$$e$$$ to $$$s$$$.

        Let's say you are on the event $$$i$$$, you could have joined the event $$$i$$$ from any event $$$j'$$$ such that $$$L_i <= R_{j'} <= R_i$$$. Let's say among all such $$$j'$$$, $$$j$$$ has the smallest $$$L_j$$$. We will add an edge from $$$i$$$ to $$$j$$$ if $$$L_j < L_i$$$.

        I suppose with this graph, the rest is pretty straightforward binary-lifting with one or two casework.

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

          Why is it correct to add edge to the j with smallest L? Doesn't seem right, for example, if we have {1, 2}, {3, 4} and {1, 5}, we will add edge from 3 to 1, so we will think there is no path from 2 to 3

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

            First, we can do casework for the answers 0 or 1.

            Otherwise, We will use binary lifting until we are on an event $$$i$$$ such that, $$$R_s < L_i$$$, and if we move one more edge this condition would be broken. Let's say we have moved $$$k$$$ edges using the Binary Lifting.

            From such $$$i$$$, if we move another time to its left (using the directed edge). We should come to the event $$$x$$$ such that, $$$L_x <= R_s <= R_x$$$. If we can't move or don't get such event $$$x$$$, then there is no answer. Otherwise, our answer would be $$$k + 2$$$.

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

              Ok, but why is "If we can't move or don't get such event x, then there is no answer." true?

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

                Sorry, missed a condition while adding the edges. Now it should make sense.

                (Condition wouldn't have mattered for the answer but it should help to get a perspective)

»
9 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Day 1 codes

Btw I knew Day1 P1 beforehand.

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

    Ah, this did indeed seem like a problem that could have appeared previously, but nobody in the SC was aware of this.

    Also, as a small challenge to everyone, we are not yet sure what the optimal solution to this problem is. We know of a solution that uses only $$$N-1$$$ queries, but maybe someone can do better? (For $$$N$$$ sufficiently large)

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

Will the editorial be posted?

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

    You should be able to download spoilers in the analysis mode which runs for 5 hours after each mirror, but we will also publish spoilers and test data on the website after both mirrors are over.

    • »
      »
      »
      41 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are they already posted? Where can I find them?

»
8 days ago, # |
  Vote: I like it +32 Vote: I do not like it

How to solve first subtask of day 2 problem 1?

  • »
    »
    8 days ago, # ^ |
    Rev. 4   Vote: I like it +11 Vote: I do not like it

    You can encode the 3 possibilities of X as 0000, 1111 and 0110. For 0000, the received sequence while decoding cannot have two consecutive 1 bits. For 1111, there cannot be two consecutive 0 bits. For 0110, there must be some consecutive equal bits. So, you can eliminate at least one possibility and return the other two.

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

      For 0110, if no messages will be wrong, there will be two consecutive equal bits?

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

        Sorry about that, I mistyped the part about 0110. I have corrected it now.

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

    I solved it with randomization.

    The key idea was to use the same seed while using mt19937 function for both encode and decode.

    For N = 3, we need to send two bits, let's call them b1 and b2 respectively.

    We will send a boolean vector sized 250, each of the indexes could represent one of the following things:

    1. it could be b1
    2. it could be b2
    3. it could be some random bit
    vector < ll > v(250, -1);
        vector < ll > b1, b2;
        mt19937 rng(K);
        for(ll i = 0; i < 250; i++){
            if(rng()%3 == 1 && (!i || v[i - 1] == -1) ){
                mx--;
                v[i] = rng()%2;  // random bits
            }else{
                if(rng()%2) b1.pb(i);
                else b2.pb(i);
            }
        }
        for(auto u : b1) v[u] = (1 << 0) & X;
        for(auto u : b2) v[u] = (X >> 1) & 1;
        for(auto u : v) send(u);
    

    We could simulate the same while decoding. So while decoding,

    If i_th number is a random bit, we would know what is the actual value of that bit and what we recieved. If they differ, then we would know for sure that i-1 th & i+1 th number is exactly what we sent (Those indexes would represent b1 or b2).

    So, if the number of changes while sending the bits are frequent then we can easily figure out X.

    Otherwise, we can assume the most of the bits we sent have sent aren't changed that much. So in this case, we can naively depend on the occcurences of 0 or 1 in the indexes of b1 for figuring out first bit, and the same for the 2nd one.

    Full code: https://ideone.com/diqCci

  • »
    »
    7 days ago, # ^ |
    Rev. 5   Vote: I like it +8 Vote: I do not like it

    There's a solution that uses at most 3 bits:

    For the first bit, encode() sends 1 if $$$n=3$$$ and 0 otherwise. Then there are two scenarios:

    • If judge sends 1, encode() sends a second bit: 1 if $$$n=1$$$ and 0 otherwise. If judge sends 1, then decode() knows that $$$n$$$ cannot be 2, since that would mean encode() sending 00 and the judge sending the wrong bit twice in a row. Similarly, if judge sends 0, then decode() knows that $$$n$$$ cannot be 1.

    • If judge sends 0, encode() sends the same bit as the first one again. If judge sends 0 again, then decode() knows that $$$n$$$ cannot be 3, using the same reasoning as above. Otherwise, encode() does the same as the above case for the third bit.

    In any case, decode() can eliminate one possibility and return the other two.

    Code (details are slightly different but idea is the same)
»
8 days ago, # |
  Vote: I like it +17 Vote: I do not like it

I got 100 points verdict on d2p3, but the scoreboard says otherwise :p

Anyway, thank you for the contest! I think d2p1 is interesting, but I was out for most of the contest time, so couldn't think much about it

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

    That was an interesting bug on our side that we hadn't experienced before... The scoreboard should now be correct :-)

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

How to solve day2 problem 3?

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

    Let dp[mask] be answer if we have this subset of groups. Now transition will be, dp[mask] = min_{mask&(1<<j)==true} dp[mask^(1<<j)]+cost[mask][j].How we can calculate cost? We can notice than if we have some groups already in place, when adding new group it's optimal to get some prefix of places from the left, and everyone else from the right. We can brute force the division point and calculate the cost, then tak minimal. To get full score notice than this function is convex, so you can binary search for best division point. To calculcate answer fast, you can use prefix sums, one prefix sum array for each group that is already in place, so you have to compute pref sums only once for every group you are calculatin cost for, and then just use it to find answer for every mask.

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

      I missed the part where the function is convex :( Nevertheless thanks a lot!

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

      How do you see that the function is convex, can you elaborate a bit more on your intuition ?

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

        Idk, it just immediately felt convex to me. The kind of reasoning I had is if we put m people going from the left, then our function will be roughly x^2 + (n-x)^2 + smth from groups already in place. Felt convex enough to me. I didn't prove it. I guess you can try taking derivative? idk

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

          Thanks for answering, the part that I have trouble understanding is, the "smth" from already placed groups is not going to mess up the binary searchability of the function.

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

            Yeah. But won't you be able to prove it if you look how this smth changed when you increase m? You add (amount on the right) — (amount on the left), this clearly not-decreases. So we have 1st derivative not-decreasing -> 2nd derivative non-negative -> convex or smth.

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

look at this dude

»
5 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Where can i upsolve boi 2022 problems?