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

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

Всем привет!

Новый, 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
  • Проголосовать: не нравится

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

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

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

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
и когда будет тестирование?
15 лет назад, скрыть # |
← 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!
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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
    • 15 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for the quick reply.  Indeed each update of step 3. can be done in O(log m). 
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 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.
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Or just scale n to O(m) and run dp.
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +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.

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

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

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

      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится -7 Проголосовать: не нравится
        Надеюсь, вы не копировали 4 раза кусок кода? :)
        • 15 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          Цикл с вызовом bool функции конечно :) Я что-то давно не писал, ну хоть таких ляпов не допустил :) Хотя контест у меня прошёл криво, пусть и на хороших задачах. Из 3 сделаных упала только A, в B полчаса убил на очевидный неправильный if, который мне стрельнуло поставить.
          (ну почти)
15 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится
Pretty fast system test it was :)
15 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится
Вот блин, писал на Е честный алгоритм с О(Н+М) памяти и О(НМ) времени, но не додебажил. А оказалось, что проходит и с квадратом памяти, деленным на константу.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Есть какие-нибудь особенности в 42-ом тесте задачи D div 1?
15 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится
Can some one explain div2 E? I am bad at vector calculation.
  • 15 лет назад, скрыть # ^ |
    ← 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.
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Спасибо за контест. Задачи понравились. Жалко правда, что С упала на том что не верно записал ортогональный вектор в СЛАУ и не смог решить D.
15 лет назад, скрыть # |
 
Проголосовать: нравится 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.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо, классные задачи.
Очень хреново писал. Сначала не знаю с какого потолка, прочитал, что в С координаты до 10^18 и когда наконец решил задачу, поленился писать длинную арифметику. К тому же вижу, что люди быстро решают и не на джаве, так что решил, что неправильно думаю. Потом решил Д, но во время имплементации мне почеленджили Б, в которой по глупости забыл координаты сжать. Пока ее исправлял, потерял время и не успел дописать Д :(
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Задачи очень хорошие, мне понравились.
Жаль, упала E-div2 из за пропущенной проверки при C = (0, 0) ...
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Как D решалась? 
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Динамика по поддеревьям. Для каждого поддерева хранить надо число вершин, среднее время, за которое мы найдём клад, если клад точно где-то там, и время на полный обход этого поддерева. Потом ещё в каждой вершине надо жадно выбирать порядок обхода висящих на ней поддеревьев.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Надо же провалить задачу С на 20 тесте =(
15 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится
Ээээм..... "Рейтинг будет обновлен позже."
А если не секрет - когда и с чем это связано?
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Хм, а почему у меня в рейтинге написано что я занял 120 место, когда я занял 82?
15 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится
Блин) зарегился ). А потом засмотрелся Рубин-Динамо(Киев) в Лиге Чемпионов). В итоге когда вспомнил, уже поздно было ) успел только 1 задачку в темпе написать. И как вывод: минус рейтинг
15 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится
Имхо, как-то странно рейтинг пересчитали. Вроде как взломы забыли учесть - у меня в профиле написано, что я занял 11-е место, тогда как реально у меня 10-е, а вот например у S.Yesipenko аж 10 мест отобрали.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Памятуя о том, как автор ратовал за проведение раундов в альтернативное время, хочу его за это дело поблагодарить. Оказывается, достаточно успеть выспаться после работы до полуночи (у нас +3 часа от Москвы) - и рейтинг становится красным =)
15 лет назад, скрыть # |
 
Проголосовать: нравится 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 : (
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А почему у задач B, D в div2 (B в div1) ограничение по памяти - 265 мегабайт? Опечатка?
15 лет назад, скрыть # |
← 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!
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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). 
    • 15 лет назад, скрыть # ^ |
      ← 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?
      • 15 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 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?
         
        • 15 лет назад, скрыть # ^ |
          ← 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.
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Where is the tutorial? Is it coming soon?
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -9 Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Can sombody explain Div2 Problem E-- "Vector"  more ?
Quite bad at vectors.... Thx : )
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Can anybody Explain algo for div2 E problem?
15 лет назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится
В Алмаате писать неудобно было, с 11 до 1 ночи
15 лет назад, скрыть # |
 
Проголосовать: нравится -130 Проголосовать: не нравится
15 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится
Как смотрите на то чтобы в начале контеста, ссылка вела не на задачу А, а на список всех задач?
Я, например, в начале каждого контеста все равно туда перехожу
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Перейти на страницы каждой задачи можно с любой другой задачи, а кроме этого на первых минутах в списке задач полезного нет ничего..
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

Какой может быть ответ для этого теста, если в строке "Правильный ответ" пусто и не отображена вторая строка инпута?
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +2 Проголосовать: не нравится

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