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

Автор Sammarize, 13 лет назад, По-русски

Всем привет!

Новый, 79, раунд представляю вам я, Валерий Самойлов, выпускник СПбГУ. Сегодня вы познакомитесь с мальчиком Геральдом и поможете ему с честью выйти из самых разных жизненных ситуаций.

В обоих дивизионах разбалловка обычная: 500 - 1000 - 1500 - 2000 - 2500

Это мой первой codeforces раунд, надеюсь, задачи вам понравятся и их будет приятно решать.

Большое спасибо Артёму Рахову (RAD) за помощь в подготовке задач, Макару Краснопёрову (Connector) за несколько ценных советов, ну и, конечно, Марии Беловой за перевод.

Желаю удачи участникам обоих дивизионов!


Контест завершён, поздравляем победителей!

Дивизион 1:

1. RAVEman

2. ilyakor

3. ACRush

Дивизион 2:

1. SuperLight

2. xiaowuc1

3. Timur_Sitdikov

Появился разбор задач.

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

13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Кстати, а почему начало раунда перенесли?
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
offtop
У меня у одного CF так тормозит? Грузит страницы доолго и раза со 2го или 3го только. С другими сайтами нет таких проблем. Браузер Firefox.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня все работает (тоже Firefox).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня все нормально. Браузер такой же, как и у Вас.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В контесте так и не поучаствовал.
    Чудеса... Сейчас для прикола поставил Chrome, абсолютно те же глюки. Аватарки почти не грузятся, и страницы открываются раза со 2го-3го. Даже залогиниться не получилось в течении 10 минут (ибо Firefox перепосылает данные при обновлении, а вот Chrome, видимо, нет).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Те же самые проблемы... сайт стало невозможно лагать после "технических работ"... писал в соотв тему, но там мне тоже все отвечали мол у нас все в порядке.
      Значит все-таки я не один такой
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Да про Геральда пока контестов не было. Наверное Gerald обрадуется)))
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    а ты радовался, когда про тебя контесты были? :)
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Everybody will show his best performance in this contest.... 

Best of luck ..
:)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
интересно, что время начала, расходится для дивизионов на одну секунду)
13 лет назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

У меня косяк с головой
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вопрос - должен ли в принципе отработать посыл с открытым в начале main freopen("input.txt","r",stdin); ? Ибо каким-то образом он у меня прошёл первый тест :(
freopr
  • 13 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    Казалось бы, не должен. Но, возможно, у вас чудом оказался записан в переменных тест с таким же ответом :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Блин, и не чудом же... Хотя тест был некорректным, но ответ действительно из 1 теста на задачу :\ Мне просто почему-то казалось, что будет что-то вроде ошибки времени исполнения. Облом, надо быть аккуратней :)
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Хорошие задачи, автору зачОт. Пиши ещё ! ;-)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Easy problems even the E was easy :) Nice contest.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
и когда будет тестирование?
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится


Nice contest. :)

What is the complexity of the intended solution for problem D div 2? O(m) ? O(m*log(m))?
I tried to implement a O(m) algorithm, but maybe there is a simpler one in O(m*log(m))?

