Блог пользователя ko_osaga

Автор ko_osaga, история, 5 лет назад, По-английски

Hello!

International Olympiad in Informatics (IOI), the most prestigious programming contest in the world, is held in a beautiful city of Baku, Azerbaijan this year.

Wish the best luck to every contestant!

Day1: The contest had started on time, but the scoreboard is broken. It seems there is no mirror this year.

Day1 Contest Overview: Benq solved all Day1 problems in only 3.5 hours, congratulations! Full scorers for each tasks: 23(rect) / 170(shoes) / 6(split)

Day2 Contest Overview: The winner for Day2 is duality, but Benq still secures his consecutive IOI win. Congratulations! Full scorers for each tasks: 0(line) / 47(vision) / 2(walk)

Contest Results

  1. Benq 547.09
  2. 300iq 511.22
  3. duality 494.33
  4. TLE 491.46
  5. FizzyDavid 482.39

Country Ranking

  • 1 Russia 4G
  • 2 China 3G1S
  • 2 United States of America 3G1S
  • 4 Republic of Korea 2G1S1B
  • 4 Vietnam 2G1S1B

Congratulations to everyone who competed, and especially to our super awesome team gina0605 GyojunYoun Onjo blackbori !

Useful Links:

Теги ioi
  • Проголосовать: нравится
  • +195
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

The scoreboard is no longer broken!

»
5 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

It seems there is no mirror this year.

How do you know that?

Also, I see you downloaded the task statements, how did you do that? I can't find anything on the IOI site.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

    He has access to the tasks because he is a leader for team Korea.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    How do you know that?

    It's just a guess :p

    I see you downloaded the task statements, how did you do that?

    I downloaded it last night because I was helping the translation.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +112 Проголосовать: не нравится

Abridged statements:

shoes: You are given $$$2N$$$ nonzero but possibly negative integers. You should minimally swap adjacent pairs to achieve:

  • $$$|X_{2i}| = |X_{2i+1}|$$$
  • $$$X_{2i} < 0, X_{2i+1} > 0$$$

for all $$$0 \le i < N$$$. What is the minimum required swaps? It's guaranteed that it's possible. $$$N \le 100000$$$

split: Given undirected connected graph $$$G$$$. find a tripartition of $$$V(G)$$$ of size $$$a, b, c$$$ respectively ($$$a, b, c$$$ given in input), where at least two of the partition is “connected” (it’s induced subgraph is connected). Return the tripartition or state that it's impossible. Note that it's partition, so $$$a+b+c=n$$$. $$$|V(G)| \le 100000$$$

