Блог пользователя r3novatio

Автор r3novatio, история, 4 года назад, По-английски

I came across this problem in which you have been given a directed graph $$$G=(V,E)$$$ with $$$|V|,|E|\leq 10^5$$$ and one additional edge can be added to $$$E$$$. What can be the maximum size of a strongly connected component in the resulting graph?

If anyone knows an approach, do share.

Thanks.

EDIT: I apologize that the $$$O(V.(V+E))$$$ algorithm that I thought would solve this also turned out to be incorrect.

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

deleted.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

    Consider such a case. The maximum sum path would suggest 1+5+3. But the actual answer here is 10 (by joining sink SCC of left diamond to its source SCC, we get 1+2+3+4 in one SCC)

»
4 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

First create a condensation graph, it will be a DAG(with multiple sources and sinks)

in condensation graph make sure to store number of nodes(original graph) for each node(SCC or dag's node)

for every sink calculate the number of nodes and from which source you achieved the max nodes( this can be done using simple graph dp)

connect the sink to the source(you stored), this should give the required graph. This can be achieved in O(V+E) as only dfs is used here couple of times

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This is what I thought of. Unfortunately it has a worst case of $$$O(V(V+E))$$$ because you might need to traverse a significant portion of graph in every dfs call (due to overlapping) and the dfs will be called for as many sinks there can be (which can be $$$O(V)$$$)

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

      You don't have to do dfs for every sink you can find max number of nodes in every sink in single dfs

      first do a topological sort on condensation graph

      go in order and perform dfs and when you return from a recursion store the maximum number of nodes from the child nodes( here you will visit every node every time)

      something like this

      number_of_nodes[source] = number_of_nodes_in_scc[source]
      max_number_nodes_of_child = 0
      for every child :
           dfs(child)
           max_number_nodes_of_child = max(max_number_nodes_of_child,number_of_nodes[child])
      number_of_nodes[source] += max_number_nodes_of_child
      

      EDIT : Here is a problem which uses the same idea

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        What you have achieved will be the maximum sum path of the condensed graph. Look at the case above (in the image). This algorithm will only find one path with maximum nodes sum. It would fail on the case with a diamond because it'll only output the sum achieved through heaviest path.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What is the problem source?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Best I could think of was an O(V(V+E)) approach.

Share it please.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Make a metagraph $$$G'$$$ where each node has a value equal to the size of SCC it represents. Let $$$ans= -inf$$$

    For every source $$$s$$$ in $$$G'$$$ do,

    • initialise a dp table and run $$$dfs(s)$$$ to fill the table by (i) $$$table[s]=value[s]$$$ and then (ii) propogating $$$table[s]$$$ value to $$$table[v]$$$ for each (visited or unvisited) neighbour $$$v$$$ of $$$s$$$.
    • If maximum value of $$$table[t]$$$ for sink (of this dfs call) $$$t$$$. Then $$$ans=max(ans,table[t])$$$
    • Clear the dp table/visited array and go to next source (step 1)
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      As I understand from your comment, you fix source $$$s$$$, than run some $$$dfs$$$ to calculate $$$table[t]$$$ for all $$$t$$$, and than claim that after your calculations $$$table[t] = \sum_{v} value[v]\cdot f(s,v)\cdot f(v,t)$$$, where $$$f(u,v) = 1$$$ if $$$v$$$ is reachable from $$$u$$$, else $$$0$$$. I cant get how your first step calculates this sum, what do you mean by propagating something to children? Need some formal explanations.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes, I realised this algorithm wouldn't hold up. While propogating values to the descendants, we might run into duplicacies in case where the descendants later happen to lead to common nodes. Sorry but my $$$O(V.(V+E))$$$ algorithm is incorrect.

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

This looks unsolvable, because solving this is as hard as telling the number of reachable nodes for each node in a DAG, which is a known problem and only has approximations in sub-quadratic time. Correct me, if I'm wrong.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    [Deleted]it wont work , I misread the ques.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Cant we find out the number of reachable nodes by iterating through the nodes in the reverse order of topological sorted order and say that dp[u]+=dp[v] for every (u,v) edge.Since this is a DAG I think this way the number of reachble nodes can be counted. Please correct me If I am wrong

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +20 Проголосовать: не нравится

      This will over count whenever some path starting from two childs of u overlap. For example:

      You'll have $$$dp(3) = 3$$$ and $$$dp(2) = 3$$$, but $$$dp(1)$$$ is not $$$3+3$$$.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      Is it really from some hiring test? Writing "atmost" and "<=" seems so unprofessional. (Also the word order is very strange in "Find the maximum size...")

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        I like "find the maximize size" even more:)

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        Professional or not , but people will always judge you. So you only solve problems which are written professionally? Sorry not everyone is pro as you. They made mistakes that's why they are called as humans.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          What exactly is the point of this comment? How are "being pro as me" or "people will always judge you" even related to all this? And I have not said I wouldn't solve problems like this, but I'd certainly form a certain opinion about this company or agency.

          I would also like to point out that my original comment wasn't even really a criticism. I was just expressing my shock ­— I found it totally unbelievable that a professional could write like this. You are unreasonably defensive for some reason.

          People make mistakes, it's more about being able to prevent mistakes. Hiring an editor or even just proofreading, for example.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

            Nowadays it feels like GrammerForces ,before asking for help you have to think a lot whether you should ask or not because some pro Coder will comment about their English or say how they should ask for help. Feels like I am in University where I have to think what others will say If ask this doubt. I comment something and it triggered you, then you suggest something for the solution. I understand it's the author's mistake. " I found totally unbelievable that a professional could write like this " . Awww Do I have to prepare a list of CF unrated rounds happened because of author's solution issues?

            Sorry for my poor english. I just want to say keep it simple and sweet . Do codeforces not grammar or englishforces. Sorry for bothering you. GLHF

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              You can take 1 minute to fix your comment

              Like this

              Btw the only real word I changed was GrammerForces to GrammarForces but as I can see in the last line you can write grammar properly if you try (and that typo could have been on purpose, idk). There are some other issues with the choice of past/present and maybe one letter wrong here and there but those aren't as important as proper punctuation and spacing.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          Why did you even write this? The problem here is that author`s solution is some unproven shit, and as I understand nobody can propose solution for a given problem even in $$$\mathcal{o}(n^3)$$$. So yes, problemsetter is unprofessional.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +12 Проголосовать: не нравится

          Even though I don't care about the markup, which might be unavailable to technical difficulties, there is a huge problem in grammatical errors, cause they lead to misunderstanding and are as said "unprofessional". Just imagine seeing such a text in your workflow. Also the solution (even close to reality, which works with good probability) remains unknown, so I would love to see the official editorial, cause the author is either a genius or his solution is completely wrong.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you have a reduction? (I also think this problem is unsolvable, but I can't really show it either).

    Also, did you mean to write "at least as hard as" or really "as hard as"? If it is as hard as counting reachable nodes, we could have a fast solution with "bit-parallelism".