Resul's blog

IOI 2016 Online-Mirror
By Resul, history, 8 years ago, In English

Hi there!
Is there going to be online-mirrors of Day 1 and Day 2?
Someone have info about this?

UPD: First online-version of IOI 2016 Day 1 will start on August 14, at 10:00 on https://contest.yandex.com/ioi/
UPD: Second online-version of IOI 2016 Day 2 will start on August 16, at 10:00 on https://contest.yandex.com/ioi/

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

Comments Comments (21)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

As a beginner, online-mirror will not be very important for me, but my humble question is will IOI has online standing ?
thanks a lot and sorry for this annoying question.
EDIT: sorry I got it now, just ignore this comment

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

Mirror will be held on Yandex.Contest platform, link will be available on ioi website, contest.yandex.com/ioi, codeforces and more

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

day 1 result

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

Damnit, why so early. It also coincides with opening of the last problem of the current HR contest (which is the only one where time matters now).

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

    It will be an open virtual contest — start whenever convenient

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

      Oh. That's good, then. I'm too used to fixed times...

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

Will I get full feedback when I submit problem, or I must wait till end? I mean how many points I got for every subtask?

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

I solved the first problem (detecting..) at o(nlogn) is there a solution at o(n)?

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

    You can use two pointers to achieve O(N)

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

      But, do not u need a sorted array?

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

        i found an easy solution in o(N) time that uses only k smollest number algorithm and no sort

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

          It must be like this, right?

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

            it is the same but i didnt sort the array i took the first k numbers that ths sum of the first k is smaller then l and then sum of the first k+1 are larger then u the i took the smallest k and highest k and did the same as him and i also did the same thing with k+1

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

How to solve 2nd problems 3rd subtask?

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

    no i am talking about the first problem, i wanted to know if the solution is o(n) time or o(nlogn) time

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

Did anybody submit successfully? I'm doing the contest now, getting CE with C++, it's saying that the function they're looking for in unidentified, although I followed their template for C (they don't have one for C++), should the function look differently for c++?

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

    There is a download button in the upper right corner near "Jury messages" button. There you can find templates for different languages including C++.

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

Does anybody know full solution (or something worthy of score over 71) for the last problem? I participated onsite and 71 is all I could get with . cgy4ever explained a really cool solution for problem 2 in another blog, but I haven't seen anything about problem 3.

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

    I haven't coded this but i think it should get 100. Label the nodes 1..N on the main line and 1'...N' attached to them, x[i] be the distance from 1 to i and l[i] be the distance from i to i'. Bsearch the answer, suppose the answer is <= t. Let u[i] = l[i]-x[i], v[i] = l[i]+x[i]. Let x1 < x2 be the "x-coordinate" (analogous to x[i]s) that we will add the extra edge between. Then for any i<j with u[i]+v[j] > t we need to have |x[i]-x1| + |x[j]-x2| + c + l[i] + l[j] <= t. This can be expanded into 4 different ineqs.

    (x1+x2) — x[i] — x[j] + l[i] + l[j] + c <= t (1)

    (-x1-x2) + x[i] + x[j] + l[i] + l[j] + c <= t (2)

    (x1-x2) — x[i] + x[j] + l[i] + l[j] + c <= t (3)

    (-x1+x2) + x[i] — x[j] + l[i] + l[j] + c <= t (4)

    Note that inequalities (1) and (2) can be considered for all pairs i,j with u[i]+v[j]>t (not necessarily just i<j) without changing the system. Also (3) is tightest when i', j' are the diameter of the original graph so that can be precompd outside the bsearch. With some O(nlgn) precomp we can calculate max(-x[i]-x[j]+l[i]+l[j]) and max(x[i]+x[j]+l[i]+l[j]) over all u[i]+v[j] > t in O(n). We now have the tightest inequalities on (1),(2),(3) and we can now iterate through x1 and keep the interval of valid (satisfying 1,2,3) x2's using two pointers. We take the x1,x2 with minimum -x1+x2 as if anything satisfies the (4) ineqs then so will this one. Then check this answer by calculating the diameter for the resultant graph (possible due to special form) in O(n) to implicitly check all the inequalities of form (4). O(nlgAns + nlgn) overall, perhaps there's a simpler soln though.

    → Reply