Soon The 2016 Topcoder Open Algorithm competition will kick off with qualification round 1A.
The top 750 contestants from this round will advance directly to round 2, while other contestants can have another shot at round 1B and round 1C.
As per topcoder tradition, the top 250 active members who have the highest algorithm rating received an automatic berth into round 2.
You can check your handle in the list of the automatic berth here!.
I̶ ̶s̶u̶p̶p̶o̶s̶e̶ ̶t̶h̶o̶s̶e̶ ̶w̶h̶o̶ ̶r̶e̶c̶e̶i̶v̶e̶d̶ ̶t̶h̶e̶ ̶a̶u̶t̶o̶m̶a̶t̶i̶c̶ ̶b̶e̶r̶t̶h̶ ̶c̶a̶n̶ ̶s̶t̶i̶l̶l̶ ̶c̶o̶m̶p̶e̶t̶e̶ ̶i̶n̶ ̶t̶h̶e̶ ̶q̶u̶a̶l̶i̶f̶i̶c̶a̶t̶i̶o̶n̶s̶ ̶i̶n̶ ̶a̶ ̶p̶a̶r̶a̶l̶l̶e̶l̶ ̶r̶o̶u̶n̶d̶.
EDIT: Seems like there were usually no parallel rounds for first qualification rounds, let's hope there will be this year.
You can find the full tournament schedule here.
Good luck all!
At least for last several years there were no parallel round for first rounds
Just curious, what is the criteria for being active?
As mentioned here, active contestant is one meeting all the following criteria
God damn, the only TC SRM I've participated in 2016 was unrated :)
But you get to compete now, so is it really a loss :) ?
Yes, being on the berth list is awesome :))
What I'm curious about is the last condition; I'm from Iran and as far as I know, I'm not eligible to participate in marathons and tournaments. Maybe we became eligible in 2016 (as a consequence of nuclear negotiations) !?
I think Iran residents were eligible for TCO for some time now, just not for money prizes
Will the qualification round be rated?
yes
io10436
I solved the medium in practice room using binary search.
In the binary search, for a given test value of D, I greedily search for pairs of adjacent items in the sorted array such that S[i+1]-S[i] <= D.
Works beautifully but I cannot prove to myself why this greedy choosing of pairs works. Can anyone help me with a proof?
Here is my code http://www.textsnip.com/a9854p but I don't think it's anything unusual, many people seem to have written this. Thanks!
Assume that in an optimal solution some non-adjacent items are paired. However, this solution can be converted into a solution where only adjacent items are paired and the number of pairs remains the same.
For example, if the array is [a,b,c,d] and (a,c) and (b,d) are paired, you can convert this into a solution where (a,b) and (c,d) are paired. There are some more cases like this, you can check that everything works.
Hmmm m m all right, that's sort of the reasoning I did for myself but what I am looking for here is some sort of rigorous proof.
Also your explanation only covers non-adjacent items. I am also interested in why we can always be sure that the greedy left-to-right scan of the sorted list will work, i.e., how can we be sure that if the list is [a,b,c,d,e,....] and we pick (a,b) and (c,d) versus the pair (b,c) and (d,e), how do we know that decision will not mess us up further down the list?
My brain isn't able to connect all the dots.
But thanks, of course.
If you have some set of adjacent pairs, you can move the first pair as left as possible, then the second pair as left as possible etc. So if you have pairs (b,c) and (d,e), you can convert this to (a,b) and (d,e).
You can write a rigorous proof using this idea, if you go through all possible cases (I think there are not so many cases).
Hi, is it possible to find results of this round? I can't find any =(
Click
Click here also :D