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)
Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).
A few things from the gift pack thing... My favorites are the 3 pairs of socks :D
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
Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).
Is there a live stream for the contest? I_love_tigersugar If you have an update, please post it here.
No. I don't think there is a live strean. Previous IOI didn't have live stream, right?
2014 did and it was pretty great.
Day 1 and 2 problems. Courtesy jonathanirvings via twitter.
Day 2 problems uploaded.
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.
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.
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.
Why this solution correct?
How your algorithm work with this case?
(I came up with this on the bus, unfortunately)
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)
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:
Do you mind sharing your solution? I tried really hard but didnt come up witha anything.
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:
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).
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?
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).
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
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.
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.Can someone drop me a hint about first task? I thought about some sort of greedy solution but can't prove it. Thanks!
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
Yep, that's exactly what I thought, couldn't have the formal proof but will think bout it, thanks :)
Use continuous subarrays
Is it possible to use ternary search for the first task?
I just guessed the solution randomly.
Sort the array, answer is a continuous subarray.
Wow!
Why contiguous?
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?
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.
Sorry had misunderstood the problem, Proper proof added now.
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.
Instead of actually sorting the array, you can sort the indices of the elements.
Really? You and random? c'mon...
Asking the right questions..
Yeah. That's one thing I pay much attention to, and make my sadness of not coming to IOI more terrible :'(
i feel ya :(
OK, so how to solve shortcut problem without tons of cases and whole page of notes filled with inequalities?
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...)
Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).
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 :(
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.
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.
Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).
Live stream link
It's the CCTV footage of the contest hall.
jcvb is really strong :o
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?
The ones on right denote medal limits, yeah.
How to solve second problem from second day for full score?
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-1n-1 bits set).Now we repeat: for each group of n/2 positions, we send n/4 subsets with exactly
n/4-1n/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).
Thanks :)
How to solve aliens(at least for 60 points)?
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.
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!"
This is not exactly proof, but explains convexity a bit.
That's exactly why I said it looks both true and unprovable...
I implemented exactly the same thing but I got wrong answer. I thought the idea is wrong... :(
Just changed 60pt code to long double and added a binary search constant x for every new photo, got only 4pt
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...
:(
But where is Ukraine...
Does anyone know if there is a live stream of the closing ceremony? Or is it live on some TV channel?
The opening ceremony was lived on UNIVER, so I think the closing ceremony will be lived there.
What time would it start?
It will start at this time
By the way, there is a live stream on IOI 2016 facebook page
Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).