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:)
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
35:03:15
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
35:03:15
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 06:31:45 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
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.
Here is the address: https://arena.topcoder.com/index.html#/u/practiceCode/15833/33977/12832/1/319775
If I know which SRM, I can found editorial on Google:(
SRM 600.5
I can't found it. It seems that nobody write editorial for this contest:(
Maybe from big $$$n$$$ you can find the answer with Berlekamp-Massey?
Ah, $$$d_i$$$ can be huge :(
For big N, wouldn't the answer be just gcd?
Yes, i think if $$$n > 2 \cdot \max{d}$$$.
But what the answer will be when $$$n$$$ and $$$d_i$$$ both huge?
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.
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.
Please, anybody replies? I neeeeeed the editorial! I'm VERY interested in this problem :(