Блог пользователя lperovskaya

Автор lperovskaya, история, 9 лет назад, По-русски

Вторая версия второго отборочного раунда состоится в 08:00 13 июня.

Отличный шанс получить футболку соревнования, войти в топ 25 участников и побороться за призовой фонд в финале!

Раунд для вас подготовил GlebsHP, и даже обещает после его окончания выложить разбор! Отличный повод начать ближайшую субботу пораньше.

UPD До раунда осталось совсем немного, не пропустите!

  • Проголосовать: нравится
  • +84
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

Спасибо, что хотя бы не в 5 =)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +72 Проголосовать: не нравится

    В 5 утра серверы Яндекса слишком перегружены, поэтому решили перенести :)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Ну ладно уже троллить-то

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +45 Проголосовать: не нравится

      Я думаю, Яндекс просто решил поиграть в "мафию":

      1. Наступило утро.
      2. Программисты просыпаются.
      3. Сервера засыпают.
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +43 Проголосовать: не нравится

        Надо наоборот, а то программисты увидят, где сервера

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

          Если программисты не будут видеть сервера, то у них только "отправка вслепую" будет.

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Хотелось бы обратиться с просьбой добавить "суммарное штрафное время" в таблицу результатов отборочного этапа. А то не очень понятно как сортируются участники с одинаковым количеством решеных задач.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    Ага, а ещё поиск по имени сделать, как в таблице результатов раунда, ну или хотя бы поиск себя.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Кстати, забавный вопрос: а как будут распределяться футболки среди не решивших ни одной задачи (которые судя по всему войдут в 512 лучших)?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Если я правильно понимаю, то тем, кто не решил ни одной задачи, ничего выдаваться не будет.

»
9 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

After this contest if someone solved 0 is in 512 will he/she take a t-shirt?!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Нужно ли где-нибудь заранее регистрироваться? На сайте ничего не вижу.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

People are talking that t-shirts only for indians,please tell us that we can get t-shirts from any place ^_^

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Only Indians are eligible to get AC in Yandex, so how would you want to win Tshirt with 0 problems solved?

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Ну вы же несерьезно, ну.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Как шутка, это смотрелось бы великолепно, конечно.

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

"Соревнование завершено. Отправка решений запрещена"

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

"Соревнование завершено. Отправка решений запрещена".

Я один такой удачливый?

А нет, кажется, не один.

»
9 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Соревнование виртуальное, или это глюк?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А теперь виртуальное соревнование?)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

у меня "стартовать вирт соревнование". стартовать или нет?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Виртуальное соревнование идет, вы можете стартовать

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

А теперь "Виртуальное соревнование идет, вы можете стартовать". Ну какое нахрен виртуальное соревнование?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Опять завершилось.

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Кто-нибудь пробовал начинать виртуальное соревнование? Там были условия?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please, press the "start virtual contest" button.

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

For how long virtual contest will be open?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    we'll fix the starting time for everyone on 8:00 in a few minutes

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      So everyone who started virtual contest earlier will have an advantage?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Is this not a "start virtual contest" button that I ask everyone to press on the title page?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +51 Проголосовать: не нравится

Yandex.GEOMETRY.com

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have no idea about geometry.. i could do only 1 question :(

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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";

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    accurate!

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Кто подскажет как решать А и D?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У некоторых ещё идёт виртуальный контест, так что лучше пока не обсуждать задачи.

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was in 50th test of problem A?

»
9 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

I apologise for not being able to publish analysis immediately. Hope to finish it before today's GCJ.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

в D у меня не проходить 4 тест? что за тест?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Возможно, ты считаешь общее количество треугольников? Я так считал сначала. Надо выбрать длину максимальной цепочки 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).

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

в А такое решение катит?

