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
Parallel Round is rated?
Yup :)
Who is the writer?
Check Here.
How to Solve C.
Thanks all for participating!
The round was prepared by espr1t. You can find the editorials here
Is O(n^2) supposed pass for B?
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.
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?
The constant factor is small, so I unsure.
On the Medium, any simple counter example why my graph dp fails on the last test sample? I tried the N*Log(N) approach.
I have the same problem and cannot figure out why!
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.
It should be upper_bound rather then lower_bound I guess.
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.
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.
Thank you, modified it and now it passes with max 14ms on worst test cases.
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.
We can be Yellows, just for one day.
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.
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 :)
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.
Can someone please share nlogn code for 500?
It's definitely not the best code and I'm pretty sure I've solved such a task nicer. But since I lost so many points on this crap, I can share it, so that it is at least useful for somebody:
solution
https://codeforces.com/blog/entry/66807?#comment-508909