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

A problem with graph
Автор toilanvd_HSGS, 10 лет назад, По-английски

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!

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

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

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

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

    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.

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

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

      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.

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

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

→ Ответить