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

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

Привет всем!

Сегодня в 19:30 по Московскому времени состоится юбилейный Codeforces Round #200. Раунд будет проведен в обоих дивизионах и будет рейтинговым.

Задачи раунда подготовили Евгений Вихров (gen), Андрей Вихров (andreyv) и Геральд Агапов (Gerald). Как всегда, выражаем благодарность Михаилу Мирзаянову (MikeMirzayanov) за системы Codeforces и Polygon. Отдельное спасибо Марии Беловой (Delinur) за перевод условий задач.

В этом раунде вы поможете безумному учёному Майку реализовать его причудливые затеи и поставить необычные опыты. По мнению авторов, в задачах поддерживается хороший баланс математики и программирования. Также мы старались сделать условия задач по возможности короткими и понятными :] Как всегда, мы считаем, что каждый участник найдёт себе задачу по вкусу.

Желаем всем участникам удачи и интересного раунда!

UPD1: Разбалловка задач стандартная:

DivI: 500 1000 1500 2000 2500

DivII: 500 1000 1500 2000 2500

UPD2: Поздравляем две лучших пятёрки победителей!

DivI

  1. tourist
  2. KADR
  3. SillyHook06
  4. niyaznigmatul
  5. Igor_Kudryashov

DivII

  1. Giraffy
  2. jzc
  3. ryad0m
  4. Kamilot
  5. API
  • Проголосовать: нравится
  • +204
  • Проголосовать: не нравится

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

Посоны, я буду синим, атвичяю

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

    Ну я тогда фиолетовым=) атвичяю(с)

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

    Посоны, я тожи буду синим, атвичяю!

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

    Я — зеленым?!

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

      судя по текущим результатам несколько больше, чем зеленым :)

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

    Лол, пацаны сказали — пацаны не сделали. Это за основу взято :D

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

      А вот даже не обещал, а взял и вернулся в синие. из фиолетового)))

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

    Посоны, в следующий раз точно синим буду, инфа стопроц

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

Не будет 200 футболок?

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

I love that balance between mathematics and programming!

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

In round #100, the top 100 participants were awarded t-shirts. How nice if top 200 will be awarded in #200 and so on :-) Seriously, what will be the next round which awards the top X participants? Haha~

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

    Top 200 will be awarded in CF #200 and so on ? So after next few years Mike have to buy more than 1000 T-shirts :) What about your sons in the future when they start to compete :) I think Mike need to Open a T-shirts factory for next generation :)

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

There wasn't any surprise for this round! I was waiting a long long time for this day and CF #200! :)

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

It will be better if there are extra T-shirts for coders which behaved excellently in CF Round #200!

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

Time flies! Codeforces #100 is my first round, and now it comes to #200 rapidly.
It gives a lot of fun, hope it to be better and better.
(of course it's already terrific now, except the network speed some times... )

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

Также мы старались сделать условия задач по возможности короткими и понятными :]

Вот за это спасибо

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

I like your handle gen! MCZ Xian, a Gen user in Street Fighter 4, won EVO this year. EVO is the biggest fighting game tournament in the world. Did anyone watch it too on stream ?

Sorry for being off topic :p

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

What about awarding all participants with +/- 20% of rating. If their rating is going to increase, increase it 20% more and if it is to be decreased, decrease it 20% less :-D

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

    Rating changes are irregular in a way — even if you get the same place, the rating change depends on the others who compete (your 'relative place'). So that'd be hardly noticeable.

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

А а а... футболки?

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

Интересно один я думал что в этом раунде не будет футболок.

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

Which Mike is he? :D

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

So which is the score distribution? :-"

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

and score distribution ??

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

Nice problem set linking science with coding :) !!

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

cf was unavailable for long time. time should be increased.

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

my code in mingw32 output correct answer but here ,cf said wrong answer!!!:| why?

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

    different compiler may result in a slightly different result. Or may also happen when u compile using windows or linux. maybe u should post your code so we could check what is wrong with it?

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

Как решается С(div.1)?

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

    Я решал с помощью бинарного поиска по ответу

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

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

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

score distribution was so wrong

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

Кто-нибудь писал в D div 1 sqrt-декомпозицию?

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

Задача на дерево Гомори-Ху на контесте КФ. Огонь!

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

    Гомори-Ху FTW!

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

      У вас отсекаются решения за квадрат поисков потока?

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

        Возможно, что такие решения пройдут, всё-таки надо было большие ограничения ставить. :/ Структуру нам подсказал Gerald, и мы вместе придумали задачу на этом дереве.

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

