whipppedcream's blog

IOI 2016 Scoreboard Discussion
By whipppedcream, history, 8 years ago, In English

Right now IOI 2016 is in progress. I'm sure a lot of you guys will be watching, so this post was created to let you guys talk about the scores and the scoreboard in the comments :) The link to the scoreboard is here.

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

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

Bolivia is in the top Scoreboard for the first time in history! I have great expectations for this year! GO BOLIVIA!

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

Day 1 is over, and a lot of contestants have fully solved Task 1. What are your thoughts on the problems (and maybe your approaches)?

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

    I think this solves 1:

    • Sorter the input
    • Take the k smallest elements, such that their sum is less than l, but if you took k+1 it would be larger than u. (If you can't do that, the problem is either easy: a sum lands inside the interval; or impossible: the total element sum is smaller than l)
    • One by one, change one of the k elements for one of the k largest elements.

    When you change an element, the sum can never increase by more than w_max - w_min <= u - l, so there is no risk of 'jumping' over the [l, u] interval.

    If the sum of the largest k is still smaller than l, then there is no solution, because the next subset in order of sum is the k+1 smallest elements, which we know is too large.

    This solution should take time equal to sorting, which should be fine for n = 200,000.

    I thought it was a fun problem :-)

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

      your answer in good but there is a better one that is very similar instead of sorting, just take the first k elements that the sum of the first k is smaller then l and the sum of the first k+1 is higher then u. then we can use the same trick that you did for k and k+1 (if there is a solution then thre is a solution that uses k elements or k+1 elements)

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

      You could also easily use two pointer on tge sorted array?

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

        Yes, I think that's a nice way to accomplish the third step.

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

3 from China ,2 form Russia in top 5 . but how??

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

When are day 2 problems coming out?

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

    When day 2 comes.

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

      Oh, I thought today was day 2. Anyways, just a little question: how difficult are the IOI problems usually? From my point of view the first problem from day 1 would be around div1. A/B. What do you guys think?

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

        problem 2 and 3 are much harder than Div1 A and B. a lot of those participants are red or orange and they all solve Div1 A and B easily in CF rounds of normal difficulty. but only 4 solved 2nd problem and just 1 solved the third (solved == 100 points)

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

        Its hard and possibly impossible to compare IOI problems with CF problems due to the completely different style and format. The first problem was easy, but the other 2 were very difficult.

        → Reply