rect: You are given a map of $$$N \times M$$$ grid where each cell has integer height $$$0 \le H[i][j] \le 7000000$$$. A rectangle is a set of rectangular area $$$[x1, x2] \times [y1, y2]$$$ s.t $$$1 \le x_1 \le x_2 \le N-2, 1 \le y_1 \le y_2 \le M - 2$$$ (so should NOT contain cells in edges). A rectangle is valid if for each cell $$$(i, j)$$$ in rectangle, $$$min(H[x1-1][j], H[x2+1][j], H[i][y1-1], H[i][y2+1]) > H[i][j]$$$ holds. Count the number of possible rects. $$$N, M \le 2500$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What's the constraint of $$$N$$$ in problem `shoes'?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      $$$N \le 100000$$$

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        Change "7M" to normal number, it's confusing.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +65 Проголосовать: не нравится

        Also, shoes are identical to this task, but IOI has higher limits (editorial tells how to solve higher limits anyway).

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +59 Проголосовать: не нравится

          This issue was raised in the GA meeting but was rejected.

          I don't like it too, but apparently, ISC didn't found the better task, so maybe it's better than yet another Nowruz.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится -47 Проголосовать: не нравится

            Ask me next time, I have a couple of good tasks prepared.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +107 Проголосовать: не нравится

            After reading this comment I want to downvote somebody, but I know that it isn't your fault. :/

            Good that there are some other comments which deserve downvotes xd

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится -17 Проголосовать: не нравится

              Well, if you need to downvote someone to make yourself feel better, feel free to downvote me. I was one of the delegation leaders who voted to keep the problem, and for me this was a conscious decision after thinking about the proposed problem (with the subtasks it had and everything) and feeling that the problem was different enough. The post by eduardische below shows that your "identical to" was far from being correct.

              I guess the problem you (and on other occasions, many other strong contestants) have is that you are only evaluating the problem from your own point of view. Sure, to you as a contestant the problem may look identical, but that's just because you are too good and you don't realize the difficulty the additional steps bring.

              In this particular problem, the Codeforces version is just the old "when you are arranging stuff by swapping adjacent elements, don't make unnecessary swaps". I assume that nobody who solved it in the contest spent any time to think about the faster solution, and I'm convinced nobody tried to implement it. And you are also being unfair when you claim that the editorial tells you how to solve the IOI problem. It doesn't. It's just a single sentence that tells you that you have to use an efficient data structure. Well, if you are an average IOI participant, that part is already obvious from the constraints. But while to you it may also be obvious how to use it, it definitely was not obvious to every participant. Plus, the IOI problem brings a bunch of new stuff you have to deal with: What if the leftmost shoe is a right shoe? How exactly should I handle multiple shoes of the same size (both in the idea and in the implementation)? All of these questions are suitable challenges for someone who aims for bronze.

              From where I'm sitting, the IOI problem is a nice generalization of the CF problem. Solving the CF problem helps a bit, but so does solving any other problem about swaps of adjacent elements, because the only thing it actually gives you is intuition on the greedy strategy. There is enough new that is neither in the CF problem, nor explained by the note in its editorial.

              Problems that are both easy enough and significantly more original than this one are incredibly rare.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 лет назад, # ^ |
                  Проголосовать: нравится -13 Проголосовать: не нравится

                How can someone be too good for IOI?

              • »
                »
                »
                »
                »
                »
                »
                »
                5 лет назад, # ^ |
                  Проголосовать: нравится +77 Проголосовать: не нравится

                The editorial mentions the following:

                If the leftmost person is in pair $$$a$$$, swap the other person in pair $$$a$$$ left, to the second position. Now the first two people are both in pair $$$a$$$, and we repeat the process on the remaining $$$n-1$$$ pairs of people recursively.

                Add "in case of tie pick leftmost", then you get 85 points. So until 85 points, it's an identical problem.

                I think your typical argument of "you are a soulless red coder but purples will agree" is nonsense. You are just avoiding criticism. “Pick leftmost" strategy is clearly doable if you studied hard enough to remember that CF one. I was blue 5 yrs ago, and I also hold contests for blue. Don't dismiss them, or us.

                Problems that are both easy enough and significantly more original than this one are incredibly rare.

                Agreed, but this is IOI, so they are usually one of the best problems in the world. Problems such as 2015 boxes, 2018 combo are easy enough but much more innovative.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                    Проголосовать: нравится -33 Проголосовать: не нравится

                  I haven't been involved in selecting the problems for this IOI in any way other than raising my country sign along with 70+ other people, so at least in this context "avoiding criticism" makes no sense to me -- I'm not the one being criticized when people dislike that this problem was used. I'm just trying to explain why I personally find the problem OK. Or more precisely: not great, not terrible.

                  I don't understand the obsession with originality at all costs -- given that it's hardly possible nowadays, and it can only get worse. E.g., I also love the task Boxes, but I can easily show you older problems that are easier versions of it in the same sense in which the CF task was an easier version of the IOI task this year. There are literally hundreds of thousands of problems out there, and if you dig enough, you'll find something that uses the same idea -- especially if that idea is easier. Most of the easy IOI problems are similar to other problems that have appeared before. IMHO, on its own this should not be perceived as a bad thing.

                  At the IMO it's common that problems 1 and 4 can be solved using standard techniques, and everybody expects that the well-prepared contestants will easily, quickly and consistently solve them, as they would have seen and solved ten similar problems before. The problems 1 and 4 are there to challenge the lower part of the field, not the crowd fighting for gold.

                  The IOI needs to do the same. In order to be as fair as possible when handing out the medals in the end, the problem set cannot be top-heavy only. If you do that, you would have a clear winner and random noise in the middle of the ranklist. The problem set needs to have parts that discriminate well around each of the medal boundaries. If you are really lucky, someone will contribute an easy ad-hoc problem, but in past years that happened only rarely and going forward such problems will only be more rare. Most of the easy IOI problems will have to look like this one: be based on clever use and modification of standard techniques. This is precisely the type of problems for which everyone who (to use your words) "studied hard enough" will have already seen the technique and they just have to apply it to solve the problem. In my point of view, this is precisely what was going on in the Shoes problem. In particular, I'm convinced that the CF problem gave less advantage to people who solved it than e.g. any of the many problems in which you move stuff to the left of an array and use a Fenwick tree to keep track of it. That implementation is much closer to what they had to write here.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                    Проголосовать: нравится +84 Проголосовать: не нравится

                  I don't agree to your opinion about IMO. It's true that well-prepared contestants solve problems 1 and 4 easily, but I don't think it's because they have seen ten similar problems. At least, I always expected to see problems easily solved but with new or uncommon ideas.

                  Nevertheless, it's hard to find an easy, interesting and new problem, so you may not be able to put one in IOI. Only in such a case should tasks like shoes (easy and interesting but not new) be used.

                  But actually, in this year's IMO, problems 1 and 4 are very typical and everyone who studied hard enough must have already seen the technique and they just have to apply it to solve the problems. So, organizers, including leaders, probably think in the similar way.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится -32 Проголосовать: не нравится

                  Re IMO, I think I have similar expectations as you but I use different words to describe them. I do expect those problems to be uncommon in the sense that I would not have seen that exact problem before, I just expect them to be standard in the sense that I would have seen and used the techniques that work on them before. Or, more precisely, what usually makes these problems easy to me is that the techniques you'll try intuitively will work, and gaining that intuition is precisely thanks to the practice we put in. E.g., you read 2018-4, you see that it's about chess knights, you remember problems about placing many knights onto a chessboard and related invariants, and you apply those to this problem.

                  I guess another part of the problem is that originality is not binary -- problem isn't just "original" or "not original", it's (at least) somewhere on a real-valued scale and different people with different experience will necessarily place it on different places on that scale.

                  I agree with everyone that problems that fall on the "more original" end of the spectrum for most people are the best. I would love to have such IOI and IMO problems every year, I just don't expect that we can realistically have that, and I'm saying that the second best is still not a tragedy if we don't.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                    Проголосовать: нравится +29 Проголосовать: не нравится

                  :) Haha you reminded me of this problem I wrote for an ACM contest that was identical to 2015 Boxes. It didn't cause big problems though, as that contest was only one week before IOI2015, and only one China team member had seen this problem beforehand

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +18 Проголосовать: не нравится

            Seems like "another Nowruz" happened anyways.

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +10 Проголосовать: не нравится

              Today's task is way harder.

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +39 Проголосовать: не нравится

              I think it's OK because that problem has the correct solution. I believe the data was given as output-only because it was very tricky, and there is a benefit of giving input data with visualizers.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +163 Проголосовать: не нравится

          Wow, ksun48's only CF task ever can make IOI???

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +60 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится

            I didn't get 100 points lmao

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится

              There was a major objection on this task that it was too similar to the task on CF with only restriction bump (but the editorial discussed the faster solution) and the unimportant complications; and the argumentation was that around 40 IOI contestants competed in that round.

              ISC recommended that since it believes there are enough differences between the tasks, it was designed to be the easiest task of the set, and the backup option wasn't recommended as viable by ISC; to keep the task as is. There also was a precedent for the situation back in 2016, when the task found to be close to the one used in ICPC contest was kept, partially because it was also designed to be easiest in the set, although to be fair, that task was from way earlier contest 10 years ago at the time. This objection was voted down by 58 to 4 votes with 3 abstentions to keep the task in, which later was claimed by the delegation who lodged the complaint to be simply because many countries have already started translating the task and didn't want to translate another task, which I personally find very arrogant and disrespectful towards other delegations.

              At the end of contest, I found 13 people who solved the task on Codeforces but didn't get 100 points for it, which in my eyes show that the ISC recommendation was well intended and that the task wasn't that identical to the one on Codeforces.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 лет назад, # ^ |
                  Проголосовать: нравится +9 Проголосовать: не нравится

                While I agree that you have some valid points, "very arrogant and disrespectful" perfectly fits you, who namechecked all 13 people without 100 points.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                    Проголосовать: нравится +58 Проголосовать: не нравится

                  I'm going to assume that by "namechecked" you meant "named", as I did check the entire table from the mapping to CF handles, and I fail to see how analysing publicly available data is arrogant or disrespectful. I'm assuming number 40 yesterday also didn't come up from the thin air.

                  However, I agree that it was not the right decision to implicitly name the 13 people I found as the backup for the data and I apologize for that if it caused any offence. Simple aggregation would have been enough, so I concede to your description in this instance.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится

                  I was one of those 13 people, I dont feel offensed. Also something to consider is, its an older contest, I didnt even remember solving this problem. I didn't even remember it existed. It was 14 months ago

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Hey, i am it :)

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            39613311 didn't get 100 pts?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

          To give more data to people who are not in the GA meeting, ISC also pointed out the fact that at least 3 of the ISC/HSC (I forgot who is the other one, sorry) solved the problem during the contest (in $$$O(N^2)$$$) and did not realize about it when reading the task.

          To me, the greedy intuition is "just another simple greedy intuition" that we can easily forget after solving the Codeforces task. Even if contestants do remember, there are still the additional steps to solve the problem. As demonstrated by eduardische above, some contestants did forget about the problem, or did not manage to solve the additional steps.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    In problem "split", it isn't always possible is it? Do we have to determine whether it is possible as well?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      Consider a star. Also, consider this sentence: "Return the tripartition or state that it's impossible."

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        Oh, the sentence was not there when I commented, thank you for pointing out :)

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Wow, you're right, sorry then :)

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          It was done by myself before your comment, so somehow you got the older revision? Thanks for the clarification anyway.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        A "state that it's impossible" phrase isn't really a guarantee that the task really is impossible; it might be just a trick of the setters. But I agree, the star case is enough to show impossibility.

