I_love_tigersugar's blog

IOI 2016 review

By I_love_tigersugar, history, 8 years ago, In English

UPDATE:

Official result of IOI 2016 has been published here: http://stats.ioinformatics.org/results/2016

The closing ceremony of IOI will start on 16:00 MSK. Online stream is available here: https://www.youtube.com/watch?v=BAkcby2xEwQ

Hey guys!

Hello all IOI 2016 participants!

IOI 2016 has eventually started. It's my big sadness that I can not take part in IOI this year. I am too old to do that :((

How is everything now in Kazan? I guess that Russian girls are all cute and beautiful, right? Can you share with me your feelings, funny stories and photos inside this post? I really want to hear from you, even when I feel jealous with you.

Anyway, congratulations for being here. You are all the best. Wish you sweet, amazing and memorable moments at IOI. Best luck in the contest and hope you will get high ratings. (just kidding :D)

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

Comments Comments (68)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).

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

A few things from the gift pack thing... My favorites are the 3 pairs of socks :D

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

Yeah, Kazan is beatiful! I think IOI16 should be good enough for participants, because many people in Kazan interested to make contest better.

P.S. I'm living in Kazan :DDD If you don't like excursions, you may write me for a walkthrough the historic center and a discussing the last PrinceOfPersia contest :D

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

Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).

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

Is there a live stream for the contest? I_love_tigersugar If you have an update, please post it here.

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

Day 1 and 2 problems. Courtesy jonathanirvings via twitter.

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

Weird. I think third subtask to railroad is really hard, but when you know how to solve it fourth subtask becomes obvious. But so far there are 10 people with accepted on third subtask, but 0 with AC na fourth which is supicious for me. Is test data weak? I guess we will have to wait for opinions of people who got third subtask accepted.

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

    There is still something between 3rd and 4th parts, although I agree that this is much easier than solving 3rd.

    I guess maybe there are some greedy can pass 3rd, or some simple conditions.

    Anyway it is an elegant task.

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

      It is possible to pass the 3rd with a greedy algorithm : iterate over all segments sorted by min entry speed, and greedily assign the next segment available with the lowest exit speed, without creating a cycle.

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

        Why this solution correct?

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

        How your algorithm work with this case?

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

      (I came up with this on the bus, unfortunately)

      Code for Railroad

      My solution in contest which passed subtask 3 but not 1, 2, or 4 is actually incorrect and fails the following test case: (along with at least three others who solved Subtask 3)

      5
2 11
8 3
7 4
10 5
9 6

      I guess IOI has weak test data as usual :/

      EDIT: Sorry about that, I think that might not have been the test case. Try this:

      5
2 11
8 3
4 7
10 5
6 9
      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Do you mind sharing your solution? I tried really hard but didnt come up witha anything.

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

      Define the flux[i] as (number of times we go from i to i+1) — (number of times we go from i+1 to i). (So if we go from 1 to 3, then we do flux[1] ++, flux[2] ++, and if we go from 4 to 3 we do flux[3] --.)

      The result (speed for t = 0, 1, 2, ...) is a path, and we can extend that path without cost to a path from 0 to 10^9. That means in the end we will get for each i: flux[i] = 1.

      We calculate flux by the given edges. For each i:

      • If flux[i] < 1, then we can add edges from i to i+1 without cost (and we will do it).
      • If flux[i] = 1, do nothing.
      • If flux[i] > 1, then we must add edges from i+1 to i with cost: we need at least (flux[i] — 1) of them.

      After that maybe there is still no solution because the given edges are not connected. Then we need to pay some costs to connect them -- this is exactly the MST problem.

      Why after that there is a solution? There exist a Eulerian path.

      See details in my code (without discretization).

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

        Wow, that solution is amazing. I'm quite surprised people came up with it. Rhe only thing I can't seem to comprehend is the MST part — with the way you build the edges wouldnt you end up taking them all always?

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

          Suppose the input is (1, 10) and (6, 2). Then we have to take one out of 2->1 and 10->6 (we should take the first one since it is shorter).

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

            Ook so I waited about a year so that I could try the problem again and hopefully be smarter and solve it. It wasn't the case. This time, though, I actually thought about it in about the same way (looking for an eulerian path in that graph). My huge problem is, and here is the part where I ask for help, for a given eulerian path in this graph, how can you be sure that you take a section all at once? Let's say we have some section with (2, 5) and we have edges from 2 to 3, from 3 to 4, from 4 to 5. The problem is that when we choose some random path, we need to have these 3 edges one immediately after another (we can't divide the section). Another problem would be related to the connected components that you mentioned: on that case we have edges 1->2, 2->3, ..., 9->10, 6->5, 5->4, .., 3->2 which sounds pretty connex to me. Could you, please, shed some light on these issues? I tried to read the official solution, too. There, they use just one edge to link s with t and they treat it the same as if it were more than one (and considering it as more edges together would lead to the same problem that I mentioned).

            I know that the comment is rather old, but I'd be grateful if you could explain it a little more thoroughly. Maybe it'd help others as well

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

          It might easier to see the components if you think about the paths as single edges. In order to ensure Eulerian path, in degree must equal out degree and graph must be connected. First we fix edge degrees (by adding edges of the form i → i + 1 and i → i - 1) and then we connect graph.

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

    I think you can do something like this for part 3:

    1) Take the graph of 0 price edges (represented implicitly, so it doesn't get large).

    2) For any pair of vertices, if they have edges going in both directions contract them (uf?). If not, the edge between them must be in the final solution.

    At each step you either get rid of a vertex or find an edge for the final path of length n. Hence it should be something like linear time.

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

