gigabuffoon's blog

IOI 2018 Scoreboard
By gigabuffoon, history, 6 years ago, In English

Here's the link: https://ranking.ioi18.net/Ranking.html

How excited is everyone?

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

»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I am literally shivering with excitement!!

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

It's not loading anymore. Kinda expected more from Japan.

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

livestream & rank : http://live2.nicovideo.jp/watch/lv314346295

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

Are there public statements available?

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

What? In 30 minutes all problems all solved by Benq

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

    No, he solved all problems in 4:14:25

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

Let's discuss problems. Who has any idea?

→ Reply
»
6 years ago, # |
  Vote: I like it +78 Vote: I do not like it
Hint for B
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why you don't in China IOI team?

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

      Mainly grade. You need to be senior high school student to qualify in China. Anyway I'm not sure if I would qualify.

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

        how suck the system is

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

        So even fateice wasn't allowed to qualify because he is not in 12th grade?

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

          No, he was unlucky :(

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

            Oh, ok. So next year you and FizzyDavid will be allowed to participate?

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

              Yes. Anyway there're selections.

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

          No,I got 16th in a match which was used to select top 15 competitors.

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

            Oh, ok. Next year dude!

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

              It's a pity that I don't have the next year.

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

                Oh damn it. Sad how competitors like you don't make it but others like babin do. :))

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

                  Qualifying to IOI (and ACM ICPC World Final) can be surprisingly easy or next to impossible, depend on where you were born.

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

                  Qualifying to top companies can be surprisingly easy or next to impossible, depend on where you were born.

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

                  Pretty sure qualifying to top companies doesn't depend on where you were born. When there are a lot of applicants from some country, there aren't any country-wide selections of a small number of people that will get interviewed.

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

                  Actually it's not about born in a better competitive programmer country but born in better country.

                  That's not a problem we can discuss in these comments anyway. Don't wanna be a bitch about it, but even at the visa phase you can fail because of that shit.

                  Well of course it's not about how many guys applied in a specific country.

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

                  Yeah, bureaucratic bullshit or some asshole on a power trip setting your life back is something that happens. I guarantee it's not only in your country.

                  At least unlike olympiads, you can always try again until it works.

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

                  That's not completely true. Read this maybe https://www.quora.com/Is-20-hours-of-competitive-programming-per-week-enough-to-get-to-IOI-Im-from-India-and-the-competition-here-isnt-as-serious-as-it-is-in-China-or-USA/answer/Pushkar-Mishra

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

wow, i'm Benq fan!!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it
hint for A
→ Reply
»
6 years ago, # |
  Vote: I like it -36 Vote: I do not like it

It's really excited. But Is It Rated?

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

    Another fighter for the last on the contribution standings!

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

How to solve werewolf?

I had a in time and in memory (C is a small constant ~= 8) solution which unfortunately MLE on the last subtask (it was able to get the 34 p. one). The idea uses a couple of small to large tricks and DSUs but it's quite long (and it doesn't pass for 100), so I won't explain it here. Did you have some similar solutions or the idea is very different?

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

    where do you submit ? can i have the mirror?

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

    Did you reduce to check if two subarrays of two permutations have common element? If so, a simple Mo's algorithm with a tricky technique may pass.

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

      Note: There's no mirror so I couldn't test this.

      If a and b are the permutations, then checking if al, ..., ar and bL, ..., bR share an element is equivalent to having points (i, b - 1(ai)) for i = 1... n (where b - 1(ai) is the index of ai in b) and checking if there is point in the rectangle [l, r] × [L, R]. Counting the number of such points can be done offline with sweepline + fenwick tree in time and memory.

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

        I got AC with this in analysis session.

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

      Can you explain the reduction in more detail?

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Spoiler
      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +32 Vote: I do not like it

    Mine is of similar complexity ( time, memory if I remember correctly)

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

    My solution that passed actually uses 2 DSUs with 2 small-to-large.

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

    I don't know if my solution is correct but what i do is compute the smallest i can go for each Si with one DSU in offline fashion for all queries (ordered by L decreasing). Then I process the queries (ordered by R increasing) and use another DSU to check if that smallest node is reachable from each Ei. This is a total complexity of O(QlogQ + Nα(N)) runtime and O(N + Q) memory.

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

      I may have understood you wrong, but I think the meeting point shouldn't necessarily be the smallest / largest valued node reachable from Si, because some other nodes unreachable from Ei may be blocking it off.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -62 Vote: I do not like it

