ko_osaga's blog

By ko_osaga, history, 5 years ago, In English

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:

Tags ioi
  • Vote: I like it
  • +195
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

The scoreboard is no longer broken!

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

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

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

    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 years ago, # |
Rev. 3   Vote: I like it +112 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      $$$N \le 100000$$$

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

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

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

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

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

          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 years ago, # ^ |
              Vote: I like it -47 Vote: I do not like it

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

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

            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 years ago, # ^ |
                Vote: I like it -17 Vote: I do not like it

              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 years ago, # ^ |
                  Vote: I like it -13 Vote: I do not like it

                How can someone be too good for IOI?

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

                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 years ago, # ^ |
                    Vote: I like it -33 Vote: I do not like it

                  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 years ago, # ^ |
                    Vote: I like it +84 Vote: I do not like it

                  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 years ago, # ^ |
                  Rev. 3   Vote: I like it -32 Vote: I do not like it

                  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 years ago, # ^ |
                    Vote: I like it +29 Vote: I do not like it

                  :) 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 years ago, # ^ |
              Vote: I like it +18 Vote: I do not like it

            Seems like "another Nowruz" happened anyways.

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

              Today's task is way harder.

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

              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 years ago, # ^ |
            Vote: I like it +163 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +60 Vote: I do not like it
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            I didn't get 100 points lmao

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

              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 years ago, # ^ |
                  Vote: I like it +9 Vote: I do not like it

                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 years ago, # ^ |
                    Vote: I like it +58 Vote: I do not like it

                  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 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hey, i am it :)

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

            39613311 didn't get 100 pts?

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

          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 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

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

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

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

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

          Wow, you're right, sorry then :)

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

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

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

        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 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Do you think that IOI is prestigier than ICPC?

»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

The tasks for #ioi2019 first competition day:

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

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +80 Vote: I do not like it

Can someone verify?

Solution for problem split
»
5 years ago, # |
Rev. 3   Vote: I like it +38 Vote: I do not like it

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

Spoiler
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -54 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it
split, 25x over-complicated and fixed
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +28 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        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 years ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

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

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

        I tried every root and only got 40.

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

    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 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
Rev. 7   Vote: I like it +9 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 7   Vote: I like it +9 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 4   Vote: I like it +3 Vote: I do not like it

          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 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't it 331?

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

      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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell what appeal is about?

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

      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 years ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it about the solution for p3?

»
5 years ago, # |
  Vote: I like it -39 Vote: I do not like it

...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 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Benq is so strong.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody knows how to solve walk problem?

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

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

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

        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 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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 years ago, # ^ |
            Rev. 2   Vote: I like it +58 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it -51 Vote: I do not like it

              We don't talk about this problem.

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

                I mean I thought that line is the same type as nowruz.

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

            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 years ago, # ^ |
              Vote: I like it +15 Vote: I do not like it

            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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How to solve in n+3 segments?

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

          Implementation is in my github.

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

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it -23 Vote: I do not like it

        About 50 points.

        People over 90 points did something provable, I think.

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

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

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

          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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    I did that in the contest.

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

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

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

        Can you write how to do that exactly?

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

          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 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Can anyone verify my solution to walk?

Spoiler
  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

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

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

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it -10 Vote: I do not like it

      You don't need to detect intersection?

      Green is that "escape" edge.

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

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

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

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

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

              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 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  For instance, consider

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

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

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

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +66 Vote: I do not like it

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

Too bad he had a awful day1 :(

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +65 Vote: I do not like it

    Nope, you got it wrong. tmwilliamlin168 performed horribly in day 1 intentionally just to make this ultra-awesome comeback in day 2. No one can ever match the geniosity. Ever. tmwilliamlin168 orz

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

      Can someone explain what orz means, I've seen it a hundred times in codeforces.

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

        orz is a person bowing down on the ground. If you look carefully and squint your eyes you can see it. The "z" is the legs, the "r" is the body, and the "o" is the head

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

          One thing to note is that whenever "orz" is used on me, it is always sarcastic.

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

            One thing to note is that when ultra-awesome genius pr0s respond to compliments, it is always sarcastically.

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

            You are such a great person because of your humility!

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

IOI 2019 preliminary results are available on IOI Stats.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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 years ago, # |
  Vote: I like it -29 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

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

    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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    (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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +184 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    '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 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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 years ago, # |
  Vote: I like it +340 Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Tests when?

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem walk? At least for 57 points

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

    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 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      That's because in subtask 4 (go from first building to last) you also only need to move to the right.

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

        Not just that, you can also assume that all heights are equal in subtask 4.

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

      How do you make that dp with set in less memory and time? Because there can be many intersections

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

        Use set of $$$(j, dp[i][j] - x_i)$$$ don't store value if $$$dp[i][j]=dp[i][k] + |j - k|$$$ for some $$$k\neq j$$$.

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

          What if you have to store many values still?

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

            Use sweeping line, many values do not change.

»
5 years ago, # |
  Vote: I like it +209 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.