Can someone drop me a hint about first task? I thought about some sort of greedy solution but can't prove it. Thanks!

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

    Sort and calculate prefix sums, then

    Iterate over k — number of elements to use, and get minimal and maximal sum you can get. say a and b

    • if a or b in [l, r] then you can get the result (trivial),
    • if b < l or a > r you can't (trivial),
    • but if a < l and r < b then you can because of super condition (not trivial, but left as exercise)
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Yep, that's exactly what I thought, couldn't have the formal proof but will think bout it, thanks :)

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it +9 Vote: I do not like it
        Don't read until you've solved or given up
        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is it possible to use ternary search for the first task?

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

    I just guessed the solution randomly.

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

      Wow!

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

      Why contiguous?

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

        Consider it like this. Let us take 3 numbers {x}1, {x}2, {x}3. Let us assume that they are in sorted order and the answer to the question is not a continuous sequence. Thus we can say that {x}1 + {x}3 satisfies the solution i.e {l} <  = {x}1 + {x}3 <  = {u}.

        We need to show that no other continuous sequence also satisfies the equation. Thus neither of these two equation does not hold {l} <  = {x}1 + {x}2 <  = {u} and {l} <  = {x}2 + {x}3 <  = {u}.

        From the assumption {l} <  = {x}1 + {x}3 <  = {u}, it implies that there 2 relations can be inferred as the numbers are already sorted.

        {l} <  = {x}2 + {x}3 and {x}1 + {x}2 <  = {u}.

        Let us assume to the contrary that none of these two equations {l} <  = {x}1 + {x}2 and {x}2 + {x}3 <  = {u} does not hold.

        Thus it means {x}2 + {x}3 > {u} and {x}1 + {x}2 < {l}.

        But according to the equation, {u} - {l} >  = max({x}1, {x}2, {x}3) - min({x}1, {x}2, {x}3) i.e. {u} - {l} >  = {x}3 - {x}1.

        This reduces to {u} >  = {l} + {x}3 - {x}1, which along with the assumption gives

        {x}2 + {x}3 >  = {l} + {x}3 - {x}1, which reduces to {x}2 + {x}1 >  = {l}, leading to a contradiction.

        Thus either {x}1 + {x}2 or {x}2 + {x}3 or both of them also satify the equation.

        Using Principal of mathematical induction, we can extend this idea to {n} variables and prove the overall result.

        For checking whether any continuous subarray (after sorting) has sum in the range of {l} to {u} can be done using bit and coordinate compression.

        But the question asks us to find the indices of the numbers as well. Can anyone give some insight on this?

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

          Did you mean the second term in this inequation (x1 + x3) + (x2 — x3) < l is (x2-x3)?. If so, l-(x2-x3) must be larger than l, and it is not certain that x1 + x3 < l.

          By the way, where did you use (u — l) >= (x3 — x1)?

          I'm sorry if I misunderstand your proof. I'm also trying to proof the algorithm.

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

            Sorry had misunderstood the problem, Proper proof added now.

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

            We claim that we can just look at continuous subarrays.

            Look at k consecutive numbers.

            Case 1. Sum of first k numbers is in [l, u] We are done.

            Case 2. Sum of last k numbers is in [l, u] We are done.

            Case 3. Sum of first k number is more than u No array with length k.

            Case 4. Sum of less k number is less than l No array with length k

            Case 5. Sum of first k number is less than l, and sum of first k numbers is more than u.

            So we have x1 + x2 + ... + xk < l, and xn + xn - 1 + ... + xn - k + 1 > u.

            Now we "push" the subarray to the right, we add xi + k - xi to the sum. Clearly this is no more than u - l.

            Therefore, as our sum goes from less than l to more than u, we must reach [l, u] at least once. (Think about it in a similar way to Intermediate Value Theorem)

            So we can just look at continuous subarrays.

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

          Instead of actually sorting the array, you can sort the indices of the elements.

          #include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 200000;
