### prof.PVH's blog

By prof.PVH, history, 3 years ago, ,

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)

• +218

 » 3 years ago, # |   0 Auto comment: topic has been updated by skyvn97 (previous revision, new revision, compare).
 » 3 years ago, # |   +28 A few things from the gift pack thing... My favorites are the 3 pairs of socks :D
 » 3 years ago, # | ← Rev. 2 →   +42 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 amd contest :D
 » 3 years ago, # |   -26 Thánh sống ảo trở lại Phạm Văn Hạnh
 » 3 years ago, # |   0 Auto comment: topic has been updated by skyvn97 (previous revision, new revision, compare).
 » 3 years ago, # |   -9 Is there a live stream for the contest? skyvn97 If you have an update, please post it here.
•  » » 3 years ago, # ^ |   +6 No. I don't think there is a live strean. Previous IOI didn't have live stream, right?
•  » » » 3 years ago, # ^ |   +22 2014 did and it was pretty great.
 » 3 years ago, # | ← Rev. 2 →   +37 Day 1 and 2 problems. Courtesy jonathanirvings via twitter.
•  » » 3 years ago, # ^ |   +28 Day 2 problems uploaded.
 » 3 years ago, # |   +16 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.
•  » » 3 years ago, # ^ |   +26 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.
•  » » » 3 years ago, # ^ |   -22 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.
•  » » » » 3 years ago, # ^ |   +5 Why this solution correct?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +15 How your algorithm work with this case? 4 1 1 2 4 4 10 6 3 
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +45 (I came up with this on the bus, unfortunately) Code for Railroad#include #include "railroad.h" using namespace std; typedef long long LL; #define x first #define y second LL par[210000]; int find(int a){ if(a == par[a]) return a; return par[a] = find(par[a]); } void join(int a, int b){ par[find(a)] = find(b); } vector > a, b; int n; LL ans = 0; LL plan_roller_coaster(vector s, vector t){ s.push_back(1100000000); t.push_back(0); n = s.size(); for(int i = 0; i < n; i++){ par[i] = i; b.push_back(make_pair(s[i],i)); a.push_back(make_pair(t[i],i)); } sort(a.begin(), a.end()); sort(b.begin(), b.end()); for(int i = 0; i < n; i++){ if(a[i].x > b[i].x){ ans += a[i].x - b[i].x; swap(a[i].x,b[i].x); } } vector > > edges; for(int i = 0; i < n; i++){ edges.push_back(make_pair(0LL,make_pair(a[i].y,b[i].y))); if(i + 1 < n){ edges.push_back(make_pair(max(0LL,a[i+1].x-b[i].x),make_pair(a[i+1].y,b[i].y))); } } sort(edges.begin(), edges.end()); for(int i = 0; i < edges.size(); i++){ if(find(edges[i].y.y) == find(edges[i].y.x)){ continue; } else { join(edges[i].y.y,edges[i].y.x); ans += edges[i].x; } } return ans; } 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 
•  » » 3 years ago, # ^ |   +31 Do you mind sharing your solution? I tried really hard but didnt come up witha anything.
•  » » » 3 years ago, # ^ |   +42 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).
•  » » » » 3 years ago, # ^ |   +10 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?
•  » » » » » 3 years ago, # ^ |   +5 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).
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 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
•  » » » » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   -8 Can someone drop me a hint about first task? I thought about some sort of greedy solution but can't prove it. Thanks!
•  » » 3 years ago, # ^ | ← Rev. 4 →   +19 Sort and calculate prefix sums, thenIterate 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)
•  » » » 3 years ago, # ^ |   +10 Yep, that's exactly what I thought, couldn't have the formal proof but will think bout it, thanks :)
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +9 Don't read until you've solved or given upUse continuous subarrays
•  » » » 3 years ago, # ^ |   0 Is it possible to use ternary search for the first task?
•  » » 3 years ago, # ^ |   +11 I just guessed the solution randomly. SolutionSort the array, answer is a continuous subarray.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 Wow!
•  » » » 3 years ago, # ^ |   0 Why contiguous?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   -15 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?
•  » » » » » 3 years ago, # ^ |   0 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.
•  » » » » » » 3 years ago, # ^ |   0 Sorry had misunderstood the problem, Proper proof added now.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +10 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 kCase 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.
•  » » » » » 3 years ago, # ^ |   0 Instead of actually sorting the array, you can sort the indices of the elements. #include #include using namespace std; const int maxn = 200000; int n,a[maxn],id[maxn]; bool cmp(int x,int y) { return a[x]> n; for (int i=0; i> a[i]; id[i]=i; } sort(id,id+n,cmp); for (int i=0; i
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Really? You and random? c'mon...
 » 3 years ago, # |   +100 I guess that Russian girls are all cute and beautiful, right?Asking the right questions..
