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

Привет, Codeforces!

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

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

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

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

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

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

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

Привет Codeforces!

Harbour.Space University, the International Tournament of Young Mathematicians (ITYM) и St. Paul International School Barcelona создали специальный онлайн тест для школьников старших классов, который пройдет 5 мая в 17:00 (московское время).

Вы можете принять участие в онлайн-тесте, если соответствуете следующим требованиям:

  1. возраст между 12 и 18 годами,
  2. еще не выпустились из школы,
  3. соответствуете правилам в Международной математической олимпиады (IMO) или Международной олимпиады по информатике (IOI) для участия в 2020-м году (то есть имеете право отбираться и, в случае успеха, участвовать в этих олимпиадах).
Зарегистрируйтесь (до 3 мая) →

Все принявшие участие в тесте получат 20% скидку на участие в Tech Scouts — двухнедельном летнем лагере, который пройдет 8-19 июля в одной из ведущих международных школ Барселоны St. Paul International School Barcelona. Те, кто займёт самые высокие места в тесте будут приглашены на собеседование, по итогам которого будут награждены полной оплатой обучения в усложнённом курсе Advanced Technical Track лагеря Tech Scouts.

Для того, чтобы зарегистрироваться, пожалуйста, заполните эту форму до 3-го мая, 2019.

Если вам хотелось бы поучаствовать в обучающем лагере или просто интересно узнать о нем больше, перейдите по этой ссылке: Tech Scouts website.

UPD: С одной из задач возникли небольшие проблемы, взамен нее будет использована одна из малоизвестных задач Максима Бабенко.

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

Место Участник Задач решено Штраф
1 step_by_step 7 491
2 MyBotDear 6 270
3 receed 6 280
4 I_love_Tanya_Romanova 6 286
5 dreamoon_love_AA 6 299

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

Место Участник Число взломов
1 halyavin 64:-3
2 achaitanya.sai 39:-23
3 wzw19991105 18:-1
4 LiM_256 14:-1
5 patriot1488 2
Было сделано 153 успешных и 180 неудачных взломов.

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

Задача Участник Штраф
A halyavin 0:06
B nuip 0:07
C quailty 0:04
D waynetuinfor 0:11
E step_by_step 0:05
F step_by_step 0:15
G step_by_step 1:22

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

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

»
6 лет назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится
Every educational round ever
»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Account of @PikMike is very inspiring for everyone, Rating progression from 945 to 2244, NEVER GIVE UP!

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

PikMike says, NEVER GIVE UP

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

Hope the problem set is going to be an interesting one like the last one :)

Happy Coding

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

wtf?

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

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

the round should be unrated

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

what is going on?

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

    Problem A was not well described. The side note under the test case was explaining an unwritten test case which means it was misleading. The solution had been rejudged. I see something strange that most of the solutions get WA answer on test 3. check the announcement of the round. Whatever, it is unrated now

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

To be honest, for long enough hasn't a problem A been so... chaotic.

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

Is it rated? Rejudging affects >3000 people.

UPD: Unrated.

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

read first problem 10 times before seeing announcement. Feeling Irritated

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

The round should be unrated, it's not ok that after 30 mins I see my AC code on A get WA

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

    Literally everybody did though, I feel like it could still be rated, I don't know

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

oh no.

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

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

Что?

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

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

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

Eventually, the round became unrated. :(

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

Solve problems just for fun. ;)

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

Authors, dont worry. Shit happens. Good luck to you

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

So what's going on in Problem A? My code got WA after rejudge. But I don't know what's wrong in it. http://codeforces.me/contest/1156/submission/53616304

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

Got really happy after getting notification of round being unrated. Already many WA.

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

should have been rated but oh well

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

This round the highest Accepted on the entrance div2-A problem was 8. Out of 100! XD

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

to be honest, this compitition has got a really chaotic problem set.

(who had seen problem A give so many leaks? And problem B also got an error in the standard output.)

yet this round is unrated.

