| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
Вторая версия второго отборочного раунда состоится в 08:00 13 июня.
Отличный шанс получить футболку соревнования, войти в топ 25 участников и побороться за призовой фонд в финале!
Раунд для вас подготовил GlebsHP, и даже обещает после его окончания выложить разбор! Отличный повод начать ближайшую субботу пораньше.
UPD До раунда осталось совсем немного, не пропустите!
Спасибо, что хотя бы не в 5 =)
В 5 утра серверы Яндекса слишком перегружены, поэтому решили перенести :)
Ну ладно уже троллить-то
Я думаю, Яндекс просто решил поиграть в "мафию":
Надо наоборот, а то программисты увидят, где сервера
Если программисты не будут видеть сервера, то у них только "отправка вслепую" будет.
Хотелось бы обратиться с просьбой добавить "суммарное штрафное время" в таблицу результатов отборочного этапа. А то не очень понятно как сортируются участники с одинаковым количеством решеных задач.
Ага, а ещё поиск по имени сделать, как в таблице результатов раунда, ну или хотя бы поиск себя.
Кстати, забавный вопрос: а как будут распределяться футболки среди не решивших ни одной задачи (которые судя по всему войдут в 512 лучших)?
Если я правильно понимаю, то тем, кто не решил ни одной задачи, ничего выдаваться не будет.
Не совсем, мне, например, прислали в прошлом году.
After this contest if someone solved 0 is in 512 will he/she take a t-shirt?!
Are you serious man :P?
Нужно ли где-нибудь заранее регистрироваться? На сайте ничего не вижу.
Уже нашёл. И уже пролетел :(
People are talking that t-shirts only for indians,please tell us that we can get t-shirts from any place ^_^
Only Indians are eligible to get AC in Yandex, so how would you want to win Tshirt with 0 problems solved?
I always thought that Yandex sounds a bit indian :]
Ну вы же несерьезно, ну.
Как шутка, это смотрелось бы великолепно, конечно.
"Соревнование завершено. Отправка решений запрещена"
"Соревнование завершено. Отправка решений запрещена".
Я один такой удачливый?
А нет, кажется, не один.
Соревнование виртуальное, или это глюк?
А теперь виртуальное соревнование?)
у меня "стартовать вирт соревнование". стартовать или нет?
Виртуальное соревнование идет, вы можете стартовать
А теперь "Виртуальное соревнование идет, вы можете стартовать". Ну какое нахрен виртуальное соревнование?
Firstly it said "The contest is over. Submissions are not allowed" and then it allowed to virtually participate. Was that supposed to be like that xd (I started)? Please don't do it to me for the second time ; d
Опять завершилось.
Кто-нибудь пробовал начинать виртуальное соревнование? Там были условия?
Да,да.
Please, press the "start virtual contest" button.
There is no such button anymore.
No such button now :(
There are no standings. (Although that may be because nobody has submitted anything.)
i clicked on it, and it shows "The contest is over. Submissions are not allowed"
Seriously? Surprize virtual contest?
опять
For how long virtual contest will be open?
we'll fix the starting time for everyone on 8:00 in a few minutes
So everyone who started virtual contest earlier will have an advantage?
Was it possible to start it before 8:00? Or do you mean they didn't set start time to 8:00 for people who started virtual contest?
Screw you guys, I'm going home
Is this not a "start virtual contest" button that I ask everyone to press on the title page?
This has no sense: I've pressed 'start vritual contest' button at 8:20 and saw "time left: 1:20" (as if I pressed 'start' at 8:00). This totally ruined contest for me.
Don't get me wrong: problems were great and I'm in top-512 for sure — nothing more to wish as a participant.
But as a human, it was really annoying to see that Round 2.2 went on par with Round 2. In both rounds, there was a non-straightforward way to see problems (random F5 pressing in Round 2, "start virtual participation" in Round 2.2), which put participants in different conditions. And in both rounds, administration neglect that fact and try to continue contest as if nothing happened.
In round 2, the announcement about failure was after about 40 minutes, but it was obvious from the start that something went wrong.
This time, there was a fast announcement that one should press "start virtual participation". But it was totally confusing: I came here for a normal round, not a virtual one. Why should I press that button? Is it safe? Will my participation count in overall rating? Will I save my time or it will start from 8:00? All those questions arouse in my head and I was not sure about pressing that button. And immediately my fears were proven: timer started from 8:00, consuming some part of my time. And after opening standings at the end of contest (my time was out), I saw people with 1:33 and 1:28 virtual participation time (meaning they were still competing). Ridiculous.
Yandex.GEOMETRY.com
I have no idea about geometry.. i could do only 1 question :(
I have ideas,but can't implement coz have not knowledge how to sort vectors by angle,how to find angle and others...
Here I think,for each bitset of length n(which means use i-th vector or not)we should add all angles in 2 consecutive vectors and it should be 2p and then anwer will be "YES";
accurate!
Кто подскажет как решать А и D?
У некоторых ещё идёт виртуальный контест, так что лучше пока не обсуждать задачи.
Am I stupid or D really needed knowledge that every Pythagorean triple can be described as (d(i2 - j2), 2dij, d(i2 + j2))?? It took me much time to solve this problem and I felt sad seeing so many accepted submission xd.
And how you can solve the problem using that fact?
Just generate all Pythagorean triples and check answer by obvious dp xd.
You can generate all possible Pythagorean triples and then do simple dp.
Can you show your code?
http://pastebin.com/x9ZFM6Gs
Just make graph for numbers less then 106: from (i2 + j2)*k to (i2 — j2)*k and (2ijk). After that dynamic.
-_-
-_-
I think anyone who has done anything on projecteuler has used this theorem about 37 times.
What was in 50th test of problem A?
I apologise for not being able to publish analysis immediately. Hope to finish it before today's GCJ.
в D у меня не проходить 4 тест? что за тест?
Возможно, ты считаешь общее количество треугольников? Я так считал сначала. Надо выбрать длину максимальной цепочки d[z] = maxx, y|x2 + y2 = z2(d[x], d[y]) + 1, а не количество треугольников d[z] = maxx, y|x2 + y2 = z2(d[x] + d[y]) + 1. Например, при n = 100 ответ 2, а не 3 (100-80-60 => 80-64-48, 60-48-36).
в А такое решение катит?
Переберем две маски, сделаем первый вектор — сумма всех векторов в 1 маске, и 2 вектор — сумма векторов 2 маски. Приложим 2 векторка к старту. Тогда если вектор(финиш — старт) лежит между этими 2 векторами, то ответ — ДА.
А зачем перебирать маски? Если вектор лежит между КАКИМИ-ТО двумя векторами (или, возможно, совпадает с одним из них), и угол между ними строго меньше 180 градусов, то ответ — ДА.
Можно перебирать только пары векторов.
Достаточно просто два вектора(возможно, одинаковых) перебрать и проверить.
если не трудно, то можно Ваш код
Можно! :)
Что за магические маски. Можно перебрать два вектора и проверить, что нужный вектор — линейная комбинация этих двух с неотрицательными коэффициентами.
(доказательство: пусть
, тогда возьмём 2 линейно независимых 
и 
, пусть 
, будем уменьшать α3 и прибавлять β1, β2 к α1, α2, пока что-нибудь из 3х коэффициентов не станет 0. Процесс можно продолжать, пока не останется <=2 ненулевых векторов).
I'm very interested to see tests 17, 21 and 31 for problem F. There's something strange about my verdicts.
21 and 31 are too large to be posted.
Test 17: baababbbbaa
Answer for test 17: aabbabbbbaa
What about 4 test in D?
Thank you, found my mistake already. It's so stupid :(
Задача C:
У меня зашло за 0.845s (Oracle Java 7 x64) и 0.682s (x64 OpenJDK Java 7). http://mirror.codeforces.com/contest/1/submission/11564395
Я не писал dfs, только три dsu.
А ещё, кстати, есть 0.356s (Oracle Java 7 x32) и 0.689s (x32 OpenJDK Java 7).
Правда тут надо быть осторожнее, x32 работает медленнее при использовании лонгов, чем x64.
Вот код, который я засылал в X для проверки. Результаты:
В дорешивании зашла такая идея:
1) Найти остов с минимальным количеством патрициев (min)
2) Найти остов с максимальным количеством патрициев (max)
3) Возможны все промежуточные остовы — с количеством патрициев a : min <= a <= max.
Доказывать не умею.
Сначала пытался построить такое решение: строим минимальный остов, а затем по одному добавляем ребра весом 1. Понятно, что мы можем их добавлять по одному (просто на старом пути между соединяемыми вершинами выкидываем какое-то ребро весом 0). Ну а затем пришла идея, что раз мы можем добавлять их по одному, то достаточно найти минимальный остов и максимальный, и ответ YES для всех запросов, которые попадают в отрезок между ними.
Вот блин. Написал это на контесте, не прошло 11 тест, подумал, раз не сдают, значит не верно и бросил. Сейчас заменил прима на краскала — прошло. У кого-нибудь прима проходит?
На контесте писал Краскала, но Прим тоже заходит: код.
Занятно, что ты уже рассказывал решение задачи C на страницах Codeforces три года назад.
I used the following logic to try A:
Firstly, if 2 vectors are not in opposite directions, then i assumed that the sector formed by the smaller angle between these 2 vectors is reachable.
Hence, using above inference, i sorted all the given vectors according to the angle they make with x-axis and checked between which 2 vectors does our destination lies. If the difference between the angles of these two vectors is less than PI, output YES , else output NO.
This gave WA on test 39. What might be the fault in this solution?
You may have problems with precision. Because coordinates can be up to 109, the difference between two angles can be about 10 - 18, so you need to use exact arithmetic.
is there any way i might do this with double? i don't have much experience in handling precision errors.. what is the suitable value of eps in such cases?
I was calculating angle using atan2; code with eps=1e-12 gets AC.
So either tests aren't good enough or difference between angles can't be so small.
Tests like this should have very small difference in angle:
For this test, the answer is
YES. And for the next test, the answer isNO:Better way check precision problems is to use vectors like (1000000000, 999999999) and (999999999, 999999998). Atan2 returns the same double for them
Hah, funny. At first thought there shouldn't be difference, because your angle is approximately just 2 times smaller, but what is important here is that atan2 values for eatmore's points are very small, so they are kept with higher precision and that is big difference. Nice!
There were about 10 tests with very small angle differences (about 10 - 18, as eatmore mentioned). No idea why your code has passed, I will investigate this case in the free time and post the result here.
Is there some place I can check my T-shirt address :) to make sure it's correct?
The registration form is inaccessible now.
are you from india ? :D
No. I hope this doesn't disqualify me! :)
I think so :) what's your position?
how to submit my address ? I used social login while registering and it didn't ask for any address then as far as i remember.
I am not sure https://passport.yandex.ru/profile/address
Anyway it would be great to know official version about it.
А где нужно указывать адрес, чтобы пришла майка? Я что-то не нахожу, а ссылка на электронную регистрацию не работает!
А кто-то, кто в сумме за 3 раунда сдал 0 задач получить футболку?
Тогда не понятно кто из них должен получить футболку, а кто нет.
Можно посмотреть, кто хотя бы пытался, а не просто "мертвая душа".
Кто больше тестов прошел XD
Я может как-то пропустил — а разыграли уже футболочки за участие в warm up раунде?
Да, полностью с вами согласен... Та ну просто так обидно, что отменили второй раунд, и именно в нем я сдал одну задачу,а теперь сижу и думаю , почему я так туп, что не смог в остальных раундах сдать хотя бы что-то.
Did registration form ask address?! I couldn't remember.
написал в D простой заоптимизированный перебор с кэшированием результатов для промежуточных вычислений. на localhost время выполнения — милисекунды на всех тестах (проверил на каждом входном числе от 1 до 1000000), но при сдаче стабильно получаю TL на тесте 17.
В чём может быть дело? Что за волшебный тест 17?
http://pastebin.com/Q8SjLie6
Это же неправильное решение. Вы умеете доказывать, что оно быстро работает на всех тестах? В утверждение про миллисекунды не очень верится, особенно если учесть, что возвести миллион int64 в квадрат — уже не миллисекунды.
Попробуйте например тест 967525 (это argmax размера дерева в подобном переборе для чисел до миллиона). Ваше решение работает очень долго.
хм, да, действительно, на этом тесте умирает. Странно, почему я не нашёл его при переборе всех входных данных. Спасибо.
Я был уверен, что удастся упихать.
UPD: упс, я похоже до 10^5 перебрал входные данные. незадача.
Да здравствует король.
27th place after 3 rounds, what a sad story :((
Where do you check place?)
https://contest.yandex.ru/algorithm2015/results/
Thanks!
I'm eager to know how to solve E. If only rectangles nx0 or 0xm would be allowed! Then I will be able to solve it using just one flow. But in order to exclude them I need to run nm flows and that clearly TLEs. However I got an idea how I can speed it up, but it seems too complicated...
I used m*n dinic flow and it was fast enough. The execution time was always below 1 second.
nm Kuhns should be fine.
nm Kuhns without any optimisation attempts whatsoever runs in 1.037s. I was surprised too!
Could the organizers, please, provide a way to check which address we used when we registered for the contest? Thanks!
Как решать B? Мне приходит в голову только следующее: 1. Найти Tmin (минимальное время, когда все колесницы пересекаются) и Tmax (максимальное время, когда все колесницы пересекаются). 2. Запустить тернарный поиск от Tmin до Tmax, чтобы найти максимум.
Tmin и Tmax можно найти идя с первого пересечения последовательно сужая интервал (очевидно, что каждая следующая колесница может только сузить интервал Tmin, Tmax). Естественно, по дороге рассматриваем крайние случаи, такие как: - одинаковые скорости у колесниц; - пустое пересечение (ответ сразу 0). Направление верное или бред?
На плоскости (x, t) множество точек, где находятся все колесницы, является пересечением множества полуплоскостей. Это пересечение можно построить за N·log(N).
Можно просто запустить тернарный поиск от 0 до 1e5, максимизируя разность (со знаком) между минимальным правым концом и максимальным левым. Она выпуклая как разность выпуклой и вогнутой функции (функции выпуклые и вогнутые как максимум и минимум линейных).
Спасибо!
Any news about t-shirts?!
Check your email or go to algorithm.contest.yandex.com for more information
Who are the t-shirt winners of Warm-Up round?!