Editorial for TLE '15 P6 - Rock, Paper, Scissors

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

For the 20% test case, we can generate a 2D array representing if a node can directly or indirectly beat another node. After, for each query, generate all possible subsets, check each subset to see if it is valid, and output the size of the greatest valid subset.

In order to get 100% of the points:

First, use Tarjan's Strongly Connected Components algorithm to group all nodes that are strongly connected. Then, run a DFS to check which components are better than others. Notice that the MEV between two components (and thus between nodes in those two components) is the largest number of nodes in a path between two components. Thus, we can use dynamic programming on the SCC (strongly connected components) DAG (directed acyclic graph) to determine the MEV between any two components and answer queries in constant time. The DP can be done during the DFS after Tarjan's SCC algorithm.

Time complexity: \mathcal{O}(NM + Q)

Comments


  • -1
    XIAOAGE  commented on March 21, 2016, 12:32 p.m. ← edited

    What's the faster way to compute the longest path between any 2 nodes on a DAG?

    I've searched on google that there's a solution using topological sorting. Do I need that or there's an easier way?


    • 1
      ZQFMGB12  commented on March 26, 2016, 4:05 a.m. ← edited

      This problem doesn't ask for the longest path between any 2 nodes on a DAG.