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

Привет, Codeforces!

В 05.09.2019 17:35 (Московское время) состоится Educational Codeforces Round 72 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Привет, Codeforces,

Университет Harbour.Space совместно с UTCC (Бангкок, Таиланд) предлагает уникальные стипендии для обучения по магистерским программам.

Наша цель устранить какие-либо финансовые барьеры для талантливых студентов: стипендии покрывают 100% оплаты за обучение, а также расходы на проживание, и, кроме того, они предоставляют студенту ценный опыт как обучения, так и работы в Harbour.Space University.

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

Подать заявку→

Поздравляем победителей:

Место Участник Задач решено Штраф
1 Tropical_maid 6 212
2 Return.Hao 6 246
3 xyz100 6 272
4 YangDavid 6 280
5 Lawali 6 300

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 VegetableP 116:-14
2 Princ_iple 49:-1
3 racsosabe 42:-1
4 shurongwang 36
5 Megatron_99 29:-1
Было сделано 1432 успешных и 1595 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A xyz100 0:02
B talant 0:06
C Laiu 0:06
D IgorI 0:08
E Umi 0:30
F Hasan0540 0:51

UPD: Разбор опубликован

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

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

Thanks for round! :)

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

:(( a funny picture. but -64 downvoted. :(( sorry i deleted it

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

    Two funny images, why so heavily downvoted?

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

      i don't know :(( Why??? i tried with funny comments. but -44 voted? :D what the f* ?

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

      i think that i will not write a another comment :(( So sad..

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

      because this is codeforces not memes center.. jokes here needs right timing so posting some joke before the round starts is not a good idea unless you're legendary grand master even if you write "potato" you'll get upvoted

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

funny picture always got upvote

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

Would anyone be interested in a round written solely by tourist?

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

Two rounds in two days, the later one must be a good round...

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

Seems like Codeforces wants me to give this contest as a rated one

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

Hope this round will be like last educational

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

[deleted]

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

I want to know if I will lost some rating if i dont have time to join this round.....

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

    Certainly not. You will not be considered as an official participant if you don't even make a single attempt.

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

Ееее, Пикмайк крутой

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

What will be the difficulty of the problems? I have just started with cp.

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

Hopefully I can gain more rating!

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

Wanna become blue today...

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

when can we upsolve the problems?

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

For E my time complexity was O(q*digits*log(n)) which got TL-5. How to do it better?

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

    Use int instead of long long

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

    My submission 60129750 got 1497 ms (complexity is the same)

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

    the shortest form of this problem: give you number Heads, list of blows and answer the fastest way to kill it (Heads<=0). There are 2 cases here: Result=1 and Result>1. When Result=1, you just simply pick the blow with the biggest damage value. When Result>1 (2,3...), you will notice that the moment the dragon die is before the the last rivival (Heads increase again) and number Heads become not positive so the last revival will not happen, If you have Result number time of blows, obviously, first Result-1 time you will change Heads by sum of (-damage+rivive), but for last you just change Heads number by minus damage value. So with case Result>1, you just simply pick the blow with the smallest (-damage+revive) for first Result-1 blows, and the last blow you just need to pick the blow with the biggest damage to end the fight. Hope you get it. I also struggled a lots to find out this logic, simple but hard to make it right in the center quickly. EDIT: So sorry, I made a mistake. I saw something about problem B so... Forgive me

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

    I think it's because of digit function in your code. I think it's $$$O(q*digits^2*log(n))$$$ in worst case.

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

    I also had the same complexity https://codeforces.me/contest/1217/submission/60133014 got tle at tc5.. can anybody tell why?

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

      I think it might be due to that combining nodes function(ret in your code). I had same merging function but also extra digit factor in complexity so it got well deserved TL.

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

    I got 1.996s on pretests and didn't realize lol.

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

How to solve problem F ?

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

    $$$last$$$ can only be $$$0$$$ or $$$1$$$, so we can make $$$2m$$$ operations and do them offline.

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

      Is there a solution which can handle these types of queries with divide-and-conquer dynamic connectivity method?

      I know it's a strange thing to ask since I am one of the authors of the contest, but nevertheless.

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

        Assume there are $$$n$$$ vertices, $$$m$$$ edges in graph $$$G$$$, and we need to process $$$q$$$ operations.

        1. Let's denote all the endpoints in these $$$q$$$ operations as important vertices.

        2. Keep all the edges not mentioned in these $$$q$$$ operations in $$$G$$$, and run a linear DFS to find all the connected components.

        3. Remove all the components that contain no important vertices, since they are useless for these queries at all.

        4. Compress each component to a single vertex, and remark all the operations. Let's denote the compressed graph as $$$G'$$$.

        5. Process the first q/2 operations using $$$G'$$$ recursively.

        6. Now we know all the answer of the first q/2 queries, so we can know what the real modifications are. Do these modifications to get a new graph G''.

        7. Process the last q/2 operations using G'' recursively.

        Time complexity is T(q)=2T(q/2)+O(q)=O(q log q).

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

      But how? I don't really understand.

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

        I think I actually got it, how to use the segment tree trick with DCP in this problem.

        For each edge, there are multiple segments where it may or may not be present (its status may change when we make a query of first type with $$$x, y$$$ or $$$x - 1, y - 1$$$). Let's add these segments in the segment tree just the way we did it in original dynamic connectivity problem, we will have no more than $$$q \log q$$$ additions into the segment tree.

        Then, while we are running DFS in the segment tree, we firstly go into the left subtree, solve the problem recursively. And after we processed all queries from the left subtree, we now know everything about all edges we could add in our right son — this is the key point that allows us to use this approach.

        Originally, when HellKitsune taught me the divide-and-conquer technique to the dynamic connectivity problem, I was a bit disapponted that the sqrt-decomposition trick is kinda useless in this problem — it is harder to code, it runs slower. So I wanted to create a problem that would show that sqrt-decomposition could still be better than divide-and-conquer in some cases of DCP. It turns out I failed.

        But the sqrt-decomposition solution for this problem is much easier. Divide the queries into $$$K$$$ blocks. For each block, we know some edges that are always present no matter what, and each query asks us to use no more than $$$\frac{2q}{K}$$$ edges that may not present in the whole block.

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

      can you please explain a little bit more?

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

      I don't understand. Since $$$last$$$ could be 0 or 1 on each query, doesn't that mean that in total there are $$$2^m$$$ possible chains of operations?

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

        Yes, we can have $$$2^{m}$$$ possible chains if we are trying to do it purely offline. But offline dynamic connectivity approaches can be modified in such way that we do not need to know all the queries beforehand. Instead of marking places when edge inclusion changes, we can mark places where edge inclusion might change and when we will have all the information make these decisions in process whether to include edge or not do include edge for future stable segment until this edge might change again.

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

    u can also solve with using dynamic connectivity

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

      There's no such thing as online dynamic general graph connectivity as far as I know :<

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

        Fuck, i forgot its online queries xd

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

        There is one. It involves some really heavy magic with Link-Cut Trees.

        Some accepted submissions use that approach.

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

          Ok, looked it up. I bow to thee BledBest, I can die at peace, even as a unicorn I'm still totally mindblown by such magic.

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

          It is called HDT algorithm. It was named after it's inventors Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup. Time complexity is amortized $$$O(log^2n)$$$ per update and $$$O(logn)$$$ per query. There is also an implementation using Euler Tour Trees instead of Link-Cut Trees.

          The best known algorithm for online dynamic connectivity problem runs in amortized $$$O(\frac{log^2n}{loglogn})$$$ per update and $$$O(\frac{logn}{loglogn})$$$ per query using Thorup's randomized data structure.

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

getting WA on test 2 in B, whats is the logic or tell me something wrong in my solution please.

link of my solution

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

    if all d < h and has no d >= x — result -1

    next chose a=max(di-hi) and b=maxd, last step max(a,b), all steps before last (b)

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

    the shortest form of this problem: give you number Heads, list of blows and answer the fastest way to kill it (Heads<=0). There are 2 cases here: Result=1 and Result>1. When Result=1, you just simply pick the blow with the biggest damage value. When Result>1 (2,3...), you will notice that the moment the dragon die is before the the last revival (Heads increase again) and number Heads become not positive so the last revival will not happen, If you have Result number time of blows, obviously, first Result-1 time you will change Heads by sum of (-damage+rivive), but for last you just change Heads number by minus damage value. So with case Result>1, you just simply pick the blow with the smallest (-damage+revive) for first Result-1 blows, and the last blow you just need to pick the blow with the biggest damage to end the fight. Hope you get it. I also struggled a lots to find out this logic, simple but hard to make it right in the center quickly.

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

How To Solve C..?

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

    How to solve C with out gettin TLE on test 12 ??????????

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

    First of all, if at a given index, s[i] == '1', then the index of the last good substring starting at i is at most (i + 20), otherwise the value of the binary number is larger than the max length of the string. So, for every index, we precompute the next occurrence of '1' and check the next 20 characters. Repeat.

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

      i still don't understand about this one i is at most (i + 20), could you explain why the last good substring starting at i is at most (i + 20) ?

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

        Because a binary number with length 20 and no leading zeroes is at least $$$2^{19}$$$ which is greater than the maximum possible length of the string so it can never be valid.

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

    my solution:

    precalc zeroes-array: how many zeroes before ith element

    next start from first (1) and count zeroes before (from precalc), if (f-length<=number of zeroes) result++. next shift left index to next 1-characker, if length > 20 (i think it is enough) you can break from cycle.

    (for example 000101)

    first step: 000[1]01

    number of zeroes before before = 3, f=1 and 3 enough to add to result (1-1<=3)

    next step go to 000[10]1

    in this case your f=2, length=2, zeroes before=3 => result++

    next step got to 00010[1] — same as first step (except zeroes before = 1, but also enought 1-1<1)

    next step got to 000[101] — f=5, lenght=3, number of zeroes = 3 (5-3<=3) => result++

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

      Thanks a lot! Nice solution, really easy to code.

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

      Good explanation.
      I upsolved in similar maner using regex, where zeroes-calc are made on the fly. Solution in Perl is quite slow, it passes in 3.6s — 60140161. Regex finds every position starting with '1' and then looks-ahead upto 18 bits.

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

      How do you get the formula if (f — length <= number of zeroes) then result++ I mean logic behind it

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

        f — function result that we needed to achieve (for example for 111 = 7)

        length — already achieved length (for 111 = 3)

        good substring when f == length

        it is obviously that we need to add some (may be 0 zeroes) leading zeroes for case when f == l, and if for your suffix of substring which has no leading zeroes can be added some leading zeroes to case when f == l you can increment your result.

        You can check first numbers

        1 = 1 (f = 1, l = 1)

        2 = 10 (f=2, l =2)

        3 = 11 = 011 (f=2, l=2, need 1 leading zero)

        4 = 100 = 0100 (f=4, l=3, need 1 leading zero)

        Sorry for my english, hope you understand

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

how to solve A? hahahahaha

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

How to solve D?

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

    Colour every back edge as black and the remaining edges as white. Since any cycle cannot contain all back edges, hence we cannot have a cycle containing all edges of the same colour.

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

    If there is no cycle, answer is 1. Otherwise paint an edge $$$(u, v)$$$ white if $$$u < v$$$, else black.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится
    • If there is no cycle the answer is 1
    • Else you can use one color for the edges u->v where u < v and another for the edges u->v where u > v so the answer is 2

    To find if there is a cycle in a directed graph, you can do a DFS marking differently vertex currently treated and vertex you finished treating. If you encounter a vertice still in treatment, it means it's an ancestor in the DFS and you have a cycle.

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

    Incoming and outgoing edges colored differently ensures this. Question: Does Upper bound of 2 also hold for undirected given no multiple edges?

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

      For undirected graphs, the edges of one color form a tree so atmost $$$n-1$$$ edges, but the graph can have $$$\frac{n(n-1)}{2}$$$ edges so it is clear the bound of 2 will not hold.

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

    How to solve D if it is a undirected graph

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

Anyone who used binary search for A?

I am a bit nervous about my approach..

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

    You can check my solution, where I used binary serch.

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

    I also used binary search

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

    I also solved using binary search.

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

    me too,binary search is more intuitive than pure math equation to me

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

    No need for binary search, see my O(1) solution — https://codeforces.me/contest/1217/submission/60107664

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

      I did realize that O(1) solution exists, but for some reasons I thought that it would have more number of cases, hence more chances of some edge case failing.

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

      Problem A 60157777

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

        could you explain how you approach the problem?

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

          (y+z) — maximum int (int+exp) that can be achieved

          (y+z)-x — difference maxInt — minStr that can be achieved

          ((y+z)-x+2)/2 number of points that we can get from int, and add to str for cases when str <= int (each point from int to str make difference less on two points), if this value < 0 it means str always > int

          i think its better to write right+1 (z+1), because there is (exp+1) options to distribute exp points (you can add from 0 to exp points to str) result = (exp+1)-left > how many options for distribution we have (for cases when str > 1)

          if result <= 0 there is no options => print 0

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

    not much work just find range [lb,ub] and ub-lb+1 is answer.a,b,c is input. x>=a and y>=b and x>y and x+y=a+b+c always which leads to x ranges from max(a,sum/2+1) to sum-b,now range difference are your total solution.

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

Anyone has a solution for problem E with 10*(3 of segment queries) per query passed ?? Is it intended to pass or not ?

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

    I did the same thing got tle

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

    I am very very sad that my solution got accepted now (after the contest) just by using this implementation of segment tree.

    So sad, that the implementation of the segment tree played a role in getting accepted for this problem. Was this intended ???? and why ??

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

      my solution with few changes got accepted.. 1) changed long long to int 2) instead of cout/cin fio using scanf/printf 3) optimized ret function

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

    I think you can do 1 query (but complexity remains the same). Just store two minimums for each digit. Constant will be much better than 3 * 10 separate queries.

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

how to pass test 2 problem C

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

what is the hack for B ?

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

    i think alot of people checked for case where highest damage is more than number off heads but did not check when that it equal.

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

      nope i got hacked on that one i checked first max difference <= heads return -1, i got hacked there , test cases were pretty weak.actually i didn't check max damage>=head count.most people solution is failing on that.

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

    hacked 6 people with the same test case, one candidate master :)-

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

how to solve E?

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

I think I am not able to tell how fucking annoying it is to not get A right for an hour or more...and then miss C for like 5 minutes.

What was so hard with A, why did I need 10 submissions?

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

I hope there is a simple solution for F. My solution is too complicated.

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

"It is guaranteed that each ordered pair (u, v) appears in the list of edges at most once."

What is mean ordered pair in problem D ?

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

In $$$E$$$, what is the best way to know the smallest $$$2$$$ numbers between $$$L$$$ and $$$R$$$ such that they both have a non zero digit at a same position?

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

    I didn't have enough time to submit, but my idea is to build a segment tree for each digit. I planned to fill them in the following fashion: if $$$k$$$-th digit of $$$a_i$$$ is not $$$0$$$, then we put $$$a_i$$$ on place $$$i$$$ in the $$$k$$$-th segment tree, else some huge constant. To get the answer, you could take two minimums on each tree and choose the one with minimum sum.

    Should pass in time, pure $$$O(n \cdot logn)$$$, albeit with a considerable constant.

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

      Thank you.

      I think the complexity should be $$$O(n*log_{10}(max\,value)+m*log_{10}(max\,value)*log_2(n))$$$. Where the term before $$$+$$$ is for trees builds, and the other is for queries.

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

    for each position, build a segment tree, for each segment, maintain the smallest and second smallest number which both has non-zero digit in that position

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

    For some reason I was thinking during the contest about maintaining something like merge sort tree for every digit position instead of just a normal segment tree through which you can get 2 minimums, and simulate non-existing numbers by large constants. Thanks all.

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

hack successful test for problem B?

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

I did problem C in O(N*logN*logN). Any better solution?

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

    My solution ~ O(N): https://codeforces.me/contest/1217/submission/60132911 if you want to tutorial, inbox for me.

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

    A good substring starting with '1' can be only '1' or '10' (the ones with length $$$x$$$ > 2 are at least $$$2^x$$$ and thus larger than $$$x$$$) — these can be checked with $$$O(N)$$$.

    If a good substring starts with '0', there can be at most one good substring starting at given index (if it is of length $$$x$$$, and equals $$$x$$$, then already the next one will equal at least 2x > $$$x+1$$$). To find these for every given index, you can enumerate possible lengths (length can be from 2 to log2($$$2 \cdot 10^5$$$)), starting from the nearest following '1'. This is $$$O(NlogN)$$$.

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

Самый сложный A за последние раунды.

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

This is such an obvious hack case for problem B, I wonder why it wasn't in the pretests??

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

very bad pretests for B((

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

indeed a great round at hackforces...

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

Poor testcases :(

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

Problem B: What is the output for this input. 1 3 999999911 3 1 11 1000000000 10 9

Jury's answer is 499999951. How ?

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

    Hit em with (3, 1) 499999950 times, finally use the (11, 10...) to finish it. Are you suggesting there's a solution with fewer hits?

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

Looks like CF managed to automate Problem Setting

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

The most wrong answer contest I have ever seen hahahahaha.

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

How to Solve D??

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

    If there is no cycles in our graph we can simply use $$$k=1$$$.

    For all other cases we can be done with $$$k=2$$$. Suppose we have edges in form $$$(from, to)$$$, we can paint all edges with $$$from < to$$$ into color $$$1$$$ and all edges with $$$from > to$$$ into color $$$2$$$. If we arrange all vertices of our graph into a sequence, edges that go left are of one color and edges that go right are of another color. Any cycle must start and end in the same vertex, so after making a first step left or right we need to move backwards, but we can only do it with edges of another color.

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

Man, I got like 11 WAs on Problem A, and still couldn't solve it. I used this equation :- str + x > int + y && x + y == exp , then finding all possible values of x and y. Can someone provide a clear implementation for this, i think i messed up in calculating the number of solutions.(or are these equations missing something?)

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

    If exp + strength <= Intelligence , then there's no solution, answer is 0.

    If exp + Intelligence < strength , then all combinations will work, the answer is exp + 1.

    If exp + Intelligence = strength , all combinations except (strength, intelligence + exp) wil work , answer is exp.

    now for the last case, the minimum exp that can be added to strength without disturbing the inequality strength > intelligence is the solution to:

    Let x be the minimum exp required.

    (strength + x) — (intelligence + (exp — x)) = 1

    x = ceil((1 — strength + intelligence + exp) / 2)

    the answer is exp — x + 1

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

      Thanks mate!

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

      you could solve it pretty obviously.S,I,E is input. now we know that X>=S and Y>=I and X>Y,constraints X+Y=S+I+E=sum => Y=sum-X substituting value we get boundary of X i.e., X belongs [max(S,sum/2+1),sum-b] hence final answer is R-L+1. you could look at my code its just 4 lines. code

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

https://codeforces.me/contest/1217/submission/60110076

Please Hack this, this is surely not O(N)/O(NlogN) .

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

Honestly, Educational rounds are not as interesting as they once were.

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

    Why not to say it from your real account, not fake one? Are you afraid of downvotes? Or afraid of us?

    P.S.: I'm not arguing about the statement itself, just about people who can't honestly state their opinion.

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

Problem A was harder than Problem B :(

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

Очень слабые претесты на задачу В. Неужели нельзя было посильнее сделать?

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

Please give me a test case on which my solution fails:)

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

When I first saw this 1000 liner code, I thought, is this the end of the universe?

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

    Isn't this code very similar to this code: 60123155? Even the strangest of variable names like ee, uuu, vvv, te, etc., in the main code or just before it are the same.

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

      MikeMirzayanov, awoo can u please check. I believe intentional efforts have been made to avoid plagiarism, like performing n = N, when there was almost no use of doing it, and also statements like if(op == 2) op = 2

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

        The order of some of the statements or expressions has also been intentionally swapped.

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

          No, it's not. If you look more carefully at my previous submission 60108293, you will see that I have marked “template from https://loj.ac/submission/25943” as comment on the first line. Actually this problem is almost exactly the same as this one on LOJ, except some I/O format and the way of forcing online. So I copied a public submission on LOJ and changed it a little bit to pass this one. According to the rules about third-party code, it's ok to do so, and I believe Return.Hao just copied from the same template.

          Reporting cheating is good, but I'd like to say you had better check more things out before you make your report.

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

            I am extremely sorry for this. I checked the last submission only as they were the ones that would've contributed to the final results and found no attribution on them, and as I said in my previous comment, a few of the statements only differed in a very suspicious way like the case of doing n = N as I mentioned above. That's what made my doubts more concrete. That's why I thought it was a cheating case. Sorry once again.

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

Can someone explain me how to solve C please?I dont understand the idea of this problem.

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

    First let's preprocess the array z, such that:

    z[i] = number of zeroes to the left of i before the first 1.

    For instance:

    v: 0 0 0 1 1 0 1

    z: 0 1 2 3 0 0 1

    What the problem wants is the number of substrings s[l..r] such that the binary number in s[l..r] is equal to its range size r - l + 1.

    Now let's say you're currently at index i and s[i] == '1'. You've already got your first answer, right? because s[i] == 1 and the range size is 1. Let's call our current value X and keep constructing new numbers using substrings that start in this index i and end at some index j (s[i..j]).

    Notice that j < min(n, i+20). Because the maximum range size possible is 2*10^5 and you need less than 20 bits to construct that value.

    Now let's add the next bit (at j'th position) and calculate our new value X, if the next bit is 1, X = 2*X + 1 and if the next bit is 0, then X = 2*X.

    So for this substring to be good, we need it to have size X. Since we started at i and we're now at j, its size is currently j-i+1. But remember we have z[i] zeroes to the left! That means that if we could add those zeroes to its left (which doesn't change the value X) and make a substring of size z[i] + j - i + 1 such that z[i] + j - i + 1 >= X, then we found a new answer.

    Hope that was well explained! :D

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

How would you solve D if the edges were undirected?

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

    If graph is undirected this problem is about finding arboricity of given graph. This goes to matroid theory and is actually graphic matroid partitioning problem.

    UPD: If someone is interested in practical introduction to this stuff, you may check out this tutorial.

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

    UPD: Nevermind :(

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

      Back edges can form a cycle. Example: 5 nodes, dfs tree is 1-2-3-4-5, and there are also edges 1-3, 3-5 and 5-1.

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

        Holy shit, you are right, sorry.

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

        It depends on what are "back edges". For me, if there is next list of edges: (1,2), (2,3), (3,4), (4,5), (1,3), (3,5), (5,1) and dfs tree is 1-2-3-4-5, then (1,3) and (3,5) are forward edges and (5,1) is back edge. So, coloring only (5,1) is ok.

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

Лол, 1200 взломов по B.

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

can we hack our own solution, if its already been hacked by somebody, rip rating, didnt realise the stupid test case, 1 4 5 6 6 6 6 6 6 6 6 this was obvious test case, why was it not included in test case list, most of people got hacked on this.

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

What is intended complexity for E? I did mlogn*10 and it is getting TLE. My implementation of seg tree is pretty not efficient, but why would you give so strict time limit? What is wrong in setting this for 4s?

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

    I've never considered my implementation to be efficient at all. I mean my usual recursive segtree works in 400 ms, so 2 seconds doesn't seem strict. I also think there might have been worse complexity solutions passing if TL was higher.

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

      Hm, im confused now. Is intended solution building 10 seg trees for each digit, and then for each query we need to visit all of them so complexity of one query is 10logn?

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

        Yes, it is. I think the part I didn't take into consideration is that I update all the 9 trees during the same query, so I'm jumping at lot less around the memory, what makes the runtime much lower.

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

      I haven't managed to get within TL with inefficient segment tree implementation. The "efficient and easy" implementation did the trick, but still only 1.5 s...

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

Delted

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

I think there's a small error in putting "Final Standings" after the hacking phase, but before system tests.

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

B pre-test should be made stronger

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

My solution for problem E 60134423 passed pretest 8 in 1954ms. But it shows time limit exceeded at testcase 8 after system testing. Can anyone tell me why this happen?

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

Why my solution 60134423 passed pretest in 1954ms. But after system test it gets TLE on pretest8 ?

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

B have 365 cases at system test lol~

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

Interesting binary search solution of problem A: 60157777

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

    This is not binary search, it is O(1). He calculates min and max values for s, named them left and right.

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

I got AC on D with following greedy solution:

Take any edge, if it has unicolored path from one of its ends, to other, take another color.

Is it possible to hack it? I guess that it is possible, but there are no such tests in system testing.

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

Hello Codeforces,

After yesterday's contest(Educational Codeforces Round 72 (Rated for Div. 2)) I have received 3 system messages. For the problems A, B and C. And these are all the problems I have solved during the contest.

Messages say that my solutions are extremely similar to this guy's coderharshit. Actually I have checked and they are identical.

For quite some time now I have been using this github repo to store my solutions.

I always push my code after the contest, actually I usually forget and do it much later.

Yesterday I just didn't think of people would dig google/github to find solutions during the contest and find my code. And I pushed the solutions during the contest. You can see the time of the commit in github.

So this person, apparently a determined soul to find other people's solutions found my solutions and blatantly submitted all of them. Don't know what to think of these people :) .

In the system messages, I was asked to write a comment here if I have evidence that I have published the code publicly and they accessed it, so writing this now.

fyi, MikeMirzayanov

Best, Burak

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

I want to say... What is the pretest of problem B made of?

It has $$$364$$$ tests. Is there an official problem with more number of testcases?

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

Still waiting for the Editorial :||||||

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

boy, this contest was really tough for me, I was completely discouraged by even first task. however, it's so exciting always (2 times for me heh)

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

    I think it must have been tough on almost everybody. I only solved one problem (as against my normal of 3 or 4) yet maintained my rating of 1539 (0 change in rating).

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

Any ideas for WA on test case 5 for E?