One of the best contests I ever participated on CF. Less to code more to think :)

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

Один из лучших раундов. Особенно div2 задачи.

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

правда ли, что в претестах D div 2 ответ был только Yes?

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

I loved the round and absolutely loved the problem statements and setting 5/5

How could I approach problem C efficiently?

I only managed to deduce a formula for some special cases... If anyone could give me some tips that would be great :)

Thanks,

Bruno

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

    f(a,b) = a/b + f(b, a%b);

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

      But this might fail according to this

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

        Good catch. (fortunately it passed according to given scenario)

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

        The question permits only a.)one resistor; b.)an element and one resistor plugged in sequence; c.)an element and one resistor plugged in parallel.

        so u only can add one resistor at a time to the existing element. (u cannot add two elements)

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

    solve (a, b) = (b / a) + solve (min(a, b % a), max (a, b % a))

    and solve (0, a) = 0;

    Explanation: you assume that b >= a, then you will take (b / a) resistors for taking in series with other resistors, so cost (b /a) for those resistors.

    For remaining you need to use 1 and x in parrallel which is a / b = x / (x + 1). which means x = a / (b — a).

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

Расскажите, пожалуйста, а какой ответ на тест в задаче 343A - Рациональное сопротивление:

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

    у меня 15.

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

      Ох я тупанул, там же "элемент и один резистор".

      А я решал для "элемент и элемент".

      И на этом тесте тогда получается 13.

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

        Ой я тупанул :) вроде все верно решил :)

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

        Как решать такой вариант задачи? Когда можно присоединять не только один резистор, а целый элемент?

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

          Я не знаю, я сразу написал наивное решение, долго думал. Потом от безысходности решил заслать, как потом оказалось, правильное решение. Зашел в комнату, первый же человек, понятно, был с таким же решением. Решил взломать — неудача, решение вывело 15.

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

    15 пишет.

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

    Да, и вот, например, на тест 6 5, правильней ответ будет 5, а не 6, как у многих, кто уже получил AC (параллельное соединение из 2 Ом и 3 Ом) http://puu.sh/4raj0.png

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

      В условии чётко прописано, что параллельно подсоединять можно только схему и резистор в один Ом, а не любые две составные схемы из резисторов.

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

    А почему в задаче A div 1 правильный ответ на тест 6 5 — 6. Ведь можно расположить 2 резистора сверху и 3 — снизу. Получим 1/ (1/2+1/3) = 6/5. Или я в чем-то ошибаюсь?

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

      Ответ чуть выше.

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

        Да, я потом заметил. Просто долго писал, а удалять вроде нельзя

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

Cпасибо большое за раунд!

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

In Div1, problem A, in my room, I saw two people use %lld to read or write 64-bit integers in c++, so I hack one of them, but unsucessful. Does it mean is using %lld to read or write 64-bit integers is no longer banned? Maybe next time, the warning "Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier." can be removed.

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

    %lld was never banned. It is just recommended to use %I64d due to historical reasons. With modern MinGW %lld seems to work as well.

    The warning cannot be removed as some people could be using old compilers on their own Windows computers, and then wonder why %lld does not work locally.

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

    I think that means "there exists at least one number when %lld will read not exactly the same as %I64d will under some compiler" rather than "it will always read wrong". So maybe you just didn't guess with hack :)

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

E can be solved by using Gomory-Hu algorithm. It takes the graph and in O(n * flow time) computes a tree such that maxflow from a to b is the minimum weight of an edge on a path from a to b (at first glance one can be amazed that such a tree exists but after some thought it makes sense). So we just have a tree and have to find a permutation that maximizes sum of the lightest edges on paths v_i -> v_{i+1} Answer to this problem is sum of weights of edges in such a tree. Just take the heaviest edge and use divide and conquer algorithm.

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