Second place the georgia!!! georgia for the win! georgia will got first place in one year, and in two years too.

→ Reply
»
6 years ago, # |
  Vote: I like it -59 Vote: I do not like it

where I can see the problems?

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

How to solve A?

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

    Determine the first letter with 2 queries ( First query two letters like AX, so you can discard two letters, and then query just one ) Then, for every letter from 2 to N-1 do the following ( Assume the first letter of S is ‘A’. For the other cases its the same process but different letters )

    Let s be the prefix of S that you already know.

    Ask s + ‘B’ + s + ‘XB’ + s + ‘XX’ + s + ‘XY’
    If the next character is ‘B’, then the query returns | s | + 1. If it is ‘X’ then | s | + 2 is returned. If it is ‘Y’, then | s | is returned. Then just get the last letter with two queries similarlly to the first letter

    This works in N+2 queries and it is enough to get 100 points

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Sorry , misunderstanding was my bed.

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

      I actually have another solution very similar to Diegogrc's.

      Similarly to his solution, define s and the prefix of S we know so far, and assume A is the first character in the string. Also, the first letter can be obtain in two queries as described in that solution.

      We will look at two consecutive indices at a time, appending onto s. In order to maintain 2 queries per 2 indices, we will split the cases into two groups as follows:

      Group 1: sXB, sXX, sYY Group 2: sYB, sYX, sXY

      First, append all elements of Group 1 together to make sXBsXXsYY. If we query and get |s| as the return value, we know that neither X or Y can be appended to s, therefore we know that B must come after s. In this case, we just move on to the next index. The cost for this case is 1 query per 1 index.

      On the other hand, if we have |s| + 2 as the return value, then we query for the string sXX. If we get |s|, then YY must be appended to s. If we get |s| + 1, then XB must be appended to s. If we get |s| + 2, then XX must be appended to s. We can then jump two indices to the right. Notice that we only used two queries per two indices for this case (one to determine that there is an answer within this group, and one to determine which of the ones in this group is the right answer).

      The other case is when we have |s| + 1 initially. We know that the first letter after s must be either X or Y, but the second letter after s makes the answer not within the first group. Therefore, our answer is contained in the second group. We use a similar method of determining the correct answer in the second group as in the previous case (|s| + 2). We also spend two queries per two indices.

      Since we spend two queries every two indices (or one query every index, as in the first case we described) and risk overshooting N-1 by one, the worst case number of queries is N. We also need 2 queries for finding the first element. Therefore, the solution runs in N+2 queries.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      For A, couldn't you just build the known prefix by trying out all characters from {A, B, X, Y} for the next unknown position? The score if it matches will be 1 + length of known prefix. Number of queries will be 4n, which since n = 2000 and max queries is 8000 will just fit.

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

        You need to find a solution with <= n + 2 queries to get 100 points

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

          In hindsight, I should have realized such a simple solution would never have been expected at the IOI.

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

IOI 2018 day 2 live streaming

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

The scoreboard is updated with day 2 tasks!

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

    What wonderful news! I am literally quivering with anticipation!

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

How much participants will have a medal ?

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

Can somebody make a graph "CF rating vs IOI score"? And the same graph for only blue+, violet+, orange+.

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

How to solve meeting and highway?

Hint for dolls
→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +10 Vote: I do not like it
    90 pts for highway
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      90 pts with 51 queries

      I might have squeezed this solution to 50 queries on Yandex with some randomization and pruning, but I'm not sure as the scoring is broken.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Spoiler
        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I described my solution to meeting point on the day 2 blog. If someone has a simpler solution, I'd love to hear it.

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

congratulations Benq for winning IOI 2018!

→ Reply