Any help appreciated!
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    There is O(m*log(m)) algorithm.
    The main idea is:
    1. If n is small, we can use DP - just calculate answer for each point
    2. Then, we understood that we are interested only in points, which are end point of some bus and our start point
    3. The last thing is to recalculate DP faster, than O(m). We have two types of events - some bus' segment is started/finished. Sort them and be happy
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for the quick reply.  Indeed each update of step 3. can be done in O(log m). 
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I did a O(m) solution using a dp array .. and it exceeded TLE .. to me it's kinda weird cause there are only 1e5 distinct states for the dp, that is not that big and I think it should have passed the system.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        You sure your complexity in O(m)? Do you visit more than O(1) others dp states to calculate one single state? If so, the complexity is bigger.
        If not, it's really weird. A lot of AC solution have complexity O(m log(m))...
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Take a closer look at your solution, it is not O(m). You have 1e5 states and you use 1e5 to  calculate the value for each state (the for in the dfs method). Conclusion: O(m^2) solution.

        Besides, I'm not a big fan of Java, but if it passes arrays around by copy, that's a huge overhead that you are not using class variables for the arrays...
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          yes you are right about the O(m^2) .. I totally missed that.

          Regarding java, I don't think it passes a new copy of the array. for objects more than the primitive data types, it passes the object as a pointer to the same memory location.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Or just scale n to O(m) and run dp.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Actually, I have trouble understanding how to do the update faster than O(m):

      Call num[t] = number of ways from the position t (a bus stop or the value 0). 
      num[max_t] = 1 and the result to return is num[0].

      the update rule at time t is:

      num[t] = c*num[next_t]

      where t is a bus final stop, and next_t is the next position where a bus stops.

      and c is either r or r+1

      with r = number of buses that start before or at t, and stop at exactly next_t.

      c = r+1 if there is a bus that starts before or at t, and stops strictly after next_t,
      c = r otherwise.
            
      I see how to get the value r in O(log m),
      but to determine efficiently whether c should be r or r+1, I'm at a loss. 
      Anyone knows? Or is there a simpler way to look at it?

      Thanks for your help.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
        The key to solving the problem is to look at it from the other side. Instead of defining num[t] as the number of ways to reach the end from position t (and then solving back to front), define num[t] as the number of ways to reach t from the start.

        With that definition, num[0] = 1, obviously, and to compute num[t] for increasing values of t, we can do:

          for each bus starting at s and ending t:
            for s <= i < t:
              add num[i] to num[t]

        Of course, we must first compress the coordinates into a range O(M) so our num array is small enough. Additionally, to avoid an O(M) inner loop, we can keep track of the accumulated sum of num[0..i]; with that, we can compute sums of num[i..j] efficiently too.

        If you can read C++, my commented solution shows the details.

        By the way: don't feel too bad about not being able to solve this one. I thought it was a pretty hard problem, despite its point value. I'm rated red here, but I could not figure this out to save my life during the contest!
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Thanks for the explanation, and the clear solution.

          It's tricky to adapt the outer loop to include the computation of num[0..i] from num[0..i-1] in O(1). 

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    There is O(m^3/2) solution that can get accept to
    idea is seperate array in to  m^1/2 array
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как решалась Е див 2?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    будет разбор, увидите.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    После перефразировки условия задачи всё более-менее очевидно:
    1. Можем прибавлять вектор C, повернутый на 90, 180 и 270 градусов
    2. В конце можем повернуть на 90 градусов несколько ра
    А далее перебираем, сколько раз в конце повернули. После этого остаётся представить вектор B-A в виде суммы C и ортогонального ему. Можно разложить по координатам и проверить, что они получились целые (разумеется, не надо считать в даблах, а просто проверить, что делится).
    Еще есть случай, когда C равно нулю (чтобы не случилось делений).
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Мой вариант - рассматриваю 4 случая (4 поворота вектора A). Решаю систему уравнений с двумя неизвестными
      xa+yb=x'
      ya-xb=y'
      x, y - координата x и y вектора С. x' y' - разница между вектором B и повёрнутым вектором A. Если b и a (неизвестные) получаются целыми - выводим YES.  По сути своей система уравнений - попытка составить вектор B-A из сложенных векторов C и C, повёрнутого на 90 градусов (отрицательные a и b - значит вектор С стоило повернуть на 180 и 270 градусов). Отдельно случаи, когда координата(-ы) вектора C == 0

      Косяк, то же самое, не сразу понял :)

      • 13 лет назад, # ^ |
          Проголосовать: нравится -7 Проголосовать: не нравится
        Надеюсь, вы не копировали 4 раза кусок кода? :)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Цикл с вызовом bool функции конечно :) Я что-то давно не писал, ну хоть таких ляпов не допустил :) Хотя контест у меня прошёл криво, пусть и на хороших задачах. Из 3 сделаных упала только A, в B полчаса убил на очевидный неправильный if, который мне стрельнуло поставить.
          (ну почти)
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Pretty fast system test it was :)
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Вот блин, писал на Е честный алгоритм с О(Н+М) памяти и О(НМ) времени, но не додебажил. А оказалось, что проходит и с квадратом памяти, деленным на константу.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня тоже не очень круто. Если поменять знаки в двух местах, то проходит :(
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Есть какие-нибудь особенности в 42-ом тесте задачи D div 1?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    ну, он на 6000+ вершин. Остальные до него меньше, чем на 1000.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I had WA on this test due to integer overflow. Be careful if you compute sum of times required to get all possible treasures, not the expected time. (Sorry for English)
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Can some one explain div2 E? I am bad at vector calculation.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    If you think about it, the vectors you can construct with the given operations are the same as those when you start with rotating A up to four times, and then adding C or one of its rotations to A.

    This is convenient, because we can just try the four possible rotations of A and subtract them from B. Then the question becomes if we can express the resulting vector with integer coordinates in an orthogonal system with C and its rotation as axes.

    So after we compute D = (B - roti(A)) for i={0,1,2,3} we want to check if there are integers x and y such that x*C + y*rot(C)=D. Since C and rot(C) are orthogonal, we can decompose D into independent components using scalar projection, and from there we can compute the value of x (or, in this case, just check if its integral). For example, x is integral iff C·D = 0 mod |C|2, where · is the dot product.

    A different approach for the last part is to write the equation
    x*C + y*rot(C)=D as a system of linear equations (C, rot(C) and D are all known) and solve that using Gauss-Jordan elimination. This is a bit more work if you don't have code prepared for this, but requires less thinking if you do.
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Спасибо за контест. Задачи понравились. Жалко правда, что С упала на том что не верно записал ортогональный вектор в СЛАУ и не смог решить D.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Not sure if this is the right place to ask, but I haven't found it anywhere... what happened to the rating graphics on user pages? I cannot see them under linux with firefox or chrome.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо, классные задачи.
Очень хреново писал. Сначала не знаю с какого потолка, прочитал, что в С координаты до 10^18 и когда наконец решил задачу, поленился писать длинную арифметику. К тому же вижу, что люди быстро решают и не на джаве, так что решил, что неправильно думаю. Потом решил Д, но во время имплементации мне почеленджили Б, в которой по глупости забыл координаты сжать. Пока ее исправлял, потерял время и не успел дописать Д :(
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Хм... А разве сжатие координат спасёт B?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну я сумматорами делал, а не деревьями как многие. Потому мне нужно было сжимать.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится
        Так оно же одним проходом за линию делается после сжатия координат. И не нужны ни деревья, ни сумматоры, ни мапы, вообще никакие структуры данных.
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Задачи очень хорошие, мне понравились.
Жаль, упала E-div2 из за пропущенной проверки при C = (0, 0) ...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как D решалась? 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Динамика по поддеревьям. Для каждого поддерева хранить надо число вершин, среднее время, за которое мы найдём клад, если клад точно где-то там, и время на полный обход этого поддерева. Потом ещё в каждой вершине надо жадно выбирать порядок обхода висящих на ней поддеревьев.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Идти туда, где сумма обхода и 2*вес ребра минимальная?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Да, но эту величину надо ещё поделить на число вершин в этом висящем поддереве, включая его корень.
        Как доказать, не знаю. Понятно, что примерно как-то так, но я сомневался, что надо брать полное время обхода, а не среднее время, если клад там. Хотя не исключено, что правильно и так, и так.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Надо же провалить задачу С на 20 тесте =(
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Ээээм..... "Рейтинг будет обновлен позже."
А если не секрет - когда и с чем это связано?
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Хм, а почему у меня в рейтинге написано что я занял 120 место, когда я занял 82?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Действительно какая-то проблема с рейтингом. Предполагаю, что взломы при подсчете не учитывались, так ли это?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      По-видимому так.
      В итоге вместо занятого 175-ого места, я "занял" 213-ое, если  судить по графику. Мягко говоря, обидно.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Какие-то проблемы, возможно, действительно есть. Мы с ними разберемся, когда приедет MikeMirzayanov.
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Блин) зарегился ). А потом засмотрелся Рубин-Динамо(Киев) в Лиге Чемпионов). В итоге когда вспомнил, уже поздно было ) успел только 1 задачку в темпе написать. И как вывод: минус рейтинг
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Даже будучи зарегистрированным, если не делать посылок в контеста, то рейтинг не меняется. Поэтому совсем опоздав, можно просто ничего не сабмитить, тогда и рейтинг не попортишь.
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Имхо, как-то странно рейтинг пересчитали. Вроде как взломы забыли учесть - у меня в профиле написано, что я занял 11-е место, тогда как реально у меня 10-е, а вот например у S.Yesipenko аж 10 мест отобрали.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Да, что-то с рейтингом не так. Мне, например, наоборот место "накрутили" - в профиле 160-е, на странице результатов - 161-е.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Памятуя о том, как автор ратовал за проведение раундов в альтернативное время, хочу его за это дело поблагодарить. Оказывается, достаточно успеть выспаться после работы до полуночи (у нас +3 часа от Москвы) - и рейтинг становится красным =)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can any one tell me if i wrong to use %lld in c++?
it should be %I64d instead in this contest ? 

