Tomorrow, the next SRM will be held at 07:00 EDT. Don't miss!
Have a nice SRM. Good luck :D
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | orzdevinwang | 3844 |
| 3 | jqdai0815 | 3682 |
| 4 | jiangly | 3618 |
| 5 | Benq | 3529 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3443 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | atcoder_official | 162 |
| 3 | maomao90 | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 02.12.2024 02:33:23 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
7 AM
SRM
Makes me regret
Choosing STEM
Can anyone tell me how to solve div1 500? Looks rather tricky for me.
I've seen several solutions, but still haven't got the whole idea.
UPD: OMG, second problem in last few weeks in which there's such "shortest-distance" graph is constructed and I don't manage to understand that the cycles can be only of length 2. Hopefully, I won't forget it next time.
The number of connected components depends on the number of cycles. It can be proved that there exist only cycles between 2 vertices. Hence, we can reduce the problem into calculating the expected number of cycles between 2 vertices.
I got this far, but how to solve this kind of problem?
For each vertex you can sort other vertices by priority (first distance, then y coordinate, then x).
Then for each pair of vertices you want rabbits to NOT be in the cells that have higher priority compared to the picked vertices in at least one of the list.
If there are
nplaces for rabbits,rrabbits andecells must be empty, the chance for that is C(n - e - 2, r - 2) / C(n, r) (two picked cells are already occupied by rabbits, which leads to minus 2). Add this chance toansfor each pair.That's O(n^6), not sure if it's quick enough, as I didn't implement it during the contest :c
but the problem said the graph is undirected, so the cycles are edges between two points or not?
A connected component as a directed graph always consists of cycle of size two and some vertices hanging on the cycle vertices as trees. Therefore number of components is equal to the number of cycles of size two.
Expectation of this value is equal to sum of probabilities for every two empty cells of grid to form a 2-cycle. Two points form a 2-cycle iff no point is closer to the first point than the second, and vice versa; so, all points must lie outside some set. The probability for this is Csr - 2 / Cpr, where s is size of the set, p is number of empty cells.
Congratulations for the victory!
Thanks.
There exist people who denote Newton's symbol using that weird notation with Cij :OO!
This notation is widespread in Russia.
"A connected component as a directed graph always consists of cycle of size two and some vertices hanging on the cycle vertices as trees.". What if the connected component is a cycle of size 3, like 1 -> 2 and 2 -> 3 and 3 -> 1? It does not contain cycle of size 2.
Hmm, 1000 didn't seem tricky or really hard to me this time (meet in the middle), I wonder if the fails were due to TLE on constant/log factor...
I think so too. If you had implemented it, you'd see that the time limit was very tight.
I did implement it actually, but didn't manage to debug it in time :D
(and now, I'm getting
Uncaught exception in the practice room on something that should totally pass: an assignment in an existing mapmemlimit exceeded — speaking of which, didn't TC use to report memlimit exceeded specifically?)Yes, there were not enough time for me to make one simple optimization. And that's why my solution failed during contest
I was never able to solve the task 250 in regular DIV 1 (I solved some in TCO) during contest, but today I solved the task 500 :D
But in SRM 635 you was able to earn 0 points but increase your rating, that looks strange :o
Yeah, and not only my rating increased. It's pretty funny. Do nothing and earn points. :D Nowise it does not give much satisfaction, at least not me. I prefer well-deserved successes.
Well, rating systems can act weird in unexpected situations (in this case, tricky 250). How much did you gain exactly?
In a sense, you did well by not losing points :D
I gained 4. xD
And several contests ago in TCO 2A I gained 81 (also doing nothing), but then I was grey.
Well yes, a grey user isn't really expected to get to round 2, so it's normal to gain rating just by being there.
Getting +4 is like nothing at all... so it's not really a fail, I guess.
And in rounds 3A and 3B even some yellow users increased their ratings with 0 — take a look at olpetOdessaONU:)
It's always better try, than do nothing :)
can somebody explain, how to solve div2 1000?
Oh, I got it now, thanks!