Irritating. Very irritating.

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

without paying attention to solved problems, It won't change our rating , yeah?

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

So funny contest.. I see this 1st time, that I solved A and after retest I get WA. Funny evening...

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

раунд помойка

Автор, ты не смог решить ашку? Рили?

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

"_Unfortunately_, the round will be unrated."

More like, Fortunately am i rite?

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

Я конечно понимаю что автору нравятся кошко-девочки и ему многое дозволено , но это уже слишком .

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

happy coding

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

Japanese people welcomed the new era, not error.

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

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

Literally half participants on problem A. ( including me )

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

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

Right, +10 WA to my submissions. Thx, dear author

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

Something went wrong...

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

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

This year the highest grade on the entrance math test was 8. Out of 100!

I guess now everyone knows why xD

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

What a mess.

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

2 1 2

is this valid for Problem A?

UPD: Finally this is surely invalid because an anoucement.

The triangle is oriented in such a way that the vertex opposite to its base is at the top.

UPD2: really sorry, maybe I should change new glasses, the problem statement says, the triangle is oriented in such a way that the vertex opposite to its base is at the top

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

    No. The direction of the red triangle should be like the black one.

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

      isosceles triangle with the length of height equal to the length of base.

      each triangle base is parallel to OX

      for each i from 2 to n figure i has the maximum possible length of side for triangle and square and maximum radius for circle

      The red triangle fit these condition well.

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

        OK. But there is another announcement now.

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

        Yes, but you have drawn a equilateral triangle for which the height is not equal to the sides, so this configuration is impossible.

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

          this is my fault because of drawn misleading.

          even thought if drawn correctly, the answer may be 5 not 6. :D

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

    No. Notice that "each triangle base is parallel to OX".

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

      Anyway, the base is still parallel :)

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

        Yea, I think you are right. In this case, I considered the vertex as the "base" actually, so I thought it's not parallel to axis.

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

      But just now there was an annoucement

      The triangle is oriented in such a way that the vertex opposite to its base is at the top.

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

        It's also in the statement of the problem:

        the vertex opposite to the base of the triangle is poiting up;

        And I think it was there before the announcement because I had the tab open and didn't refresh.

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

          yeah, you are right.

          maybe I should change my glasses

          UPD: there are only four condition in very first,

          the vertex opposite to the base of the triangle is poiting up;

          this was just added later.

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

            No, you don't have to do that; that state is revised, and before revising that, there was some vague state.

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

    Hehe, didn't even think of this one!

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

Since the contest is unrated and everyone is discussing the problems anyway... how to solve C? It feels like there should be some sort of greedy way of matching up points but I can't figure it out.

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

    I did binary search for the number of matches k. Check by trying to pair the k smallest points with the k largest points.

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

    just sort the array, and use two variables i and j. initialize i=0,j=n/2 and then just start pairing them.

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

I want to experience how it feels like asking a solns of ongoing contest in comments.