»
5 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

Do you think that IOI is prestigier than ICPC?

»
5 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

The tasks for #ioi2019 first competition day:

http://jonathanirvin.gs/files/ioi2019/

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
»
5 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Problem split reminds me this theorem (Can be spoiler): Link to arXiv

»
5 лет назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

Can someone verify?

Solution for problem split
»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +38 Проголосовать: не нравится

Task split is in my opinion completely amazing, easily best problem of the year so far!

Spoiler
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -54 Проголосовать: не нравится

    Even though I solved the task, I have no idea what you're saying here...

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится
split, 25x over-complicated and fixed
  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    Well, I come up with the same idea about biconnected components, but it was looking very complicated, so I gave up and started merging shitty solutions to get 64 (°ー°〃)

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      For split, it seems to have numerous heuristics that is almost impossible to break.. I believe 64 points worked by trying all DFS spanning trees in each root.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится

        I thought the same, but somehow organizers made tests really strong, kudos for that. I thought it would be impossible to break heuristics and this task will have like fifty solutions for 100pts, but only five of them would be legit solutions. It's great to see I was mistaken in that prediction.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится

        No, it doesn't work. My solution is much harder (・へ・)

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I tried every root and only got 40.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

    Sorry, can you please post your sketch of proof? I've been thinking about it for a while and it seems to me that there may be a counterexample. Consider a = b = c = n/3. Let's construct the graph like this: there is a clique of size 2*a-2. The other a+2 vertices we add as single edges attaching to distinct nodes in the clique. In this case we have a solution (consider one added vertex and a-1 vertices from the clique, times two), but if I understood your solution correctly, neither of your statements hold. The biggest biconnected component is of size less than a+b, and after we remove any articulation point we get components of sizes N-2 and 1.

    Sorry, I don't post comments often so I don't know how to use math mode.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Oh shoot, you're right! I think I know how to fix this, but it's even more complicated and starts looking like "the model solution, only with extra steps". I'll try to edit my post in a moment. Thanks!

      Edit: done, hopefully. I had a false statement in my proof that went like: "if after removing any articulation point $$$v$$$, there exists a connected component of size $$$\ge \frac{2n}{3}$$$, then there exists a biconnected component of size $$$\ge \frac{2n}{3}$$$". It's false, obviously. Silly me...

