Hello all. Today , I participated in a contest with problems from the Croatian Olympiad in Informatics. The relevant contest environment is here. I had a perfect solution for the 3rd problem , and I was able to solve the first part ( finding the number of different values of the shortest path) of the first problem.My backtracking solution for the 2nd turned out to be buggy and scored 0. Since they take too long to publish the results along with codes and solutions on COCI , I'd appreciate if anyone who has participated ( specially those solving many tasks perfectly) can explain his algorithmic approaches for solving the problems.Thanks!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
22:37:56
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
22:37:56
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 18:57:04 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Last problem: You can add one more vertex V0 to the graph. Put distances to other nodes as prices of sending spies on assignment. Then the answer if weight of this graph's MST. It is quite easy to prove :)
I didn't solve the first problem because I can't find the sum of the sorhterst distances for large cases. We can use binary search to find the largest X that makes the path shorter than without using hiperroutes at all and, of course, the shortest path will be disticnt for every value of X smaller than this, so the largest X is the first answer in this problem :)
How long did the exam last ?
5 Hours.
SNJEGULJICA :
I use segment tree by this way, for every query (A, B) we will find smallest and largest position of numbers from A to B with segment tree, if largest pos — smallest pos == B — A then answer is YES else it's NO.
How to solve 1 problem ?