Here it goes -
"How to Solve D??"

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

    You can solve it with a little bit of DSU.

    First of all, use all edges marked as $$$1$$$ to merge nodes into disjoint sets.

    Then, the remaining edges — those marked as $$$0$$$ — are considered as the actual edge of the graph (in other words, after using all $$$1$$$ edges to create disjoint sets, we remove them).

    From here, we'll perform DFS for the entire graph to find the components of nodes connected solely by $$$0$$$ edges.

    For each component, let's denote $$$m$$$ as the component's size. Also, let's denote $$$k$$$ as the number of nodes not within the component, but can be reached from some nodes of the component due to being in the same disjoint set (mentioned at the first step). We'll add $$$m(m-1) + mk$$$ to the final answer.

    The calculation of $$$k$$$ is simple — before the DFS traverse initiate $$$k = 0$$$. For each node $$$z$$$ visited, increase $$$k$$$ by $$$sizeof(dsc(z)) - 1$$$, with $$$dsc(z)$$$ is the disjoint set containing node $$$z$$$.

    Total complexity: $$$\mathcal{O}(n \cdot \log(n))$$$ or $$$\mathcal{O}(n \cdot \alpha(n))$$$, based on how you construct the disjoint set union.

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

      Why not to use DFS to find the components connected by 1 edges?

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

        Well, we still need $$$sizeof(dsc(z))$$$ after joining nodes by $$$1$$$ edges, and (not sure if there was any neat implementation), if I performed DFS on that step, I'd either do it twice to assign $$$sizeof(dsc(z))$$$ to all $$$z$$$ in that component, or use a vector/stack to maintain the newly visited nodes, which could actually makes the implementation be a bit unnatural.

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

      The answer is S(m*(m-1)) + S(dsc(z)*(dsc(z)-1)) + S(m*k) right? S() denotes sum over all components, disjoint sets and components respectively.

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

        $$$S(m(m-1)) + S(mk)$$$ actually. Forgot to include it into the main comment, will edit in a few seconds ;)

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

    I used Tree DP, with:

    dp[0][i]: number of 0-1 path whose lca is child of i

    dp[1][i]: number of 1-path which ends at i

    dp[2][i]: number of 0-path which ends at i

    dp[3][i]: number of 0-1 path which ends at i and the edge connecting i is 1-edge

    dp[4][i]: number of 0-1 path which ends at i and the edge connecting i is 0-edge

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

    It's also possible to do it in O(n) using dp on trees. Let dp[x][0] be equal to number of vertices to which we can access from vertice x using paths which have only zeroes as their weights and dp[x][1] same thing but which have only ones as their weights.

    We can note, that each path we are looking for has a point where ones change to zeroes. Let's assume that our vertice is the vertice of change for some paths. We can easily observe that we need to add to an aswer dp[v][0]*dp[v][1]+dp[v][0]+dp[v][1].

    So now the only problem is to find a way to calculate dp array. Firstly let's calculate number of paths which i mention before but only for vertices in the subtree of vertice x. That can be done as follows: if we have dp calculated for our son, and we use a path of weight y to go to him, then dp[x][y]+=dp[son][y]+1.

    Now we have the answer but only for a vertice from which we started our DFS (because his subtree is full tree). Now let's start second DFS. An observation is: if we go from vertice x to its son using a path with weight y then dp[son][y]=dp[x][y]. Why? Having in memory that dp[x][y] is number of vertices we can access from vertice x using paths which have only weights y, then we see that this number can't change if we are using a path of weight y.

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

    Lots of tree-DP problems based on paths have a standard procedure consisting of two steps:

    • Solve the DP, but the DP of a vertex will only be restricted to the subtree of the vertex.
    • Start changing the DP values from top to bottom, so that now, the DP of a vertex describes all paths originating at the vertex. There are only two cases — one, we have already included in our DP state, that the second vertex is a child of $$$v$$$, and the other is when the second vertex of the path is the parent of a vertex $$$p[v]$$$.

    Initially, if I define $$$dp[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a valid path, and $$$dp1[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a path by navigating only 1-edges, then in one dfs we can compute these values. Then, in the next dfs, we include in both $$$dp[v]$$$ and $$$dp1[v]$$$ the case where the second vertex of the path is the parent, which gives us the final answer for vertex $$$v$$$. So after this dfs, $$$dp[v]$$$ will be the number of valid paths originating at vertex $$$v$$$ and $$$dp1[v]$$$ will be the number of valid paths originating at $$$v$$$ by navigating only 1-edges. Note that we must change the value of the parent before that of a vertex, because we want to use the second definition of $$$v$$$ for the parent in the second DFS.

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

problem A (and other problems also) proved that every contestant is also a Labour. Happy Labour Day.

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

Is it possible that a cycle inscribed into the non-equilateral triangle (isosceles with the length of height equal to the length of base) with three distinct points touched?

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

fortunately, the round be unrated :) problems are interesting,but I have bad performance.

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

I know author is going to be blamed for this round. But honestly, I found the problems really beautiful and engaging. Kudos to author.

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

Good decision to announce the contest as unrated .

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

Thanks for very interesting problems! Can anyone tell me how to solve B?

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

    Lets represent a, b, c...z as 1, 2, 3, ... 26. Now the best strategy is to club all a's together, all b's together etc. If you keep first all evens and then all odd terms, then we'll just have to worry about junction. For this you can find a pair of (even, odd) which differ by atleast 1.

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

    Let's switch to numbers instead of characters, so the alphabet will be $$$0,1,2,\ldots 25$$$. Notice that a pair can only be ugly if one of them is odd and the other is even. First we have two cases if there're only odd or only even numbers, in that case we're done. Else we have at least one odd and one even number, intuitively we may want to minimize the touching of odds with evens so we may think about an order where first the even numbers then the odds come. This will only be possible if there's at least a pair of odd and even numbers that have a difference larger $$$1$$$ (since then we can put them in the middle and the rest can be placed arbitrarily) and obviously in the case when we have $$$0$$$ such pairs it would be impossible to order them (since in every ordering there is at least one odd-even pair), so we can see that the above statement is equivalent to that there's a valid reordering.

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

For everyone who got WA on test 7 (problem C), try this case:

10 2 1 2 3 4 5 6 7 8 9 10

Correct output: 5

I made a greedy solution (sort all the numbers using multiset, then for every number find the smallest number it can be connected to and erase both numbers from the multiset) and this case showed me that my approach was wrong. I hope it'll be helpful to someone.

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

(Direct quote from Problem A) So can you pass the math test and enroll into Berland State University?

Um..... (sigh...)

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

after rejudged A

It was at this moment theroot knew, he fucked up xDD

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

Why RE on test 16? Code

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

    I guess it is due to size of the array. As segment trees have around 4*N nodes.

    Btw if possible then please explain your approach here!

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

В чем баг то заключался в задаче A?

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

    3 3 1 2 ответ 7, по идеии ответ 6. Кажется автор тоже пропустил этот момент.

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

      Нет. Там получается, что одна вершина треугольника совпадает с точкой пересечения окружности и квадрата

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

So.. Any hint for C?

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

    If you order the array and one of the best possible solution has some pairs with both indexes in the first half of the array, you can change one index of each this pairs be indexes of the second half of the array. And this new set of pairs still is one of the best solutions.

    Same way if you have some pairs with both indexes in the second half.

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

Last contest I wrote a toxic comment and I'm really sorry for that because mistakes happens and we should understand that

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

Any hints for E ?

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

    You can doing it using a Mergesort tree.

    For each element Ai calculate the range in which it will be maximum. That is Li and Ri where Li is the highest index j < i such that Aj > Ai and similary Ri is lowest j > i such that Aj > Ai.

    For each Ai, check each j in Li...i-1 to see if Ai — Aj exists between i+1...Ri using the mergesort tree. (You just have to maintain a set on each node in the Mergesort tree and check for each node in the range if the required value exists in its set).

    Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once. Each query takes logN*logN time.

    Thus the complexity is N*logN*logN.

    Not sure if easier approach exists.

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

      "For each Ai, check each j in Li...i-1 " Can you please help me understand why this will not lead to O($$$n^2$$$)?

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

      "Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once."

      Could you explain this part a little bit more? What if we have a situation like:

      [ ( y ) x ]

      Here x and y are two elements, [] indicate Lx and Rx and () indicate Ly and Ry. Obviously, y < x. Evidently, we can construct such a case (for example, 10 5 6 7 1 3 2 8 9 4 11).

      In such a case, every element between Ly and y is queried twice (once because of y and once because of x). I thought of the same approach during the contest, but I didn't think it would work because of such cases.

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

      I had a similar approach, but i think it is easier. For each element you calculate l[i] and r[i]. These numbers represent the range in which a[i] is the maximum element. To find this easily we can use a stack.

      Then, for every i from 2 to N-1, we will do the following: Choose the smallest side in our range [l[i],r[i]]. ( Smaller between i — l[i] and r[i] — i ). Then we can try every number in this range with a "bruteforce" approach. To know if that number will make a valid solution, we need to check if its complement ( a[i] — a[j] ) its in the opposite side and inside the range in which a[i] is maximum.

      This approach seems like bruteforce, but with a little bit of math you can confirm it is actually linear.

      Code to understand the idea better : 53634108

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

        "This approach seems like bruteforce, but with a little bit of math you can confirm it is actually linear. " can you please give a rough sketch of proof?

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

      I think Li and Ri can be found using range maximum query inside a binary search..

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

    divide and conquer

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

    I think that 53648275 is pretty short, easy to understood and O(n log n)

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

      can you please explain your solution a little bit?

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

        I used divide and conquer... $$$f[l, r)$$$ counts how many pairs $$$(i, j)$$$ exists such that $$$p_i+p_j=max(p_i...p_j)$$$ and $$$i < m <= j$$$ for $$$m = (l+r) / 2$$$, and again solve the problem for $$$f[l, m)$$$ and $$$f[m, r)$$$ recursively (cases when the condition $$$i < m <= j$$$ not is true).

        So for a fixed $$$f[l, r)$$$ and $$$m = (l+r) / 2$$$ for every $$$l <= pl < m$$$ and $$$m <= pr < r$$$ the maximum of the interval $$$[pl, pr]$$$ is $$$max(max(pl...m-1), max(m...pr))$$$, i assume that the maximum is equal to $$$max(pl...m-1)$$$ this determine $$$pr$$$ of a unique way $$$(pr=max(pl...m-1)-pl)$$$ so you only need check if $$$[pl, pr]$$$ is a valid pair

        But what about if $$$max(max(pl...m-1), max(m...pr)) == max(m...pr)$$$ not $$$max(pl...m-1)$$$ ?, then solve the same problem again but with the reverse of the array, because if the maximum is in the right part in the reverse will be in the left part :)

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

          is selecting all possible $$$(pl, pr)$$$ doesn't lead to $$$O(n^2)$$$?

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

            For a fixed $$$pl$$$ you can determine of a unique way the maximum (assuming that is in the left part) and then $$$pr=max(pl...m-1)-pl$$$. So you only need iterate all $$$l <= pl < m$$$

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

