hmehta's blog

TCO19 Algorithm Round 1B and Parallel Round
By hmehta, history, 6 years ago, In English

The first Algorithm Competition Online Rounds of the 2019 Topcoder Open has arrived! Round 1B will be held on Wednesday May 1, 2019 at 07:00 UTC -4. Registration is open for the round and closes at 06:55 UTC -4, May 01 2019.

There will also be a rated parallel round for those who have already qualified for Round 2

Did you win an Automatic Berth a.k.a Bye for Round 1? Check out the list of members who won an automatic berth to Round 2 here.

Did you qualify to Round 2 from Round 1A ? Check out the list of members who qualified to to Round 2 from Round 1A here.

There will also be a rated parallel round for those who have already qualified for Round 2

How many will qualify? The 750 highest scorers from each Round 1 will win a spot in Round 2 of the Algorithm Competition. Note: To be eligible to advance from an Online Round Match, the Competitor must finish the Match with a point total greater than zero.

Best of luck to you in the Arena! -Topcoder

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

Comments Comments (25)
| Write comment?
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Parallel Round is rated?

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

Who is the writer?

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

How to Solve C.

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

    Thanks all for participating!

    The round was prepared by espr1t. You can find the editorials here

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

Is O(n^2) supposed pass for B?

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

    I think so and my quadratic time solution passed. But there's $$$O(n^2 \log n)$$$ solution which uses binary search, and I thought that it should TLE.

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

    N can be 10^4 so the worst case is 10^8. Is it possible that such a number of operations can pass in two seconds?

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

On the Medium, any simple counter example why my graph dp fails on the last test sample? I tried the N*Log(N) approach.

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

    I have the same problem and cannot figure out why!

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

      I got it, consider a loop, any node should give the same answer (lenght of loop), but in my (our?) case only the first node we've visited gives that answer, all other give n-(time of visit). This matters when optimal answer ends in a loop that we've processed but not starting with the entering node.

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

    It should be upper_bound rather then lower_bound I guess.

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

    In a general graph, if you have a path that dives into a cycle (e.g. 1->2->3->4->5->3) then in theory you could first run dp from somewhere in the cycle (in the example, from 4) and fill the dp (in the example, dp[4]=3, dp[5]=2, dp[3]=1) and then from the path (dp[2]=dp[3]+1=2, dp[1]=3) giving you too small answer.

    Taking M=10, A=P=2, B=Q=0, H1=7, N=5 has this property. The sequence is 7->4->8->6->2 but you first run the dfs from 2 and only later from 7. Your solution returns 4.

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

      Thanks for the great explanation! So that's why the longest path problem cannot be solved with dynamic programming in general until the graph is acyclic.

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

      Thank you, modified it and now it passes with max 14ms on worst test cases.

      Spoiler
      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

When is the rating change for parallel round? I'm really hoping to get back to red in 1 day.

P.S. It was updated. 2189 --> 2242 (+53). I was yellow coder just for 1 day.

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

    We can be Yellows, just for one day.

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

Will greedy work for 1000 pt. -- take the loneliest color and put it in its biggest group so far ?

The editorial didn't mention if any greedy solution exists.

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

    No, greedy shouldn't work here. But you can try — if you manage to pass, let me know and I'll add it to the analysis :)

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

      I tried my greedy algo above. It didn't work. The reason is that when there are equally good choices to consider, there is no way to arbitrage and if you choose any of them, there are some which do better finally.

      In short, there needs to be additional thought on how to arbitrage between the loneliest ones.

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

Can someone please share nlogn code for 500?

→ Reply