»
5 лет назад, # |
Rev. 7   Проголосовать: нравится +9 Проголосовать: не нравится

I want to share my idea for rect and split. (I haven't tried to implement yet, so please correct me if I'm wrong).

Rect:

Hint

Split:

Hint
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I don't see how preparing (x1, x2, j) states easily helps you to solve the whole problem. Can you explain a bit more?

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 7   Проголосовать: нравится +9 Проголосовать: не нравится

      Well, after preparing all (x1, x2, j) and (y1, y2, i) states, you can merge two adjacent states together, for example (x1, x2, j) with (x1, x2, j + 1) or (x1, x2, j − 1).

      So we can deduce to the new problem:

      Given P rectangles of type 1: [(a1, b1), (c1, d1)] and Q rectangles of type 2: [(a2, b2), (c2, d2)]. Count number of pair rectangles x of type 1 and y of type 2 such that a1(x) <= a2(y) <= c2(y) <= c1(x) and b2(y) <= b1(x) <= d1(x) <= d2(y).

      You can fix the segment [b1(x), d1(x)] and sweep line those segments [b2(y), d2(y)]. So all you need to do is to calculate the number of rectangles y such that a1(x) <= a2(y) <= c2(y) <= c1(x).

      It seem that this kind of problem can only be solved in O(P * log2(N) * log2(M)). However, you can see that for every pair rectangles y1, y2 of type 2 that have overlapped area, there are only two cases:

      1. a2(y1) <= a2(y2) <= c2(y2) <= c2(y1).

      2. a2(y2) <= a2(y1) <= c2(y1) <= c2(y2).

      With that observation, you can reduce the complexity to O(P * log2(Q)).

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I got to all your points above, but I fail to see how that last observation reduces the complexity to $$$O(P\log Q)$$$. Can you elaborate?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

          You can sort all pair [a2(y), c2(y)]. For a query, you want to calculate the number of pair [a2(y), c2(y)] such that a1(x) <= a2(y) <= c2(y) <= c1(x).

          To answer a query, first, you can calculate the number of pair [a2(y), c2(y)] such that a1(x) <= a2(y) <= c1(x). So all you need to do is to calculate he number of pair [a2(y), c2(y)] such that a1(x) <= a2(y) <= c1(x) < c2(y) (*) to subtract the result with this.

          You see that all the rectangles of type 2 satisfying the (*) condition have overlapped area, so there are only two cases as I mentioned in the comment above. Or if we call S as the subset of rectangles of type 2 satisfying the (*) condition, it is true that:

          1. a2(S[i]) <= a2(S[i + 1]) (0 <= i < |S| − 1).

          2. c2(S[i]) >= c2(S[i + 1]) (0 <= i < |S| − 1).

          You can find S[0] position and S[|S| − 1] position on the segment tree by storing something like (does this segment contain an element equal to 1, if it does what is the maximum c2 value of an element equal to 1).

          UPD: I just realized that my above solution is wrong. So I'm very glad to hear another solution if possible.

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