int n,a[maxn],id[maxn];
bool cmp(int x,int y)
{
  return a[x]<a[y];
}
int main()
{
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i=0; i<n; i++)
  {
     cin >> a[i];
     id[i]=i;
  }
  sort(id,id+n,cmp);
  for (int i=0; i<n; i++)
    cout << id[i] << ' ';
  return 0;
}
          → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Really? You and random? c'mon...

      → Reply
»
8 years ago, # |
  Vote: I like it +100 Vote: I do not like it
I guess that Russian girls are all cute and beautiful, right?

Asking the right questions..

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

OK, so how to solve shortcut problem without tons of cases and whole page of notes filled with inequalities?

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

    I will try to retake this thread. First I would like to see the solution with tons of cases, I came up with a lot, but got no efficient solution. The solution I found at the end runs in n·log2(n), and uses that the function required to evaluate in the problem is indeed a convex function. Although I don't really know if that works for the strongest test cases... Is anybody willing to discuss it? (I'm a bit lazy to write it up if nobody does...)

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

Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).

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

Why did many people get 30 points on problem 2 yesterday? The first 2 subtasks were too easy DP-bitmask, weren't they? I think they have wasted many luxurious points :(

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

    I did not think of O(n^2 2^n) bitmask DP during the contests, I only saw O(n!) brute force. Besides, for contestants time is luxurious also and I spent too much time working on the full solution to problem 2.

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

      What a pity :( I think a good strategy is coding easy subtasks before thinking about the hard one. Easy subtasks usually need short codes. It avoids wasting points. Spending time on solving hard subtasks first can let us be lack of time for easy one.

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

Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).

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

Live stream link

It's the CCTV footage of the contest hall.

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

jcvb is really strong :o

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

Guys, what do those 3 pointers at the right corner of the rankings list at the left stay? Are they telling us about gold, silver, bronze limits?

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

How to solve second problem from second day for full score?

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

    For n positions, let's try to find out what the first n/2 positions permute to. We could send n/2 subsets with 1 bit set in each of them, but then we wouldn't be able to send any more subsets with exactly 1 bit set (otherwise we wouldn't be able to tell them apart). Instead, let's send n/2 subsets with exactly 1 bit not set (exactly n/2-1 n-1 bits set).

    Now we repeat: for each group of n/2 positions, we send n/4 subsets with exactly n/4-1 n/2-1 bits set. etc. etc.

    (disclaimer I didn't compete and haven't actually submitted this)

    Okay I submitted it to yandex mirror and it got AC. Code: http://hastebin.com/udecimixug.cpp

    s = start, e = end, m = middle, p = current string we're adding or querying, v = current set of indices (ie indices which [s, e) maps to), x = left indices (ie indices which [s, m) maps to), y = right indices (ie indices which [m, e) maps to).

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

How to solve aliens(at least for 60 points)?

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

Key fact in solving aliens for 100 pts is that function f(k) that gives answer given k as argument is convex. In other words that f(k - 1) + f(k + 1) > 2f(k). Does anyone have an idea how to prove it? It looks like it is true, but unprovable at the same time.

Btw assuming this you can solve it so that you set some magic constant x and then pay x for every new photo and by binary search find x so that optimal answer consists of taking k photos (using some approach used for getting 60 pts).

UPD: http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/sdarticle_204.pdf Proposition 7 ( ͡° ͜ʖ ͡°)( ͡° ͜ʖ ͡°) IOI at its best. Organizers were probably thinking something like "Uh, it's an informatics olympiad, not a math one, who needs any proofs? It's working, so it's working, end of topic!"

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

    This is not exactly proof, but explains convexity a bit.

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

      That's exactly why I said it looks both true and unprovable...

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

    I implemented exactly the same thing but I got wrong answer. I thought the idea is wrong... :(

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

      Just changed 60pt code to long double and added a binary search constant x for every new photo, got only 4pt

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

        Well I found out my bug, i had a global N which was n in the function, but i changed n to remove unnecessary cells, and didn't change global N (which I moved my bineary search to a function). Missed top 5 forever...

        :(

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

But where is Ukraine...

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

Does anyone know if there is a live stream of the closing ceremony? Or is it live on some TV channel?

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

Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).

→ Reply