Today, at 6 PM MSK (3 PM UTC)
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:17:06
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:17:06
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 02:17:56 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
I'm having problems with registration (It says that registration is by invitation only despite the fact I have automatically advanced to the Round 2). Any ideas how to fix this?
I think admins just forgot to add byes to advancers pool
how bad!!!
Same here.
Hey where has cgy4ever gone?
Damn , my classmate wrote that stupidness :D idk wht's going on there so sry .
I'll be correcting the issue with those who have byes. Those compeittors will be automatically registered for this round.— said TopCoderWe just fixed it: "All competitors with a bye have been automatically registered, our apologies for the trouble. For everyone else competing today, be sure you register at least fifteen minutes before the match begins, thanks!"
WEB ARENA IS DAMN TOO SLOW -_-
I can't login now. I could several hours ago.
Sorry, you cannot perform this operation because you are not assigned to this room. The likely cause is that you did not successfuly register for the match during the registration period.
But I am registered...
Как решать вторую? И решения для первой задачи тоже интересны.
В 400 в дорешку зашел рандом: перемешиваем, пока есть время, и пишем dp[N][value] = true\false. На сис тестах получил TL =\
Я знаю такое решение которое зашло: просто перебираем три элемента, и если с этими тремя элементами можно сделать TARGET, то и со всем массивом можно сделать.
Как такое ломать?
Если я правильно понял, то: из (0, 0), (1, 1), (2, 2) можно получить (0, 0), а из (0, 0), (1, 1), (2, 2), ( - 1, 1) -- нельзя.
НОК((-1,1),(1,1))=(1,1) и сводим тест к предыдущему.
У меня было предположение, что одну из операций надо использовать только один раз и в конце. Так что динамим два множества другой операцией и склеиваем результаты под конец. Упало на систестах, потому что не учёл, что склеивать можно той же операцией, что и динамил.
Кажется, это правильное решение.
Я делал иначе, разобрав четыре случая (на самом деле шесть, если учесть симметричные):
Представим числа 2a3b как точки (a, b) на плоскости. Пусть числу t соответствует точка T = (x, y).
Если существует пара точек A = (x', y) и B = (x, y') таких, что x' ≤ x и y' ≤ y, то можно показать, что все остальные точки можно удалить, не испортив положение точек A и B.
Случай x' ≥ x и y' ≥ y симметричен предыдущему.
Иначе допустим, что существует пара точек A = (x', y) и B = (x, y') таких, что x' ≥ x и y' ≤ y. Тогда утверждается, что мы сможем попасть в точку T тогда и только тогда, когда существует точка C = (x", y") такая, что x" ≤ x и y" ≥ y.
Случай x' ≤ x и y' ≥ y симметричен предыдущему.
Наконец, пусть нашлась единственная точка S, совпавшая с T. Тогда, если все остальные точки лежат либо строго правее и ниже, либо строго левее и выше, то в точку T мы попасть не можем, потому что в какой-то момент S поменяет своё положение и больше в него не вернётся. Иначе можно показать, что ответ Possible.
Во всех остальных конфигурациях среди всех точек не найдётся либо нужной x-координаты, либо нужной y-координаты, а тогда ответ Impossible.
По-видимому, решение с перебором трёх точек выдаёт точно такие же результаты. (Моё, правда, упало из-за теста "{1}, 1" -_\\)
Surprisingly my randomized solution for A passed.
I shuffled the array 1000 times and check if if possible to fix the first element and apply GCD or LCM using DP.
Unfortunately it was not enough to advance, my browser got frozen while testing sample cases.
I would like to know a deterministic solution.
Ugh. I failed 500 on slightly exceeding the memory limit (so slightly that changing long long to int in 4 places would've fixed it).
How to solve the first question?
Unfortunately most of passing 500's solutions were ugly (including mine).
Admins said the intended solution was meed-in-the-middle, but I just googled how to count the number of cliques (http://cs.stackexchange.com/questions/9209/finding-all-cliques-of-a-graph).
tourist's solution looks good
Why this code is TL on topcoder? 400pt
http://pastebin.com/1wxnCQhM
Would have pulled of successful last second submission. Did not change min->max in two lines during last sec updates. Two things 1. The excitement of a successful last sec submission would have been great. 2. Generally frustrated for missing because of typing miss!
My solution on 500 passes if fix stupid bug in 134ms.
Solution is following. We can count sum for each edge independently. For one edge answer is equal to ({Number of cliques with a} + {Number of cliques with b} + 1 — {Number of cliques total}). So the solution is to find number of cliques in graph except each vertex. It's well known, that dp on subsets, works in time 2n / 2 if don't count same mask twice, and choose to get or not to get smallest vertex each time. If use same cache, it's works even faster, than n*2^{n/2} (i think even in 2^{n/2} time, but I can prove, only n/2*2^{n} visited states).
Would you mind elaborating that DP which counts cliques a little?
dp[S] = count of cliques, which are subset of S
Let's v be vertex in S.
If always get as v vertex with minimal id, there is O(2n / 2) states reachable. If v is less than n / 2, there are less than 2n / 2 branches, if v is more, there are less than 2n / 2 states total. Order of vertices is imortant. For example, choose random vertex each time is bad (but choose random order one time is ok, of course).
I did it in other way. Divide vertices on two equal parts. For first part precalculate for every subset A is it clique or not, and if it is clique calculate mask of vertices in second part which is connected with all vertices in A (both could be done by & incident masks of vertices in A). For second part calculate for every subset is it clique. Then calculate convolution of this array. For each query S, we look for subsets A of S in first part and if A-clique add number of subsets in second part which is clique and incident to A.
the same problem, but i have zero execution time on little test
According to the following, system calls like
clock()are not accounted for the reported "Execution time", but are accounted for the timeout, and for some reason the call toclock()is slow on TopCoder: http://apps.topcoder.com/forums/?module=Thread&threadID=507280&start=0&mc=9#511776thanks for link!
Same story here :(
I think problem 400 was nice for people who like
ifs a lot. I'm not sure I likeifs quite so much :(You can also solve the 400 by checking if any pair or triplet of numbers can reach the target (also handling the case where n=1 correctly).
I solved it by bfs on reachable states. Every number 2i3j is a pair i, j. There 9 different types of pairs (first and second coordinate could be <,=,> then in t). It could be proven that every type of pair could be useful not more than twice. Then I made search on this 39 states.
I had the same approach. How to prove it?
Consider about 10 cases =) I haven't done it during round, and for sure submited 4^9 states solution.