For the purpose of medal allocation, after day 1 the official number of contestants is 327. (This number cannot go down after day 2, and most likely it should not change.)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Isn't it 331?

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      No, 327 is the number we were told at the meeting after day 1. AFAIK, four of the contestants who were shown in the online results are contestants who were registered for the IOI but did not take part in day 1. The most likely reason is that they are not here and they won't take part in day 2 either, but I don't know for sure whether this is the case. (And in the past there were some cases when some contestants only took part in day 2 for various reasons.)

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

There was an accepted appeal that still is being worked on that may or may not result in the score change, so at this point results of Day 1 are not final.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you tell what appeal is about?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      According to ISC, some contestant or contestants were not able to submit during the final moments of the contest due to CMS slowness. If any of that submission would've gotten a bigger score, it may be submitted manually and the score would be updated. My understanding is that there are backups of workstations at the time of contest end, so any changes made during the analysis shouldn't be a factor.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        Im not 100% sure if i managed to change it in time, but i might have an ac code for shoes on the machine at the time when the contest ended. Is there some chance that someone can check that? I will provide details if it's possible.

        Edit: i guess that i have to do that with my team leaders and it too late for that now, plus im not sure if the appeal is valis and its "only" 15 points so it doesn't matter that much.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

          Yes, officially it's the case that your team leader has to submit an appeal. Before dinner we were told to submit these appeals if we have them and didn't submit them before, and there was no strict deadline on this. Get in touch with your leader, you have nothing to lose by doing so. Ideally, send them the exact name and location of the file you want rejudged.

          (Edit: I would recommend that your leader should send the details to the ISC by email ASAP and to formally file an appeal on paper later, if required.)

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          There just was an e-mail distributed amongst GA that if students were affected by the issue at the end of the contest, and haven't yet submitted an appeal, that the deadline is tomorrow noon (in ~13h from now). So definitely contact your leaders! You'll need exact path and filename on your machine to be evaluated.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is it about the solution for p3?

