### Resul's blog

By Resul, history, 5 years ago,

Hi there!
Is there going to be online-mirrors of Day 1 and Day 2?

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/

• +140

 » 5 years ago, # | ← Rev. 2 →   0 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
 » 5 years ago, # |   +65 Mirror will be held on Yandex.Contest platform, link will be available on ioi website, contest.yandex.com/ioi, codeforces and more
 » 5 years ago, # | ← Rev. 4 →   +12 day 1 result
•  » » 5 years ago, # ^ |   -13 which problems are these?
 » 5 years ago, # |   0 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).
•  » » 5 years ago, # ^ |   +28 It will be an open virtual contest — start whenever convenient
•  » » » 5 years ago, # ^ |   +6 Oh. That's good, then. I'm too used to fixed times...
 » 5 years ago, # |   +3 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?
•  » » 5 years ago, # ^ |   +15 We'll try to keep things just as on IOI
 » 5 years ago, # |   0 I solved the first problem (detecting..) at o(nlogn) is there a solution at o(n)?
•  » » 5 years ago, # ^ |   0 You can use two pointers to achieve O(N)
•  » » » 5 years ago, # ^ | ← Rev. 4 →   0 But, do not u need a sorted array?
•  » » » » 5 years ago, # ^ |   -10 i found an easy solution in o(N) time that uses only k smollest number algorithm and no sort
•  » » » » » 5 years ago, # ^ |   0 It must be like this, right?
•  » » » » » » 5 years ago, # ^ |   -10 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
 » 5 years ago, # |   0 How to solve 2nd problems 3rd subtask?
•  » » 5 years ago, # ^ |   -67 no i am talking about the first problem, i wanted to know if the solution is o(n) time or o(nlogn) time
 » 5 years ago, # |   0 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++?
•  » » 5 years ago, # ^ |   +10 There is a download button in the upper right corner near "Jury messages" button. There you can find templates for different languages including C++.
•  » » » 5 years ago, # ^ |   0 Thanks
 » 5 years ago, # |   +8 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +51 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 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 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.