А мне может кто-нибудь объяснить зачем в D 500000? Чтобы опять любители Java шли лесом?

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

    Чтобы отсечь корневую?

    Разобьемся на блоки по операций. Каждый блок обработаем за линию целиком. Осталось учесть влияние внутри блока. Это делается за запросов является ли a предком b.

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

      Нельзя один блок за линию отработать, там порядок выполнения важен. Это можно как-то обойти?

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

        Как так нельзя. За линию находим самое позднее опустошение в каждом поддереве, за линию самое позднее наполнение из предков и сравнили?

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

          Наверное, голова сейчас вообще не варит ;D

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

    Были опасения, что пройдут какие-нибудь корневые эвристики. Вообще-то, наше неоптимизированное решение на Java работает две секунды, поэтому мы посчитали, что 4 секунды разумное ограничение.

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

      Мне кажется, что в этой задаче любые корневые эвристики написать сложнее, чем правильное решение. Я верю, что С++-style Java решение может работать довольно быстро даже без оптимизаций, но это же не повод

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

        Ну по ощущением, то что я описал выше, будет где-то в два раза короче по коду. И придумалось раньше лично у меня.

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

      Еще хотелось бы отметить — 2х для АСМ — нормально. 2х для подобного формата — годится только если есть макс тест в претестах. Возможно это стоит даже отдельного топика для обсуждения

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

Nice problemset!

Especially for problem E, the solution is quite simple (maxflow-mincut theorem) but it's hard to think in that way. :)

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

    Thanks; the intended solution was to use Gomory-Hu tree, as Swistakk explained earlier.

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

      I see. That tree can be easily obtained by analyze it in this way:

      Suppose X-Y is a minimal cut of graph G. Then:

      • If x \in X and y \in Y then flow(x, y) = cut(X, Y)
      • Otherwise, it will be no less than cut(X, Y), we focus on nodes only in X and only in Y, so we split S into X and Y.

      Then we focus on X and Y and do the same thing.

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

        Exactly. That's how Gomory-Hu works :). But it's not straightforward to prove that these bounds are really the best ones.

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

          Frankly saying, sometimes I really don't understand people's reasoning regarding to rating comments. I described solution to E and gen replied "Intended solution was as Swistakk explained" and got more pluses than me and few posts below cgy4ever explained Gomory-Hu algorithm and I said "yes, that's how Gomory-Hu works" and I got more pluses than him :P.

          EDIT: Note that ratings I am reffering to may vary. When I was writing this comment cgy4ever's comment got +5 and mine response got +8, but now he has got +16 and I still got +8 :D.

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

            It's even weirder when there are 2 comments below each other, both saying something along the lines of "good luck", one of them is rated around -50 and the other around +50. The only reasonable explanation is heavy trolling of some comments.

            As for me, I usually vote minus on "spam" comments (those that only contain one of the usual phrases related to contests etc.), plus on comments that contribute something to me or are well written (that, of course, requires the comment to talk about something useful, meaningful) and for comments that are just random short replies or I'm unsure of how to vote, I don't vote at all.

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

              Last Wednesday i took 10 random new neutral comments with 0 votes each, upvoted random 5 of them and downvoted other 5. In 12 hours first 5 had +2, +11, +5, +4, +8, and second 5 had -9, -5, -8, -3, -4 respectively. Funny, isn't it?

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

                Yeah, that's one type of trolling. Just voting the more common option. Voting randomly is another common type. (In general, trolling is anything that isn't based at all on your view of the content.)

                Not like we can affect it, anyway. And when one has large contribution, it starts only depending on blogs — comments have much lower weight, so unless you're getting like +50 or -50 for one comment, it doesn't affect contribution at all...

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

Первая красная точка! Спасибо авторам!

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

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

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

    В качестве полумеры можно встраивать генератор внутрь решения.

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

      Можно конечно так, но, во-первых, для этого еще что-то надо писать (и не забыть удалить), а во-вторых, чтение, например, 106 элементов (int-ов) занимает у меня 0.3 секунды, что немало

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

Rating update was quite fast! :)

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

Can anyone tell me why this code fails on time limit ? (Div.1 Problem C)

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

Большое спасибо, за удачный контест!!!

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

We want T-shirts : )

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

физика доминирует

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

Почему нельзя разложить третий тест (199/200) задачи DIV2-C на: 1/50 + 1/40 + 1/5 + 1/4 + 1/4 + 1/4?