i fail one prob because of this : (
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    %lld is for linux, %I64d for windows.. and codeforces sytem runs in windows..
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Actually %lld is for GNU Compilers, and %I64d for Microsoft's. And the real problem is that %lld doesn't work correctly in 4.6 GNU Compiler port on Windows, which is using here
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Really actually: it's a feature of the C library, not the compiler.

        Both POSIX and ANSI C allow ll as a size prefix, but Microsoft doesn't implement either standard.

        If GCC on Windows calls the printf() implementation in Microsoft's C library, then it probably behaves incorrectly too. The fact that it works on Linux is not thanks to GCC, but thanks to the GNU C library.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Also, Visual Studio handles %lld correctly. So if you want to submit solution which uses %lld, you can just choose MSVC compiler instead of GNU one.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yes, you can read it in FAQ and btw it's often written in problem description.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      yeah but no task in this contest which expected to use %I64d..
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        therefore it wasn't written in this contest)
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Normally when you need them it is specified on the statement.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Firstly, I wrote this round in Java, and, btw, I didn't need any long variable ( c++ long long equivalent).
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              I don't know how you solve E but my solution have to multiply somepoint and . . .  . since coordinate are in range (-10^8,10^8) so it overflow when i use integer?
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Therefore then I try to test after the contest i found that my solution fail in really small input (which is correct in my computer)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А почему у задач B, D в div2 (B в div1) ограничение по памяти - 265 мегабайт? Опечатка?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Опечатка - но при тестировании на самом деле будет 265 мегабайт.
13 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

I can't understand the algorithm for Prob E-Div2/Prob C-Div1.
why after vector A rotated,both [(B-A)cross C]%C^2==0 &&[(B-A)dot C]%C^2==0,the answer is YES?
Could anybody explain it for me? Thanks!
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    i think it's C^2?
    if  [(B-A)crossC ]%C^2 ==0 && [(B-A)dotC ]%C^2 ==0 ] answer will be "YES"

    it's because if you dot vector  AdotB = ||A|| ||B|| cos(zeta) and if you divide by ||B|| it's ||A|| cos(zeta) (which mean size of vector A (cos zeta) that parallel to B . . .   ( AdotB  % B^2) ==0 use when you want to check if ||A|| cos(zeta) %B ==0 

    in the same way AcrossB product ||A|| ||B|| sin(zeta). 
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Why should I check if |B-A|sin(zeta)%|C|==0 and |B-A|cos(zeta)%|C|==0?
      What's the intuitional meaning?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        |B-A|cos(zeta)%|C|==0 checks whether |B-A|cos(zeta) is x times as much as C ,iff |B-A| can rotate to be parallel to C. And How can I ensure that the condition can be obtained?
        And what does |B-A|sin(zeta)%|C|==0 mean?
         
        • 13 лет назад, # ^ |
          Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

          you can rotate C by 90degree and obtain C' ( rotate A and A will see that C is rotate by 90 degree)

          and vector can construct by 2 unit vector that perpendicular to each other
          ( like x= |A|cos(zeta)*i and y = |A|sin(zeta)*j in x and y axis ) and we use vector C and C' to represent unit vector so any vector construct by these should have size x time to |C| (it's (B-A) = xC + yC' (B-A)cos(zeta) = xC && (B-A)sin(zeta) = yC' )

          sorry if it's hard to read my english is not good.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Can you explain why this condition sufficient ?

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            (A rotate90) + C  is not equal to (A + C) rotate 90

            so isn't it possible that the answer is something like 
            ((((A + C) rotate90) + C) rotate90)  +C    ?

            is the approach you've mentioned check this ?
            it seems to me that it just check 
            A + tC 
            (A rotate 90)  +tC 
            (A rotate 180)  +tC 
            (A rotate 270)  +tC
            where t is some scalar
             
            I don't understand....
            thx.

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

              ((((A + C) rotate90) + C) rotate90)  +C    ?
              you have C that rotate 2 two time so it become -C 
              so we consider only C and Crotate90

              so we check
              B-A+ tC + rCrotate 90\
              B-Arot90 + tC + rCrotate 90
              B-Arot180+ tC + rCrotate 90
              B-Arot270+ tC + rCrotate 90
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                isn't (A+C)rotate90   != A+(C rotate90) ?
                suppose A = (0 , 1) C = (1 , 0)

                ((A+C) rotate90 + C)rotate90 != ( A+ - C )

                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  you right
                  but
                  ((A+C) rotate90 )rotate90 = -A-C
                  (((A) rotate90 )rotate90+C)rotate90rotate90 =A-C
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    thx for the reply. I get it though I don't know how to prove it formally for general case that rotation of "any combination of A and C"  is combination of "rotation of A" and "rotation of C"
                    thx though.
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Where is the tutorial? Is it coming soon?
13 лет назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can sombody explain Div2 Problem E-- "Vector"  more ?
Quite bad at vectors.... Thx : )
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anybody Explain algo for div2 E problem?
13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
В Алмаате писать неудобно было, с 11 до 1 ночи
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Ну а на два часа раньше, как обычно, у меня 8 утра -- тоже не удобно :о) Поэтому контесты должны быть в разное время.