Can someone tell me why this submission got WA https://codeforces.me/contest/1156/submission/53640819

got it fails for this input 10 2 1 2 3 4 5 6 7 8 9 10

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

If anyone wants to solve problem D using dfs 53633184.

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

    would you please explain your approach

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

      Divide the tree into connected components of edges of 0s and 1s.

      Now, there will be three cases to sum:

      case #1: the path contains edges of all 1s.

      case #2: the path contains edges of all 0s.

      case #3: the path contains some edges of 0s in starting then all 1s at end.

      For case #1 and case #2 answer will be simply cnt1 * (cnt1 - 1) and cnt0 * (cnt0 - 1) respectively.

      For case #3: select a center vertex containing both edges of 0s and 1s. Now, to form a valid path, you have to select first vertex from connected component of 0s and second vertex from connected component of 1s. Answer in this case will be (cnt0 - 1) * (cnt1 - 1). [ how ? center vertex will be counted in both components.]

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

How to solve B? What is the case when we don't get an answer??Please help guys

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

    You need to take unique elements in string sort it and keep even indexes in first and odd indexes in second array. For example if string is "dcbab" then it would be like "ac" and "bd" and check if we can return it as "acbd" or "bdac" if two if this replacements are not possible then we return wrong answer, else we would return possible answer.

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

      But how is this true ??

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

        Because there if we take even and odd indexes of the unique string then there would be minimum 2 letters between them and if there is the size of the string is odd number it means last element of two arrays differ by 1. It means you check if which replacement is right array two-> array one or array one -> array two. And don't forget to print out the number of elements in the string

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

    Cases when we don't get answer..
    2
    ab
    abc

    Critaical Test Cases you can check...
    2
    abd
    acd
    Output:
    adb
    cad
    How to solve:
    You can count the frequency of every letter from 'a' to 'z' in the input string... Then iterate through 'a' to 'z' and if count of it is not zero then insert it in a vector or string as you want... then take the even positions characters in vector1 and odd positions characters in vector2... then check if vector1+vector2 give you a valid solution or vector2+vector1 give you a valid solution if no one give a valid solution then, there exist no solution.. Hope you understand..

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

