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

A Hard Problem on Topcoder
Автор meaningIess, история, 6 лет назад, По-английски

You are given a number $$$n$$$ and a set $$$d$$$ that describe the graph. The graph has n vertices, numbered 0 through n-1. Vertices i and j are connected by an edge if and only if |i-j| is an element of d. Return the number of connected components of this graph.|d|<=50 and n<=1e18. In Topcoder its called "HugeGraph". I have searched for the editorial and I found nothing. Please anybody gives a editorial? Btw, for n,|d|<=1e5, if the problem can be solved? Sorry for my bad english:)

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

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

I cannot search for this problem in Topcoder archive. Was this special round? If you know which srm it was you can check petr blog, I think he explains some problems from round he participated.

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

Maybe from big $$$n$$$ you can find the answer with Berlekamp-Massey?

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

    Ah, $$$d_i$$$ can be huge :(

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

    For big N, wouldn't the answer be just gcd?

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

      Yes, i think if $$$n > 2 \cdot \max{d}$$$.

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

      But what the answer will be when $$$n$$$ and $$$d_i$$$ both huge?

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

        Yeah, that's the question ;p

        I don't how to solve it. I only answered to 300iq's comment saying that BM is unnecessary.

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

          For little $$$d_i$$$, it can be seemed $$$gcd$$$. For big $$$d_i$$$, it won't make a loop, every edge using big $$$d_i$$$ will minus the answer by 1? I guess that if all the $$$d_i>=n/2$$$ then the answer is $$$n - edges number$$$? I don't know if it's true.

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

Please, anybody replies? I neeeeeed the editorial! I'm VERY interested in this problem :(

→ Ответить