whipppedcream's blog

By whipppedcream, history, 6 years ago,

Right now IOI 2016 is in progress. I'm sure a lot of you guys will be watching, so this post was created to let you guys talk about the scores and the scoreboard in the comments :) The link to the scoreboard is here.

• +42

 » 6 years ago, # |   +10 Bolivia is in the top Scoreboard for the first time in history! I have great expectations for this year! GO BOLIVIA!
 » 6 years ago, # |   +5 Day 1 is over, and a lot of contestants have fully solved Task 1. What are your thoughts on the problems (and maybe your approaches)?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +30 I think this solves 1: Sorter the input Take the k smallest elements, such that their sum is less than l, but if you took k+1 it would be larger than u. (If you can't do that, the problem is either easy: a sum lands inside the interval; or impossible: the total element sum is smaller than l) One by one, change one of the k elements for one of the k largest elements. When you change an element, the sum can never increase by more than w_max - w_min <= u - l, so there is no risk of 'jumping' over the [l, u] interval.If the sum of the largest k is still smaller than l, then there is no solution, because the next subset in order of sum is the k+1 smallest elements, which we know is too large.This solution should take time equal to sorting, which should be fine for n = 200,000.I thought it was a fun problem :-)
•  » » » 6 years ago, # ^ |   -20 your answer in good but there is a better one that is very similar instead of sorting, just take the first k elements that the sum of the first k is smaller then l and the sum of the first k+1 is higher then u. then we can use the same trick that you did for k and k+1 (if there is a solution then thre is a solution that uses k elements or k+1 elements)
•  » » » 6 years ago, # ^ |   0 You could also easily use two pointer on tge sorted array?
•  » » » » 6 years ago, # ^ |   0 Yes, I think that's a nice way to accomplish the third step.
 » 6 years ago, # |   -6 3 from China ,2 form Russia in top 5 . but how??
 » 6 years ago, # |   0 When are day 2 problems coming out?
•  » » 6 years ago, # ^ |   +18 When day 2 comes.
•  » » » 6 years ago, # ^ |   +7 Oh, I thought today was day 2. Anyways, just a little question: how difficult are the IOI problems usually? From my point of view the first problem from day 1 would be around div1. A/B. What do you guys think?
•  » » » » 6 years ago, # ^ |   +4 problem 2 and 3 are much harder than Div1 A and B. a lot of those participants are red or orange and they all solve Div1 A and B easily in CF rounds of normal difficulty. but only 4 solved 2nd problem and just 1 solved the third (solved == 100 points)
•  » » » » 6 years ago, # ^ |   +5 Its hard and possibly impossible to compare IOI problems with CF problems due to the completely different style and format. The first problem was easy, but the other 2 were very difficult.