»
5 лет назад, # |
  Проголосовать: нравится -39 Проголосовать: не нравится

...is held in a beautiful city of Baku, Azerbaijan this year.

Sorry for the offtopic, but maybe you should have written " a beautiful city of Azerbaijan, Baku " ?)

»
5 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Benq is so strong.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anybody knows how to solve walk problem?

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

It seems sad that line problem can be solved in a fully provable way (what problem highly suggested, right?), but nobody solved it and it boiled down to basically pushing through some garbage heuristics. However I don't know how to solve it as well, so I am not to blame contestants, but just stating fact that it's sad :P.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Well I don't think that problem highly suggested it. I didn't thought that it is possible to solve in provable way lol. Maybe n+3 is just a parameter they used for test generation

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      There's a relatively easy $$$n+3$$$ solution.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Yeah I know now, but during the contest it was not clear for me that it is solvable for any test case in n+3

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          Ok, but in general: why would a problemsetter set a problem that cannot be fully solved (I mean the one that doesn't have 100pts solution)?

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +58 Проголосовать: не нравится

            What about nowruz? I thought that it is the problem of the same type.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

            BOI 2019 Flash 100 points in this task is the theoretical maximum if you have infinite time. Nobody knows the 90+ solution as far as I know.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +15 Проголосовать: не нравится

            Huh, because 90% of output-only are not meant to be solved in a provable way? Fact that solution for given instances with <=n+3 exists is significantly different than fact that any instance you can imagine has solution with <=n+3 segments. A priori it is possible that tests were generated by creating some broken line with <=n+3 segments and marking some points on them what makes it very easy to create test like that which would then be hard to solve (similar to as it is easy to generate a graph with hamilton cycle, but it is hard to find it afterwards).

            So, my conclusion is that contestants could definitely suspect that some general provable algorithm exists, but can't be sure about it.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        How to solve in n+3 segments?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
          Spoiler

          Implementation is in my github.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    AFAIK it's solvable for every instance in $$$N+3$$$. I'm aware of the basic idea, but that's all :(

    Giving a normal problem as an output only has several pros and cons. For the good thing, the contestants were given visualizers, so they can easily spot what's going on (very helpful for a tricky problem like this), plus the scoring system can help break ties. For the bad thing, it gives room for ad-hoc test analysis and garbage heuristic which isn't science at all. And due to some bad past practices on OO tasks, contestants might consider the search for $$$N+3$$$ solution as a "risky strategy".

    In general, I think the contestants got what they deserve, but some might consider the "naive spiral strategy" as garbage and should not get more than 10 points. I don't have a very strong opinion about that...

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How many points did spiral give? Indeed seemed garbage to me (however on random test I guess it should be ok), but I didn't try it

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -23 Проголосовать: не нравится

        About 50 points.

        People over 90 points did something provable, I think.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +34 Проголосовать: не нравится

          Lol I have 90+eps and I just used some greedy.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +14 Проголосовать: не нравится

          My solution(try going in the same direction as previous one by, for example, if the last line was going up, going to a point above the last point; try to keep yourself in the middle by taking the point with the median x coordinate out of all the candidates if you're going up or down and taking the point with the median y coordinate out of all candidates if you're going left or right; it's n^2 log n but TL is 5 hours) gets between 2 and 6 points on all tests which are structured like diagonal lines(i think tests 2 and 7 were crosses, test 5 looked like this:  and test 4 was a diagonal line) and more than 9 points on all other tests. The union of my solution and my teammate's solution(decompose the input into a small amount of monotone sequences and handle each of them separately) seems to get 88 points.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Did anyone solve vision with prefix xor over columns/rows and addition of H + W bits?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did that in the contest.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      I think the easiest solution is to do prefix xor on diagonals and check if $$$dist >= K$$$ and check $$$>=K+1$$$

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you write how to do that exactly?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          I think $$$|r_1-r_2|+|c_1-c_2| = max(|r_1+c_1-r_2-c_2|,|r_1-c_1-r_2+c_2|)$$$. If you do prefix xor for diagonals $$$(i+j)$$$ and $$$(i-j)$$$ when you will have some consecutive number of ones (let's say $$$a$$$ and $$$b$$$). We need to check that $$$max(a, b) = K$$$. That means $$$max(a,b)>=K$$$ is true and $$$>=K+1$$$ is false. To check if $$$a>=C$$$ try anding $$$(i)'th$$$ and $$$(i+C)'th$$$ element.

»
5 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Can anyone verify my solution to walk?

Spoiler
  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

    Nah, that won't work.

    You will not detect the intersection marked with dot.

    (Edited after ~300iq pointed out my previous counterexample was wrong).

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      I think it will detect it, cuz this intersection is adjacent to the right vertex of the upper segment.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Whoops, sorry, thanks. However I still think it doesn't work and I will update the picture in a second.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

      You don't need to detect intersection?

      Green is that "escape" edge.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

        Where does the green line come from? You can't just add it in.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          When the horizontal segment ends, we make an "escape route vertices", where we make vertices for two horizontal segments, vertically adjacent to that endpoint.

          You are making escape edges too.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Escape edges have to be along an existing vertical pole; otherwise, we allow some invalid solutions.

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              I think that we need to add some escape edges without existing pole, if they are correct. Without it this solutions is completely incorrect.

              But I am not sure if what I am saying makes sense.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                It's true you sometimes can, but it doesn't work in general. I think if you can show that you're only moving left->right, then you're allowed to, but it actually could be wrong for this case.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  For instance, consider

                  ______
                  |    |
                  |    |
                  |-|  |
                  | S  T
                  

                  Adding an escape edge upwards from S to the top bar would illegally shorten the path.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    This doesn't work (as described by Swistakk), but here's a modification which I'm pretty sure does:

    For each horizontal segment, insert vertices:

    • At each endpoint
    • At the closest intersections to the left and right of s, if it passes over s
    • At the closest intersections to the left and right of t, if it passes over t

    Also, insert vertices at the intersections on poles directly above and below all the ones we listed. This gives $$$\le 18 M$$$ vertices, and then we run Dijkstra.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I solved it in contest using the exact same way. I didn't prove the correctness, though.

»
5 лет назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

tmwilliamlin168's insane comeback was probably the best thing to watch in day2, change my mind.

Too bad he had a awful day1 :(

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

IOI 2019 preliminary results are available on IOI Stats.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Is country rank based off of sum? Or lexicographical order of medals? I guess the latter is a tad bit more favorable to Korea ;) Anyway, congratulations to your team on a great performance!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    Thank you, and congratulations for team USA! I think the former is better, but we (our government?) always considered country rank based on medals. Even in 2015, where we were the absolute 1st place in score order, we used medal based rank :)

»
5 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

Why did sunset perform so poorly, taking only 49th place, who knows?

»
5 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

To leaders: how many appeals were there and how close is this preliminary result to a possible outcome?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have not heard about any changes to the results during the meetings or some private conversations with other leaders. In other words, I have no reason to believe that any major changes will be made to the scoreboard.

    Of course, I could be wrong...

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    (I am the USA deputy leader.) There are between 5 and 10 appeals, maybe one or two still under review. In general, the vast majority of appeals are rejected.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My understanding is that several instances of accepted appeal for first day are still in progress.

»
5 лет назад, # |
  Проголосовать: нравится +184 Проголосовать: не нравится

I stumbled upon a post by Olimpiada Informatyczna. As my Polish is very basic I gladly used the Facebook translator. But what does the following sentence mean?

I spent the evening mostly with the Russians, the Russians, the Russians, the Russians, the Russians, the Russians and the

Better check the original!

Spędziłem wieczór głównie z Gruzinami, Bułgarami, Estończykami, Rosjanami, Ukraińcami i Białorusinami, szlifując mój rosyjski.

Not cool, Facebook!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    It's not FB's fault, it's the algorithm's fault! (Classic excuse when something goes wrong.)

    Or it must be those Russian hackers FB and similar media worried about so much.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    'I spent the evening mostly with the Georgians, Bulgarians, Estonians, Russians, Ukrainians and Belarusians practicing my Russian.'

    The blog made by Polish leaders is amazing! Though they haven't written that in English :(

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    If we will have some international audience, we might consider translating our posts.

»
5 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

The GA have voted to approve IOI 2019 results and medal allocation.

There have been several changes of scores from preliminary results as results of appeals but none have resulted in changes in medal allocations.

»
5 лет назад, # |
  Проголосовать: нравится +340 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

Tests when?

»
5 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Does anyone have solutions and\or test data for the problems?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem walk? At least for 57 points

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    The first 2 subtasks are trivial (just run dijkstra).

    For subtask 3, you will only go right since you should never visit the same building twice. We can write a DP solution, where dp[i][j] = min cost to get to building i at height j. We can use a set to do this efficiently.

    Subtask 4 seems harder than subtask 3 since the heights are not equal, but...

»
5 лет назад, # |
  Проголосовать: нравится +209 Проголосовать: не нравится

You can submit all problems except Rectangles here: https://oj.uz/problems/source/420

It seems someone forgot to make rect.zip public on the folder here..

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody explain the solution for task vision, I got up to 66 points, but I couldn't think of anything better, also I couldn't find any editorial on the internet.