13 лет назад, # |
  Проголосовать: нравится -130 Проголосовать: не нравится
  • 13 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится
    Не везёт в контестах, повезёт в любви?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It's a spam.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится
      Seriously?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится


        I think so. Let me check again. 
        Yes, I'm 100% sure.  Why do you ask?

        A little bit more seriously (sorry):  My intention was to protect the poor twits who first click without understanding the text, and then think and use Google Tranlate.
        I wish we were able to flag posts as spam, in addition to negative votes.   Where is the right place to request the feature? :)


        • 13 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится
          The only thing we can do now is ignore such posts.
          I don't think there are much people on this site that click on every link they see without understanding it.
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Как смотрите на то чтобы в начале контеста, ссылка вела не на задачу А, а на список всех задач?
Я, например, в начале каждого контеста все равно туда перехожу
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Перейти на страницы каждой задачи можно с любой другой задачи, а кроме этого на первых минутах в списке задач полезного нет ничего..
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    в этом раунде задача B была проще, чем A во втором дивизионе:) а закидывает принудительно на первую задачу
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Мое решение задачи C (div.2) не прошло тест 9. Взглянув на него, я очень удивился:

Какой может быть ответ для этого теста, если в строке "Правильный ответ" пусто и не отображена вторая строка инпута?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У тебя Runtime а не Wrong Answer.
    Рискну предположить что дело в неправильно указанной длине строки)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Но я не могу это проверить, так как не знаю целиком весь тест, вот в чем загвоздка. И строка должна умещаться, размер массива 10001 символ = 105 + 1.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Вообще-то 105=100001. Так что измени размер массива и ищи ошибку уже на 40 тесте.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
10001 символ это 10^4+1
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Когда будет разбор задач?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Сегодня вечером. Ну или ночью. В общем, через несколько часов.