I'm a little bit confused. Isn't solution for problem F is to calculate number of winning and all combinations and just divide them?

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

What's halyavin doing?

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

in fact, Problem A is nice and trick. if you got WA... did you thought about this foken test case :D ?

6 intersection Points, NOT 7

also, the Infinite Cases :

But during the Contest: Set_IQ(0);

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

halyavin back in business.

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

Can anyone help me debug my solution for problem C

https://codeforces.me/contest/1156/submission/53644079

I get WA on test 7, is my idea completly incorrect ?

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

Международная математическая олимпиада — это не MOI, как написано в посте, это IMO.

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

Why do most problem C solutions split the initial array in 2 ?

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

Lmao waited for this contest ever since they messed the last one a couple of days ago just to mess this one again.

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

Maybe this might interest someone...

I solved problem B using random_shuffle

https://codeforces.me/contest/1156/submission/53634293

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

In tags of problem C I've seen ternary search.Can anybody explain how to use ternary search in this problem?

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

    https://codeforces.me/contest/1156/submission/53646659 here is a solution using ternary search. it's very similar to the binary search one so i think it isn't necessary to do it using ternary search. i think the easiest solution is using two pointers technique, it's clear that it isn't optimal if we matched any number with another one has index below than n/2 because it may decrease our answer and we could match the two numbers with another two have indices above n/2, so we only have to start the first pointer from 0 and the other from n/2 and increase our answer whenever the condition happen and increase the two pointers too if the first pointer is below n/2, else we increase the second pointer until the condition happen or the second pointer reach n and here is a solution using two pointers https://codeforces.me/contest/1156/submission/53615906

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

    if the solution has one peak or low on the middle of searching range, we can find that by ternary serach . when doing two pointer greedy rolling match p1 = 0 is optimal obviously, and choice of p2 have the property to do ternary search if choose 1 it is not good since best can only be 1 it will be optimal at some middle point and then be bad again at last part since some possible match will be in front of p2

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

