→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
28:51:18
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
28:51:18
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 12:43:44 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Thank you for reminding me, you care about me more than TC : pp.
To everyone who missed this SRM because of the reschedule: add the topcoder event calendar to your google calendar, then check "notify me one day before each event". This even sends out e-mails with your local time zone!
TC emails have never been reliable, but at least Google has never failed me so far.
Could you give a link? The event calendar which got by Googling "Topcoder Event Calendar" mentioned today's SRM to be on December 6th. :/
The calendar is at http://www.topcoder.com/community/events/
Hmm, I can't log in.
UPD: Now, I can. Match postponed by 1 hour.
According to topcoder event calendar SRM 640 was on sunday, glad I saw your post, thanx.
Something's wrong with the old Topcoder theme events calendar. SRM 640 was on tuesday there some time ago but now it's messed up)
Looks like new theme calendar is the only choice.
An hour delay. Looks like I've no chance to participate =(
This java application is the biggest shit that I ever seen.
I admit it, problem 550 div1 caused me to waste a lot of paper ,and in the end hasn't solved it!
+1. I wonder how to practise the skills which are required to solve such problems and what the skills are. I tried so many ways to connect the edges and for each of them I realized (not always immediately) that it does not work.
Well, the first thing I realized immediately (this grammatic construction is cool, it has 2 meanings :D): I can draw the first ans vertices on the left, on the right and connect the corresponding pairs.
Next: one unmatched vertex has to be connected to d matched ones (it obviously can't be connected to unmatched ones), and we can connect all other unmatched vertices to these as well. That's one biclique on each side.
Similarly, we can make these matched vertices into a biclique with their matching counterparts.
There are some more steps, like splitting the matched vertices into 2 bicliques, where one of them has d vertices in each part and the other has ans - d, and each biclique has one part connected to n1 - ans / n2 - ans unmatched vertices, and then figuring out that we can make another biclique between 2 parts of these 2 bicliques, but it's hard to explain without pictures. The result is very simple, though.
Ну наконец-то нормально SRM написал. Почелленджил все три харда у себя в комнате, room winner и 12 место в диве.
Как 550 делать? Во всех решениях почти одна и та же формула, но я не могу понять, откуда она берется.
О, а не расскажешь как делать 1000? У неё настолько простое условие, что совершенно нет идей, как её не в лоб решать.
Основной факт: если у x[i] и y[j] одинаковый остаток по модулю p, то p прибавляется к ответу с соответствующим коэффициентом (если x[i] и y[j] при этом не равны).
Теперь решение. Переберем модуль до корня. Для каждого остатка сохраним список x[i], имеющих такой остаток по этому модулю. Для каждого y[j] пробежимся по списку с соответствующим остатком и обновим ответ. Всего операций будет не больше, чем 1000 * 1000 * log(10^9).
Таким образом мы учли все делители меньше корня. Для того, чтобы учесть остальные, будем хранить матрицу xy[i][j], в которой поддерживать в актуальном виде разность x[i]-y[j]. В конце пробегаемся по этой матрице, если в какой-то клетке стоит не 1 и не 0, то обновляем ответ.
Размер максимального паросочетания равен размеру минимального вершинного покрытия. Назначим x вершин из левой доли и ans — x вершин из правой доли вершинами минимального вершинного покрытия. Проведем из всех вершин ребра к вершинам покрытия из противоположной доли. Всего таких ребер x * n1 + (ans — x) * n2 — x * (ans — x). Нужно найти максимум этой функции.
I was very lucky in 550. I made 2 errors in formulas and 2 errors in thought process, but 3 of them "xored" to correct formula and fourth error turned out to be nondangerous xD.
I had sth like - 2a·ans + 2a2 = a( - ans + a) and I forget to add all edges between two groups of vertices of a and b elements, but in my solution ans = a + b, so difference I made because of wrong formula resulted in having a·(ans - a) more edges and difference caused by forgetting those edges resulted in having ab less edges, but a·(ans - a) = ab, so it all cancelled xD. Moreover I thought that I need to search for a minimum value of quadratic function but I messed up signs and it turned out that it was completely unnessecary, because it was sufficient to check them only on boundaries :P.
But nevermind, got accepted and 6th place :D.
Right now, in the practice room on 1000:
Uhh... what?
Какое решение для див2 1000. Я придумал одно, но не успел дописать. Правильно ли оно или нет?
Мое решение состояло в том что надо найти НОД всех подмножеств и пытаться оптимизировать наш ответ. Если НОД = 1 то за модуль я беру 2(скорее всего это не оптимально).
Hello,what is the approach to solve Div1 250?
Remove edges between vertices with the same color and count a number of connected components. Subtract 1 and that's your answer.