Соединить параллельно круга на 50, 40, 5, 4, 4, 4 резисторов. А потом их соединить последовательно? И того потратить 50 + 40 + 5 + 4 + 4 + 4 = 107 резисторов. Подскажите пожалуйста где у меня ошибка?

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

    Потому что разрешено добавлять только по одному резистору, нельзя склеивать любые два элемента. В условии мы это подчёркивали как могли (; А общая задача, наверное, решается достаточно медленной динамикой.

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

      А я сколько раз перечитывал, так и не понял... обидно

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

    Согласно условию, последовательно (как и параллельно) можно соединять только элемент и резистор.

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

Any hints for Problem D div2 ?

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

    My solution is prolly the easiest, though longer than optimal, to understand. I use linked list and remove ++s and --s http://mirror.codeforces.com/contest/344/submission/4465292

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

      You can just use a stack and assign digits for + and -. Let's say '+' is 1 and 0 is '-' . Then you can do the following:

      If current character's code(0 or 1) is the same as the stack's top, then pop, otherwise push the code in the stack. Then, if the stack is empty the answer is "Yes", and if it is not, the answer is "No". Here is my solution 4464633

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

i realy like div1 problem D , i think range assign with segment tree is not intended solution , is it?

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

    It is actually, the core of the solution is to color some whole original tree subtrees in logarithmic time.

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

The contest was very specific! It was about any kind of science: Chemistry, Physics, Math, ... . gen was right. It had questions for any tastes. :D

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

Is 21/10 a valid test case for Problem-C (Div.2).....?

acc. to me (7) and (3) in parallel results in (21/10) which equals to 10 resistors minimum. But acc. to AC soln's. ans = 12.

Pls clarify!!!!!!

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

    You cannot combine 7 and 3 in parallel. According to the question, you can combine an element with just one 1 ohm resistor. Hence, combination of two elements in parallel in not permitted.

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

    And 6/5 is also a wrong case. We can use (2) and (3) to get it: 1 / (1/2) + (1/3) = 6/5. So the answer should be 5, not 6.

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

      You should read the statements more carefully.

      There are only two types of combination:

      1) x -> x + 1

      2) x — > 1/(1/x+1/1)

      There is no x,y -> 1/(1/x+1/y)

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

What a great contest, I really enjoyed it...

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

I tried to hack this solution on test case "++++" because of the intermediate state (s[2] == s[-1]), but no runtime error, why?

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

    Well, since it's not Pascal with its range checking for everything, he just access whatever byte is before the char array. It is most likely accessible to the program (hence no segmentation fault) and since we have no idea what's in there, it can only possibly affect the code if there is '-' or '+', meaning that in at least 127 out of 128 cases it will run just fine.

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

What I liked about this round was that the problems were more connected to the real world than usually. Solving them almost felt like doing some actual work:) Way to go, gen!

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

I became red and feel very happy!!! And first I solved 4 problems. Div1 D was very very cool problem! (I could answer the different types of queries by using the same euler-tour array!!) That should be one of my most favorite problems!! Thanks for writer.

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

Where can we get an Editorial for this round?

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

I think no one wrote about the solution of Div1 D, so I write it.

third query can be said, "which was the last operation, adding water to the ancestors of the node, or emitting water from the children of the node?".

So we want to calculate two values -- the time of last operation no.1 which added water to the ancestors of the node, and the time of last operation no.2 which emitted water from the children of the node.

Both queries can be done with the different segment trees to the array of Euler-tour.

So we can solve this problem in O(Qlog N).

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

    not O(Qlog N) , O(Qlog NlogN)

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

      This can be solved in O(Q log N), but I know another solution whose order is O(Q log^2 N). (Actually I found this at first, but I thought it is too slow to get accepted and too hard to code, so I tried to find another solution.)

      In this solution, we can use heavy-light decomposition or the general technique of merge the data structures like std::set.

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

The problems were interesting! I liked them!

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

Hello,

Anyone has any tips about Problem E for Div. 2?

I am totally clueless about it and still trying to grasp logic of problems C and D...

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

    Hint for problem E Div. 2 (Read Time):

    Try binary search the answer. For particular time T you have to determine if it is possible to read all tracks (p1..pm) in time T.

    Another hint:

    • There exists an optimal solution where heads don't change their relative order.
»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

What a nice tag for the blog post :) "everybody reads tags" Thanks for the laugh!

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

I think there is an issue with Problem 343A — Rational Resistance. Here according to the editorial the answer to the ratio 6/5 would be 6(I have verified this with an accepted solution). But this ratio can be achieved with a resistance of 2 and 3 in parallel, which makes the number of resistors required equal to 5 which would imply the editorial and the system tests to be wrong.

Am I missing something here?

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

    you cannot put resistance of 2 and 3 in parallel.

    According to the problem statement you can only put Ro and Re in parallel where Ro = 1.