I am intrested in solution if n <= 1e5 and n — 1 <= m <= min((n-1) * n / 2 , 1e5) and k <= 1000.Thanks
I mean this solution must work no more when 2seconds. Sorry for dont write it
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
06:49:09
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
06:49:09
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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
Время на сервере: 23.11.2024 10:45:51 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Looking at the constraints the solution is obviously polynomial on N or M so no, it's not NP-hard.
Edit: whoops I just assumed NP != P
Can u give some prompt?
NP-hard is for problems which have do not have a solution which works in polynomial complexity (the degree may be anything, but it has to polynomial). For example a problem with best solution which is exponential might be considered to be NP hard. Your question above obviously has a polynomial solution (as described in editorial), so it isn't NP hard.
Ok thx, but maybe u now how to solve this problem?
Afaik the editorial's solution doesn't make use of any special constraints, so it should be working on your constraints as well.
About what editorial's solution u tell , if it solution for div -3 then its too slow O(nmlogn)
Please elaborate on your proof that P != NP.
/s
Well, I should have written "NP-hard is for problems which have do not yet have a solution which works in polynomial complexity".
Auto comment: topic has been updated by Stimsly (previous revision, new revision, compare).
Auto comment: topic has been updated by Stimsly (previous revision, new revision, compare).
Auto comment: topic has been updated by Stimsly (previous revision, new revision, compare).
Auto comment: topic has been updated by Stimsly (previous revision, new revision, compare).