•  » » 3 years ago, # ^ |   +10 Yeah. That's one thing I pay much attention to, and make my sadness of not coming to IOI more terrible :'(
•  » » » 3 years ago, # ^ |   +5 i feel ya :(
 » 3 years ago, # |   +35 OK, so how to solve shortcut problem without tons of cases and whole page of notes filled with inequalities?
•  » » 3 years ago, # ^ |   0 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...)
 » 3 years ago, # |   0 Auto comment: topic has been updated by skyvn97 (previous revision, new revision, compare).
 » 3 years ago, # |   +11 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 :(
•  » » 3 years ago, # ^ |   +11 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.
•  » » » 3 years ago, # ^ |   +8 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.
 » 3 years ago, # |   0 Auto comment: topic has been updated by skyvn97 (previous revision, new revision, compare).
 » 3 years ago, # |   0 Live stream linkIt's the CCTV footage of the contest hall.
 » 3 years ago, # | ← Rev. 2 →   +50 jcvb is really strong :o
 » 3 years ago, # |   0 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?
•  » » 3 years ago, # ^ |   +6 The ones on right denote medal limits, yeah.
 » 3 years ago, # |   +1 How to solve second problem from second day for full score?
•  » » 3 years ago, # ^ | ← Rev. 4 →   +13 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.cpps = 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).
•  » » » 3 years ago, # ^ |   0 Thanks :)
 » 3 years ago, # |   0 How to solve aliens(at least for 60 points)?
•  » » 3 years ago, # ^ |   +28 Put some numbers here http://codeforces.com/problemset/problem/321/E and that's all. http://main.edu.pl/en/archive/ceoi/2004/two is also the same problem. Alternatively you can use convex hull trick.
 » 3 years ago, # | ← Rev. 2 →   +5 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!"
•  » » 3 years ago, # ^ | ← Rev. 2 →   -7 This is not exactly proof, but explains convexity a bit.
•  » » » 3 years ago, # ^ |   0 That's exactly why I said it looks both true and unprovable...
•  » » 3 years ago, # ^ |   +11 I implemented exactly the same thing but I got wrong answer. I thought the idea is wrong... :(
•  » » » 3 years ago, # ^ |   +7 Just changed 60pt code to long double and added a binary search constant x for every new photo, got only 4pt
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +38 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...:(
•  » » » » » 3 years ago, # ^ |   +74
 » 3 years ago, # |   -17 But where is Ukraine...
 » 3 years ago, # |   0 Does anyone know if there is a live stream of the closing ceremony? Or is it live on some TV channel?
•  » » 3 years ago, # ^ |   0 The opening ceremony was lived on UNIVER, so I think the closing ceremony will be lived there.
•  » » » 3 years ago, # ^ |   0 What time would it start?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 It will start at this timeBy the way, there is a live stream on IOI 2016 facebook page
 » 3 years ago, # |   0 Auto comment: topic has been updated by skyvn97 (previous revision, new revision, compare).