toilanvd_HSGS's blog

A problem with graph
By toilanvd_HSGS, 9 years ago, In English

Ok, I will go straight to the problem. Give N vertexes (N<=200000), build a graph by completing M (M<=200000) queries, each of them contain only one integer X (2<= X <= N), that means you must connect vertex 1 to vertex X, vertex 2 to vertex X+1, ..., and vertex N-X+1 to vertex N.

After built that graph, you have to list all connected components of that.

Thanks for your help!

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

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

This code counts the connected components, maybe you can use a similar idea to list them?

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

    Thanks for your help! This problem is really hard! I still don't understand completely what algorithm is hidden in that source code. I will keep reading.

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

Notice that if we have a query X, that means vertices with indexes congruent modulo X-1 will be connected. When we process a query, note that it will connect congruence classes. More specifically, if we currently have congruence classes mod A, and we are processing a query B, then we will be left with congruence classes mod gcd(A,B). There is only one slight complication when a congruence class is unable to transition because going left or right would go out of range. We can take care of this problem if we process queries from smallest to largest though. I think the complexity should be NlogN since gcd decreases by at least half each time.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Uhm, but in test N= 17, M= 2, X[1]= 10, X[2]= 14, after built edges, there is only congruence class of mod 4, it is not congruence class of mod gcd(10,14)= 2.

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

      Yeah you're right, my algorithm above isn't correct. After we process the first query (10), we will have connected components corresponding to congruences mod 9. However, when we process the next query, some vertices will go out of bounds when incremented by 13 (=14-1). For example, if we increment 6 by 13, we get 19, which is out of bounds. In the end of the example above, we will be left with connected components of {1,5},{2,6},{3,7},{4,8},{0} of classes mod 9. I overlooked some things, and the out of bounds problem is actually quite tough to resolve.

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

Here's a comment on a similar problem in Petr's blog, made by rng_58.

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

    Wow, reducing the actual graph itself is pretty cool. Thanks for sharing!

    → Reply