| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
Давайте делиться впечатлениями о прошедшем отборе.
Самый забавный момент был у меня, когда за 10 минут до конца моя C падала с assert-ом, что говорило о том, что одна структура данных считается с отличием от наивного решения. Поискал баг, не нашел. Закомментил assert и скачал input. Не знаю чем закончится, но на инпутах rng_58 и Petr мое решение выдает ответы как у них :)
Я во 2ой написал Ахо-Корасика за какую-то невменяемую полиномиальную асимптотику, скачал инпут, убедился, что оно тесткейсы с ненулевой скоростью решает, и пошёл читать третью. Когда оно через 6 минут досчитало не всё — был неприятный сюрприз :( Хотел забить, но к счастью передумал и написал таки 3ю (кстати, кто как её решал? мне кажется, что моё решение работает за O(nm), но доказывать я умею только O(m2)).
Вообще, по сравнению с прошлыми фейсбуками, этот финальный отбор какой-то совсем халявный. Поздравляю всех прошедших!
У меня что-то вроде куба. Я начинал с пустого графа и добавлял в него дуги, поддерживая отношение сильной связности, кол-во вершин в блоках и множество стоков. При добавлении дуги иногда надо пересчитывать за квадрат (может на log), но это когда какая-то компонента сильной связности растет. Таких событий не более n. А отвечал на запрос — выбирал из множества k самых маленьких стоков (по числу вершин).
У меня работает за что-то в стиле
. Можешь своё рассказать?
В явном виде поддерживаю конденсацию графа: СНМ + матрица смежности в битсетах. Потом начинаю добавлять рёбра с дорогих, каждый запрос обрабатывается за не более, чем линию операций с битсетами
А по мне так в самый раз. Лучше, чем когда больше одной решает пара человек и всё решает время :)
Ну моё видимо тупее. Добавляю дуги по одной, поддерживаю только компоненты сильной связности, из которых ничего не выходит. Интересны дуги из компоненты в незивестно что (остальные дуги — трив). Такой случай я обрабатываю dfs'ом из конца дуги с понятными отсечениями. Но это по идее слишком медленно, поэтому я для вершин ещё храню, какие компоненты из них достижимы (либо "неизвестно", либо "вот такая компонента", либо "больше одной компоненты"), и обновляю это в dfs. Правда, доказывать про это дополнительное отсечение я ничего не умею.
P.S. Проверил — на их тестах отлично работает и без отсечения, видимо, из-за рандомности.
Казалось бы там совсем не нужна асимптотика в Корасике. Я, например, тупо создал отсортированный вектор всевозможных префиксов и накидал потом failureLinks наивным способом (удаляю первую букву, пока не найду префикс).
Ну вот, а у меня список префиксов был неотсортированным :) В общем, 100 или 100^2 там убрать было очень просто, но не за 30 секунд до time expired (когда я осознал, что эта версия не успевает).
Забыл протащить флаги окончания по суффиксным ссылкам в Ахо-Корасик. Свалилась, но всё равно прошёл, второй раз повезло на FB Hacker Cup :)
А контест хороший получился: первая и третья с неплохим временем — проход. Мне кажется, это лучше, чем в прошлом году.
Мне кажется что лучше было бы, если бы двух первых с хорошим временем тоже хватало. А то первые две фактически ни на что не влияли вообще (ну, кроме Сергея Рогуленко :))
Неужели такая стопка ошибок из-за этого?
И кстати, я строил Ахо-Корасика за долго и предварительно вычистил массив от строк, подстроки которых есть в наборе. С чего оно упало-то?
Я тоже это сделал. У rng_58 упала из-за одинаковых строк в наборе. У меня была тонкость: я значения для динамик считал в long long и long double одновременно, чтобы не париться с возможными переполнениями.
Да, я уже понял, одинаковые строки — FAIL, надо было инпут поюникать.
Переполняется long long небось?
Нет, у меня устойчивая к этому реализация. Я считаю перебор с сохранением (state, l, k) но ифаю сохранененное только на предмет < k. В этом случае сложность по-прежнему state*l, поскольку не более, чем дважды.
Бага идиотская — при двух равных я выкидываю обе.
Видимо, это был частый баг. У меня на этом же упало и у maksay.
Facebook такой Facebook...
Миша, поздравляю с проходом!
А что с Facebook?
Сам не ожидал, спасибо! На прошлом раунде тоже был последний со всеми задачами. Кто понял жизнь, тот не спешит :) Оба раза последняя начинала работать чудесным образом за минуты до конца.
Андрей, в восхищении от твоей победы! Поздравляю!
Handles:
1 — andrewzta
2 — hos.lyric
3 — watashi
4 — cerealguy
5 — RAD
6 — Petr
7 — Shef
8 — MikeMirzayanov
9 — RAVEman
10 — rng_58
11 — kalinov
12 — vepifanov
13 — meret
14 — zeliboba
15 — ilyakor
16 — yeputons
17 — tomekkulczynski
18 — KADR
19 — Marcin_smu
20 — eatmore
21 — tourist
22 — alexander86
23 — izulin
24 — pparys
25 — John Dethridge
7 — Shef 23 — seems like Psyho from TopCoder (his name is Przemyslaw Debiak)
Nope, 23rd place is izulin
7 — vasyl(alphacom) from TC
2 — hos.lyric, his name is Kazuhiro Hosaka.
Это fail! В прошлом году 27е место, в этом — 26е. В следующем году должен пройти :)
Нет, Fail — это неправильно понять условие и полтора часа решать не ту третью задачу.
Это точно. А ведь всего лишь, надо было семпл разобрать :(
А разве не окажется, что кто-нибудь наверняка откажется и тебя позовут?
Если не ошибаюсь, в прошлом году Андрей Станкевич занял 26 место, но на финале (судя по фотке) его не было. Мне кажется, в отличие от GCJ тут почти все пишут не ради фана, а ради именно прохождения на финал, поэтому и отказываются редко.
Месяц до онсайта, так что кто-то может и не успеть визу сделать.
кусок правил:
All Onsite Competitors must confirm their attendance at the onsite event no later than March 4, 2013. If an Onsite Competitor is required to travel from outside the United States, the Onsite Competitor must show proof of a visa application and/or passport by March 4, 2013. Onsite Competitors who fail to meet this requirement may be replaced as an Onsite Competitor.
фраза "visa application" тут означает "подать заявление на визу до 4 марта" или "уже получить визу"?
Очень важный вопрос. Думаю, что речь идет о получении визы к 04.03.2013, и подтверждении сего факта. Какое им дело да наших очередей.
В то же время в СПб среднее время ожидания собеседования на визу 19 дней + 2 дня на изготовление. То есть не раньше 11.03, это если завтра записаться.
А они какое-то письмо присылают? Цель поездки, принимающая сторона, оплата поездки? Отликнитесь, кто в курсе.
Честно говоря, я не вижу, как можно понять эту фразу, как получение визы. Если бы это было так, то было бы написано proof of visa/proof of visa issuance. Написано именно application
Ну видимо они хотят именно application, надеясь, что за почти 3 недели визу смогут сделать (что далеко не всегда верно).
Письмо они присылают, и насколько я помню — в письме указывают это ужасное официальное название контеста. Поэтому если не хочется после собеседования получить background check на 2 недели — лучше внятно объяснить, что к хакерам это никакого отношения не имеет :)
Для B-1 и J-1 визы существует запись на срочное собеседование(проходит в 10 — 11 утра, очередь около недели максимум, как я помню), где нужно показать консулу, что это действительно срочно. Основное требование — отсутствие отказов по американским визам за прошедшие полгода.
Сегодня письмо прислали, что один человек отказался и я прохожу. Правда, меньше двух недель осталось)
Anyone could add this year's problemset on the GYM. ( ⊙ o ⊙ )。。
The official website itself is inconvenient for practice .. .
Agree with it...In China it is blocked as well...
And Cong to all those onstiers :) wish I can grow up quickly.
I wonder how watashi this year and ACRush last year were able to compete if the site is blocked.
VPN?
Maybe with some kind of proxy/VPN.
You know, bypassing the Great Firewall is an important skill for those who lives in China :D We cannot even search "胡萝卜"("carrot" in Chinese) on Google without bypassing censorship.
omg, what's wrong with carrot?
But I've heard from person who have been in China that you have Chinese analogues of search engines (Google) and social networks (Twitter and Facebook). Why just not to use of them? Of course, it's not applicable to Facebook Hacker Cup.
BTW, sorry for my curiosity, I just want to know what Chinese people feel and think about that firewall and does it really bother them.
Weibo (a Twitter copy) and Renren (a Facebook copy) is okay in my opinion. But Baidu (the most popular search engine in China) is not as powerful as Google, especially for English pages and scholar.
You can compare Baidu's result with Google's. Baidu's is not very useful.
As I showed before, people usually say 胡(Hu) instead of 胡锦涛(Hu Jintao) , so the character "胡" was banned. Unfortunately, the firewall cannot really understand what you are trying to search, so all words containing 胡 get banned, including 胡萝卜(carrot). That's why we hate it.
Most Chinese people don't care about the firewall because services outside the wall are seldomly used by them. But as a coder, I think it's really annoying :(
Thank you for such interesting answer. Wish you one day you can search google without any obstacles ^_^
Where there is a wall (Great Firewall) there is a ladder to climb and cross in. :)
Does anyone know the handle (if he has one ) of competitor 28, Eryk ?
Eryx