Переберем две маски, сделаем первый вектор — сумма всех векторов в 1 маске, и 2 вектор — сумма векторов 2 маски. Приложим 2 векторка к старту. Тогда если вектор(финиш — старт) лежит между этими 2 векторами, то ответ — ДА.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    А зачем перебирать маски? Если вектор лежит между КАКИМИ-ТО двумя векторами (или, возможно, совпадает с одним из них), и угол между ними строго меньше 180 градусов, то ответ — ДА.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Можно перебирать только пары векторов.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Достаточно просто два вектора(возможно, одинаковых) перебрать и проверить.

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    Что за магические маски. Можно перебрать два вектора и проверить, что нужный вектор — линейная комбинация этих двух с неотрицательными коэффициентами.

    (доказательство: пусть , тогда возьмём 2 линейно независимых и , пусть , будем уменьшать α3 и прибавлять β1, β2 к α1, α2, пока что-нибудь из 3х коэффициентов не станет 0. Процесс можно продолжать, пока не останется <=2 ненулевых векторов).

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I'm very interested to see tests 17, 21 and 31 for problem F. There's something strange about my verdicts.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Задача C:

  1. Выбрать правильно язык. Внезапно, Oracle Java работает в три раза медленнее, чем OpenJDK. Заодно прокачать скилл поиска нужного языка в списке, который забыли отсортировать.
  2. Повозиться с неасимптотической оптимизацией. Потому что иначе три DFS'а (по всем рёбрам, только по нулевым, только по единичным) TL-ятся.
  • »
    »
    9 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +5 Проголосовать: не нравится

    У меня зашло за 0.845s (Oracle Java 7 x64) и 0.682s (x64 OpenJDK Java 7). http://mirror.codeforces.com/contest/1/submission/11564395

    Я не писал dfs, только три dsu.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А ещё, кстати, есть 0.356s (Oracle Java 7 x32) и 0.689s (x32 OpenJDK Java 7).

      Правда тут надо быть осторожнее, x32 работает медленнее при использовании лонгов, чем x64.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Вот код, который я засылал в X для проверки. Результаты:

      • Oracle Java 8: 1.24s
      • Oracle Java 7 x64: 0.975s
      • x64 OpenJDK Java 7: 414ms
      • x32 OpenJDK Java 7: 343ms.
  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    В дорешивании зашла такая идея:

    1) Найти остов с минимальным количеством патрициев (min)

    2) Найти остов с максимальным количеством патрициев (max)

    3) Возможны все промежуточные остовы — с количеством патрициев a : min <= a <= max.

    Доказывать не умею.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Сначала пытался построить такое решение: строим минимальный остов, а затем по одному добавляем ребра весом 1. Понятно, что мы можем их добавлять по одному (просто на старом пути между соединяемыми вершинами выкидываем какое-то ребро весом 0). Ну а затем пришла идея, что раз мы можем добавлять их по одному, то достаточно найти минимальный остов и максимальный, и ответ YES для всех запросов, которые попадают в отрезок между ними.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Вот блин. Написал это на контесте, не прошло 11 тест, подумал, раз не сдают, значит не верно и бросил. Сейчас заменил прима на краскала — прошло. У кого-нибудь прима проходит?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Занятно, что ты уже рассказывал решение задачи C на страницах Codeforces три года назад.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Tests like this should have very small difference in angle:

        0 0
        1 0
        2
        1 999999999
        -1 -1000000000
        

        For this test, the answer is YES. And for the next test, the answer is NO:

        0 0
        1 0
        2
        -1 999999999
        1 -1000000000
        
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

          Better way check precision problems is to use vectors like (1000000000, 999999999) and (999999999, 999999998). Atan2 returns the same double for them

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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!

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        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.

»
9 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Is there some place I can check my T-shirt address :) to make sure it's correct?

The registration form is inaccessible now.

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

А где нужно указывать адрес, чтобы пришла майка? Я что-то не нахожу, а ссылка на электронную регистрацию не работает!

»
9 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

А кто-то, кто в сумме за 3 раунда сдал 0 задач получить футболку?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Тогда не понятно кто из них должен получить футболку, а кто нет.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится

      Можно посмотреть, кто хотя бы пытался, а не просто "мертвая душа".

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Кто больше тестов прошел XD

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          Я может как-то пропустил — а разыграли уже футболочки за участие в warm up раунде?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Да, полностью с вами согласен... Та ну просто так обидно, что отменили второй раунд, и именно в нем я сдал одну задачу,а теперь сижу и думаю , почему я так туп, что не смог в остальных раундах сдать хотя бы что-то.

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Did registration form ask address?! I couldn't remember.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

написал в D простой заоптимизированный перебор с кэшированием результатов для промежуточных вычислений. на localhost время выполнения — милисекунды на всех тестах (проверил на каждом входном числе от 1 до 1000000), но при сдаче стабильно получаю TL на тесте 17.

В чём может быть дело? Что за волшебный тест 17?

http://pastebin.com/Q8SjLie6

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Это же неправильное решение. Вы умеете доказывать, что оно быстро работает на всех тестах? В утверждение про миллисекунды не очень верится, особенно если учесть, что возвести миллион int64 в квадрат — уже не миллисекунды.

    Попробуйте например тест 967525 (это argmax размера дерева в подобном переборе для чисел до миллиона). Ваше решение работает очень долго.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

      хм, да, действительно, на этом тесте умирает. Странно, почему я не нашёл его при переборе всех входных данных. Спасибо.

      Я был уверен, что удастся упихать.

      UPD: упс, я похоже до 10^5 перебрал входные данные. незадача.

»
9 лет назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

Да здравствует король.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

27th place after 3 rounds, what a sad story :((

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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...

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Could the organizers, please, provide a way to check which address we used when we registered for the contest? Thanks!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решать B? Мне приходит в голову только следующее: 1. Найти Tmin (минимальное время, когда все колесницы пересекаются) и Tmax (максимальное время, когда все колесницы пересекаются). 2. Запустить тернарный поиск от Tmin до Tmax, чтобы найти максимум.

Tmin и Tmax можно найти идя с первого пересечения последовательно сужая интервал (очевидно, что каждая следующая колесница может только сузить интервал Tmin, Tmax). Естественно, по дороге рассматриваем крайние случаи, такие как: - одинаковые скорости у колесниц; - пустое пересечение (ответ сразу 0). Направление верное или бред?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    На плоскости (x, t) множество точек, где находятся все колесницы, является пересечением множества полуплоскостей. Это пересечение можно построить за N·log(N).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно просто запустить тернарный поиск от 0 до 1e5, максимизируя разность (со знаком) между минимальным правым концом и максимальным левым. Она выпуклая как разность выпуклой и вогнутой функции (функции выпуклые и вогнутые как максимум и минимум линейных).

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any news about t-shirts?!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Who are the t-shirt winners of Warm-Up round?!