There will be online version of the ACM ICPC Phukhet Regional 2013 tomorrow 14:00UTC time. It will be 5 hour contest. You are cordially invited to participate in the contest. Hope you will enjoy the set!
Here is the contest link
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 21:17:42 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Anyone has hints for H? I tried Gaussian Elimination for each query but it was too slow.
The constraint on N was small, so a backtrack or bitset DP of some sort should work.
How do you handle repeating vertices?
That was just a wild guess. Not like I coded anything... (I did the first 1.5 hours of this, then today's CF round and realized that it won't do me any good to train much with no actual competition in sight :D)
We can precompute some special inverse matrix in advance and answer each query in O(n2). This matrix seems to be depend on t but precomputing n matrices still gets TLE. Then I try the same matrix for all t and it passed. I have no idea why :)
I guess, since t is O(n), so generate O(n) matrices each of size O(n^2). And also do the gaussian elimination in O(n^6) per matrix to answer each query O(1). Am I mistaking?