can anybody help me on test 6, problem B plz :( thanks

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

Don't worry awoo, we still love you!

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

D, E, and F were really intersting. I guess without problem A we could've had a great contest.

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

Editorial?

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

Can someone tell we why I get a WA on test1 problemB My submission, it says that "wrong answer Resulting string should be a rearrangement of the given string" but I think my answer is correct!

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

Prob.B
BOGO SORT Σ(っ °Д °;)っ
53651542

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

The problems are really good, by the way, how to solve problem E?

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

My second unrated contest...

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

Can someone explain problem C using binary search?

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

    After sorting the set of point x, you only need to look at begin and last N points while checking whether N can be an answer.

    My submission

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

You have no right to recognize a non-existent state Its name is Palestine, not Israel -_-

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

awoo There is a bug in the checker of problem G!
It says "each character is a lowercase or an uppercase Latin letter, or a digit" in the statement, but if you use uppercase, you get WA!

Accepted 53671039 and Wrong answer on test 1 53671084 only differ by 1 byte.

I think you have no choice but to rejudge G and make this round unrated :(

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

    I fixed the checker and rejudged your submission, it's ok now.

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

The problem G is 20 years old! It was offered by Maxim Babenko for Saratov internal contest. Now he heads development of the YT platform for distributed computing at Yandex. We studied in the same school, in parallel classes. I am very grateful to Maxim that he inspired me to learn programming in those years.

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

Loved the problems... keep taking such contests more... it was nice contest if we ignore issue on first problem