hmehta's blog

Topcoder SRM 783
By hmehta, history, 4 years ago, In English

Hey All!

Topcoder SRM 783 is scheduled to start at 12:00 UTC -4, April 11, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to lg5293 and misof for writing the problem set and coordinating the round. Also thanks to a.poorakhavan for writing the editorials.

This is the first SRM of Stage 3 of TCO20 Algorithm Tournament.

Stage 3 TCO20 Points Leaderboard | Topcoder Java Applet | Upcoming SRMs and MMs

Some Important Links
Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

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

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

So... I will write the reminder. It will start in around 3 hours.

  • For those who doesn't know how to compete: It's good to read this article!

In last SRM 782 we had 536 participants, which is the highest number in last 50 SRMs! And now there's already 900+ registerants for this SRM. The increase can be due to coronavirus lockdown's effect, but also other effects are possible.
→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +39 Vote: I do not like it

How to solve Div1 500pts.
Just read last div2 comments
Last div2D

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

I got confused if i was participating in SRM Div2 or Physics exam.

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

I didn't actually struggle much in figuring out the problem statement of Div1 250 — CardboardBoxes, however, some of them did. I don't mean the problem statement is bad and obscure. It was fair, but not the best.

To make the best statement, I suggest adding pictures (like PNG or JPG) on some problem statement like this. This will improve the readability drastically! For the case of Div1 250, for example, putting one example of cardboard box and state that the surface area is 470.

I don't see pictures on problem statement of SRM recently. If I remember correctly there was in the past. That's why I suggest.

P.S. Div1 1000 was interesting. I liked it a lot :)

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

I found alternative approach of Div1 1000 — RecursiveTournament.

First, the graph which is not strongly connected, can divide the vertices into two part, let them $$$S$$$ and $$$T$$$, so that all internal edge between $$$S$$$ and $$$T$$$ is directed to $$$S \rightarrow T$$$.
If you are given $$$S$$$, calculating all $$$T$$$ is not really difficult. We can first find the maximal $$$T$$$ (let it $$$T_{max}$$$) and all non-empty subset of $$$T_{max}$$$ is a valid $$$T$$$, but not for others.
Let's define $$$out_i$$$ the set of outgoing vertices from $$$i$$$ (i.e. vertex $$$j$$$ that there's edge $$$i \rightarrow j$$$). Then, $$$T_{max}$$$ is the intersection of $$$out_k$$$ for all $$$k \in S$$$.

Now let's denote a set by binary number (i.e. bit integer). First, calculating $$$out_k$$$ is easy. Then, using dynamic programming, we can calculate $$$T_{max}$$$ in $$$O(2^N)$$$. Let's denote $$$M_S$$$ the set $$$T_{max}$$$ for given $$$S$$$.

The induced subgraph with vertex set $$$V$$$ is not strongly connected if there's at least one $$$S$$$ which hold all of the following conditions:

  • $$$V$$$ is completely included in $$$S \cup M_S$$$.
  • $$$V$$$ is not included in $$$S$$$.
  • $$$V$$$ is not included in $$$M_S$$$.
So, let's define $$$c_S$$$ the integer for each set, which initialized to zero. We increment $$$c_{S \cup M_S}$$$ by one for all $$$S$$$. Then we decrement $$$c_S$$$ by one for all $$$S$$$. Then we decrement $$$c_{M_S}$$$ by one for all $$$S$$$.

Then, $$$S$$$ is not strongly connected if sum of $$$c_T$$$ for all $$$T$$$ such that $$$S \subset T$$$. We can calculate such sum in $$$O(2^N \times N)$$$ by Fast Zeta Transform!
We can see my implementation in practice room, and also from here. It ran in 244 milliseconds at maximum, when $$$n = 23$$$.
Now I want to know if there's an $$$O(2^N)$$$ solution or even a polynomial-time solution. Let's discuss!
→ Reply