Killever's blog

TCO'14 Algorithm Round 2C
By Killever, 10 years ago, In English

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

Tags tco
  • Vote: I like it
  • +23
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

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

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

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

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

        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.

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

          Maybe I can write out of competition?

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

            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.

            → Reply
»
10 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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?

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

    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?

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

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

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

        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.

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

        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?

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

        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?

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

          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.

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

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

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

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

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

How to solve 500pt problem?

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

    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.

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

      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.
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, that was the best way to code it.

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

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

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

          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.

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

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

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

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

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

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

→ Reply