Are there IOI 2014 tasks somewhere on the internet or someone can upload them?
Thanks in advance.
Are there IOI 2014 tasks somewhere on the internet or someone can upload them?
Thanks in advance.
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 155 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | BledDest | 145 |
Name |
---|
Here: IOI Tasks
Thanks.
I've an algorithmic solution to both Game and Rail.
game — O(n^2) time and space rail — O(nlogn) with 2n-3 calls to the function
I'm pretty proud of myself for solving those questions, too bad I didn't qualify to my national team :/
Where are u from?
Could you please provide me the details of your solution to Rail? I can use no more than 3N-5 queries (or something like that) and I really would like to know if it can be done in an even more optimal way ;)
I have two distance ararys, one is sorted by distance from station 0 to the other stations, the second is a sorted by index from the closest station to station 0, let's call it station i(which is D type of cours).
in total 2n-3 quries(because d(a,b)=d(b,a)).
d(a,b) — the distance as they define it
D(a,b) — the number of blocks from a to b.
now for every station j which is not 0 or i:
if d(j,i)<d(j,0) than j is a C type to the left of station 0, D(j,0)=d(0,j)-d(0,i)
if d(j,i)<d(0,i) than j is a C type to the right of station 0, D(j,0)=d(0,i)-d(j,i)
if d(0,j)<d(i,j) than j is a D type to the right of station 0, D(0,j)=d(0,j)
there might be a factor of +1/+2/-1/-2 in the caculation of D.
the lower bound might be a little bit lower(because we know that the most left and most right stations are C type and D type respectivly)
This does not work without additional queries.
For example, in your first case, consider the following situation:
the distance from station 3 to station 1 is way smaller than the distance from station 3 to station 0, but this does not mean that station 3 is a type-C to the left of station 0.
if d(j,i)<d(j,0), then it could be of type C and be between station 0 and station i. It could also be of type D and be left from station 0, so how do you know the case?
if d(j,i)<d(0,i), then it could be of type C to the right of station 0, however if it is right from station i then this doesn't hold.
if d(0,j)<d(i,j), then it could also be some C to the right of station i.
Also, I don't see you mentioning anything about type D to the left of station 0?
I just can't seem to get your idea, I did participate in the IOI myself (256 points) and this problem was quite tough, even though the author solution seemed to be just a lot of cases.
nvm
"If we apply an operation to a node whose children don’t have the same value then we apply this operation to each of its 2 children, and update the value of the node."
I don't understand something.
Let's say N=500000. In 250000 queries we can make a wall in which every other height is equal to 100000, that is, (0,100000,0,100000,0,100000,...,0,100000). Then we make 100000 max-queries acting on all columns and successively increasing height (first query makes maximum with all columns and 1, then 2, 3 and so on). Won't your algorithm give then O(n) time per query?
Indeed, a bug in my solution, if we just change the given interval's node minimum/maximum value and keep this in mind when traversing the tree the bug should be fixed.
Looks like problem B can be solved simply by an interval tree. But I don't know the exact time limit.
The problem B is solved by an interval tree. I think the exact time limit is 3 seconds.
Where score board????
Here: http://live.ioi2014.org/Ranking.html
EDIT: Sorry, didn't see someone had posted a solution blog