TsunamiNoLetGo's blog

Topcoder open 2016 kicking off!
By TsunamiNoLetGo, history, 9 years ago, In English

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!

  • Vote: I like it
  • +61
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

At least for last several years there were no parallel round for first rounds

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just curious, what is the criteria for being active?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As mentioned here, active contestant is one meeting all the following criteria

    • Competed in at least one rated topcoder SRM in 2016.
    • Competed in a total of at least three (3) rated topcoder Algorithm events as a member at any time.
    • Meet all other Algorithm Competition and Tournament eligibility criteria
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +52 Vote: I do not like it

      God damn, the only TC SRM I've participated in 2016 was unrated :)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +17 Vote: I do not like it

        But you get to compete now, so is it really a loss :) ?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          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) !?

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think Iran residents were eligible for TCO for some time now, just not for money prizes

            → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the qualification round be rated?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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).

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, is it possible to find results of this round? I can't find any =(

→ Reply