Блог пользователя Killever

Автор Killever, 10 лет назад, По-английски

Just don't miss it
BTW it's the last chance to advance to next Stage & this is the last TCO round for me this year :)
See what time it starts in your area
http://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO14+Algorithm+Round+2C&iso=20140705T12&p1=98
Let us discuss problems here after the contest.
GL & HF

Теги tco
  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is everyone allowed to take part, i am new to topcoder and i have not taken part in any of the previous TCO matches, am i allowed to take part in this one?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    This one is only for those who advanced from Round 1. If you want to take part in topcoder contests, check out Single Round Matches (SRM).

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I have taken part in 2srms before but not in any TCO'14 match , thats why i just wanted to find out if i was eligible for this one or not, btw thnx for your help :)

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        if you haven't taken part (and advanced) in TCO 2014 Algorithm Round 1, then (sorry for the bad news) u are not eligible to take part in Round 2.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Maybe I can write out of competition?

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

            if u have advanced from Round 1, and also advanced in one of the rounds 2A or 2B, then u can participate in the Parallel Round 2C.

»
10 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Oka~y, WTF is going on. And this isn't a question, because WTF is definitely going on. I don't know how about others, but the final results don't show me any systest AC, just pending scores...

what's more, my rating got updated and I can't log in to the Arena. What's next, aliens climbing out of my monitor?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    when i enter my Username and Password into arena, it waits around 30 seconds and then says "Request timed out".
    anybody else facing similar problems?

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Yes, me too, this happened since 30 minutes ago :) BTW, any chance to get the T-shirt if my rank is 23X ?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        No chance for T-shirt, sorry! There are 350 T-shirts, first 50 places were different in all 3 contests, so that leaves 200 T-shirts for places 51 and lower. Saying that 23X's place gets a T-shirt is like saying that 18X out of these 200 people were placed in top 23X in all 3 contests. Or something like that.

        My guess is you have to be in the top 140-190 to get a T-shirt. Really depends on the diversity of the results.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        I think that you have no chances for T-shirt:( Take a look at last year's winners.

        BTW, has someone made same list for this year?

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        what is the criteria to get a t-shirt?
        best score best position of all 3 rounds (whichever participated) of each participant is taken, and top 350 of these get a t-shirt. am i correct?

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yes, you are) Only results with score >0 are taken into account (but usually it do not affect list of winners). Rules, scroll down for part about t-shirts.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It's to be expected that the arena system's disabled and TC techs are working on it.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, they notified that there were problems with system testing. Most likely they shut down the arena to investigate.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve 500pt problem?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    It's BFS, you just take all edges of a clique at once. Notice that when your BFS visits the second vertex of some clique, you can ignore all edges from that vertex in that clique, since the distances of all vertices that belong to it can't decrease anymore even if you tried these edges. That means you can do a BFS where you mark all cliques, of which you already visited a vertex (there are at most 2500 of them), and for each vertex, check all cliques and only try edges from that vertex that belong to cliques visited for the first time.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      So, basically, on each BFS step we process the current vertex v and:

      1. Pick all the cliques in which v lies.
      2. For each clique that we haven't processed yet, update distances to vertices in them that we haven't visited yet to dist[v] + 1, put these vertices to the queue.
      3. Mark all cliques we processed on this step as processed.
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes, that was the best way to code it.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The complexity of that is O(N^3), right?

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          No, it's O(NV + N2), where V is... well, size of the array V. Suppose we're doing a BFS from some vertex. Notice that we only check each clique as many times as it's mentioned among all vertices to which it belongs, and there are just V such vertices in total; similarly, we'll only try to go to each element of V once. That means a BFS only tries O(V) "edges", so it takes O(N + V) time, and all BFS together take O(N(N + V)) time.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

      (Ignore, same idea was already posted but I missed it when initially reading the thread. Sorry!)

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You should add one vertex per clique and match original vertices with corresponding "clique vertices" only. So, in this graph all the distances are exactly 2 times bigger than in original one. But the edges number is linear and you can call BFS from each original vertex.

    UPD: Another answer has appeared while typing :)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What about 3th problem? How to solve this? :-)