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

Автор Gol_D, история, 3 года назад, перевод, По-русски

1619A - Квадратная строка?

Идея: MikeMirzayanov

Разбор
Решение

1619B - Квадраты и кубы

Идея: MikeMirzayanov

Разбор
Решение

1619C - Неправильное сложение

Идея: MikeMirzayanov

Разбор
Решение

1619D - Новогодняя задача

Идея: Vladosiya

Разбор
Решение

1619E - MEX и инкременты

Идея: senjougaharin

Разбор
Решение

1619F - Сыграем в Шляпу?

Идея: MikeMirzayanov

Разбор
Решение

1619G - Необычный сапёр

Идея: Gol_D

Разбор
Решение

1619H - Перестановка и запросы

Идея: Brovko

Разбор
Решение
Разбор задач Codeforces Round 762 (Div. 3)
  • Проголосовать: нравится
  • +73
  • Проголосовать: не нравится

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

Really liked Problem D. The observation about how pigeonhole theorem can be used in the check function of binary search was very good.

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

    You guys used binary search ? Wow

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

      How have you solved it? Would you like to share your approach?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        • A = maximum of Top-2 by shops
        • B = minimum of Top-1 by friends
        • Result is min(A, B)

        https://mirror.codeforces.com/contest/1619/submission/140109705

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

          podtelkin could you please explain why this idea worked? UPD: Got it. Nice idea

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

            你可以在这里看到中文版本(Link)

            I think I can explain it.

            (Please forgive my poor English.)

            my code is here

            According to the description of the problem, you can easily get the follow inequality:

            $$$ ans \leq \text{minimum of Top-1 by friends} $$$

            I use a[i][j] to describe the j's contribution to friends numbered i.

            Then let's suppose $$$n-1 \leq m$$$.

            Now I give a strategy for choosing gifts:

            • Choose a friend numbered I, and find his favorite gift J.

            Let's suppose a[I][J] is also the maximum among a[1][J],a[2][J],...,a[n][J].

            (That means J's contribution is also the biggest if it's for I.)

            Let me call this Hypothesis A.

            • Then find the Top-2 among a[1][J],a[2][J],...,a[n][J], and pick the corresponding I'.
            • Now both I and I' will be given the gift J.
              • Joy Point of them is top1ByFriends[I] and top2ByShops[J].
            • For the rest n-2 friends, we can always pick their favorite gifts.
              • For those friends, their Joy Point is top1ByFriends[i].
            • So if we try to choose everyone as the lucky I, we will have several $$$\alpha$$$ that satisfy the following condition:
            $$$ max\{\alpha\}\leq \text{maximum of Top-2 by shops} $$$
            • After having this consequence, let's think the situation that Hypothesis A doesn't hold.
            • It's quite easy to come to the conclusion that if top1ByFriends[I] < top2ByShops[J], the $$$\alpha$$$ will be determined by top1ByFriends[I] so any I' who has a[I'][J] bigger than a[I][J] is OK, because he won't influence the result in this situation.

            So now we can say:

            $$$ ans \leq \text{min{minTop1ByFriends[i],maxTop2By Shops[j]}} $$$

            You can prove the result is exactly $$$\text{min{minTop1ByFriends[i],maxTop2By Shops[j]}}$$$ by category discussion.

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

              Supplement:

              If $$$n-1$$$ > $$$m$$$, everyone can get their favorite gifts.

              So ans is minTop1ByFriends[i].

              And you can find that at least two friends will have their favorite gifts in the same shop, so the maxTop2ByShops[j] won't less than minTop1ByFriends[i].

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

              Thank you very much man

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

          I think one simple way of explaining this approach is:

          1) we have to pick at least two gifts from the same store (by the pidgeonhole principle).

          2) we can always choose the store that has the highest second max, and pick the max and second max gifts from this store and give them for the respective friends (lets call this decision opt*), and I argue this choice can always be made and still achieve an optimal solution: if our solution has 2 other items from any same store, then the second highest of these two will be smaller than the second highest of the opt* choice (by definition of highest second max), making it a worse choice. thus, we can always choose opt* and still get a optimal solution.

          3) now pick the best n-2 for the remaining n-2 friends.

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

            Nice explanation. I honestly think that this approach should be added in the blog..

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

        What i did in the contest was we know that we can visit n-1 shops ,so the idea is that for every shop we can see the maximum and the 2nd maximum joy values which are attained for any two friends .let say its i and j ,so leaving these two friends apart we can easily take the maximum of joys from any shops for the rest of the friends .i won't suggest you to see my implementation it's really messy and the binary search logic is way more easy to implement and think .my implementation involves map of multiset of pair of int which was the best i could think in the contest

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

        well, i have a solution using sort and some magic

        this is my solution. I scared to fail the system test, but some how it passed.140057739

        here are my thoughts while doing this problem btw:

        • if i sort the items by price and when I reach the $$$i$$$_th item, if i can delete all the item before $$$i$$$ and still albe to take some of the items after, i can just consider $$$i$$$ as an answer
        • after that is finding how to check if the remaining item can sastisfy the condition at most n — 1 shop:
        • i'm not so sure about this, but if one item was deleted from all shop you should break the loop, and another case is when the remaining items are the same as the number of remaining shop -> this means you can take two item from any shop so you also need to break loop
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    I also used the pigeonhole principle to solve it but the binary search part is still unclear to me... Like how I can prove that if I can get x units of joy I would be able to get x-1 units of joy? Please care to explain...Thankyou

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

      The binary search function $$$f(x)$$$ means I can get $$$x$$$ or more units of joy (not necessarily exactly $$$x$$$ units)

      If $$$f(x)$$$ is true, then $$$f(i)$$$ for $$$i < x$$$ is definitely true

      If $$$f(x)$$$ is false, then $$$f(i)$$$ for $$$i > x$$$ is definitely false.

      So you find the maximum $$$x$$$ for which $$$f(x)$$$ is true by binary search.

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

    Solution to problem D without binary search :-

    • Suppose we can visit at most n shops instead of n — 1, since we have n friends, we can select the best shop for each friend and doing so we will be selecting at most n shops.
    • Now, for n — 1 shops, since we have n friends, there must be a shop from which we buy gifts for at least 2 friends.
    • Hence we select the shop with the highest 2nd max.
    • Now we need to select at most n — 2 shops for n — 2 friends. We can simply take the best shop for each remaining friend.

    my submission

    Edit: I don't have any proof, but it works

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

    prob stupid of me but why is this case ans 2

    2 4 6 5 2 1 7 9 7 2

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

When upsolving G with an unordered_map I got TLE for problem G. When using a map it passes. Took me a long time to realize this was the problem.

Gol_D Did you on purpose make a test case that blows up an unordered_map? I doubt this could've happened accidentally. Especially since my code runs quickly on other max cases, it's only Case 14 that is slow.

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

    Yes, they do keep such a test case on purpose.

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

      I believe it is because someone got hacked using unordered_map during the open hacking phase, then the test case used was included in the main tests

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

can anyone please explain G in bit more detail ?

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

    This is actually a graph problem, let's see it in graph terms.

    Let each bomb be a node in our graph, there is an edge between two nodes if they share a coordinate and have distance $$$\leq K$$$. Now look at its connected components. Clearly if we trigger a bomb, then the entire connected component containing that bomb will explode as well. So a connected component can be triggered by either: we trigger any bomb by ourselves, or we let the earliest bomb explode naturally.

    Now we have two tasks to solve: Find all the connected components (and the minimum bomb timer in each component), and choose which components to trigger manually (and which will explode naturally).

    To find connected components: Suppose all bombs are on a straight line, then it's easy. Sort the bombs, add an edge between all pairs of consecutive bombs with distance $$$\leq K$$$. For the general problem, use a map<int, vector<int>> mapx, mapy; or something like that to store bombs on the same x-straight line or y-straight line and solve it as if all bombs are on the straight line. You now have the graph.

    To choose which components to trigger: Try solving the problem for $$$K = 0$$$ (i.e. no bombs trigger one another). Obviously we want to sort the bomb timers, and trigger the highest timers first, until the rest explodes naturally.

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

      Ahh, sorry I meant H, there are so many problems in contest nowadays, nice explanation, thanks :) I understand sqrt decomp. is applied. I got the idea of query of type 2, but not of type1, why we need inverse indices and that part.

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

        Think about the permutation as a functional graph where each vertex points to another vertex. In order to answer type 2 queries efficiently, we need a "jump" array which gives the index we will be at if we step forward $$$Q$$$ times. When we perform a type 1 query on indices $$$x$$$ and $$$y$$$, most values do not need to be recomputed--the only indices are $$$x$$$ and the $$$Q-1$$$ ones that jumped over $$$x$$$, so $$$r_x$$$, $$$r_{r_x}$$$, etc., and similarly for $$$y$$$.

        To recalculate these, start with $$$x$$$ and step forward $$$Q$$$ times to find $$$jump_x$$$. Then step backwards using the reverse permutation to calculate $$$jump_{r_x}$$$, $$$jump_{r_{r_x}}$$$, etc.

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

      140270271 Can you take a look at this submission of G, please? I would appreciate a lot.

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

In problem C's code it should be 18 instead of 19

if(x < y && y >= 10 && y <= 19) b.emplace_back(y — x);

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

I saw some solutions for problem H that use link cut tree, could anyone help me to understand the idea behind these solutions?

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

    My understanding is:

    1. A permutation can be decomposed into several cycles. If you view each element (1,2,...,n) as a vertex and each (i -> p[i]) as a directed edge, you end up with a directed graph of some simple cycles.
    2. A type 1 query "1 x y" is equivalent to cut cycle(s) at the edge (x -> p[x]) and the edge (y -> p[y]), and join the broken cycle(s) with new edges (x -> p[y]) and (y -> p[x]).
    3. A type 2 query "2 i k" is equivalent to, (say vertex i is on cycle[i]) find the (k mod length(cycle[i]))-st neighbor of i on cycle[i].

    To simulate the above process, all you need is a data structure that represents cycles and supports quick split/merge (for type 1 queries) and find k-th element (for type 2 queries). One obvious choice is the splay tree. Given link-cut tree is mostly based on splay tree, I guess that would work as well.

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

couldn't get AC on E because of integer overflow. makes me wonder if there are any downsides to always using long long instead of int, I couldn't see any time difference with $$$2.10^9$$$ operations

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

Can someone explain this part from Problem G ?

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

    If you are considering bombs till component i to be exploded by timeout, then remaining bombs need to be detonated manually. The count of remaining bombs is (res.size()-i-1). Since you can start detonating from time 0, total time taken to manually detonate remaining bombs is ((res.size()-i-1)-1) i.e. (res.size()-i-2). For a particular i, you would be taking max of time taken to manually detonate and time taken to explode by timeout. Because we can be sure that in that time, all bombs are gone. The minimum such time where all bombs are gone would be the answer.

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

Solution for problem D without the log factor:

For every person, find $$$B_i$$$. $$$B_i$$$ means the best shop to choose while buying a gift for person $$$i$$$. From now on, I'll rephrase "buying a gift for a person $$$i$$$ from shop $$$s$$$" as "assigning person $$$i$$$ to shop $$$s$$$.

Case 1: Number of different "optimal" shops (i.e. number of distinct integers $$$B_i$$$ for $$$1 \leq i \leq n$$$) does not exceed $$$n - 1$$$. We can assign person $$$i$$$ to $$$B_i$$$ and calculate the answer directly.

Case 2: Otherwise. Then there has to be at least one person $$$i$$$ such that it's not assigned to $$$B_i$$$. Let's call such a person "unhappy". Then I claim that there is no more than $$$2$$$ unhappy people in an optimal assignment. Proof is left as an exercise for the reader.

What we can conclude from here is that in an optimal assignment, we'll choose exactly $$$2$$$ people and assign both of them to the same shop. Note that none or one of them can be assigned to their best shop. And every person $$$i$$$ in remaining $$$n - 2$$$ people are assigned to $$$B_i$$$.

Call the shop with $$$2$$$ people assigned as $$$s$$$, and friends to be assigned to $$$s$$$ as $$$x$$$ and $$$y$$$. Without loss of generality, assume that $$$p_{sx} \leq p_{sy}$$$. What is the answer for a fixed $$$x$$$, $$$y$$$, $$$s$$$? Turns out it's the minimum of $$$min_{1 \leq i \leq n, i \neq x, i \neq y}(p_{B_ii}), p_{sx}$$$ and $$$p_{sy}$$$.

Note that we can assume as if $$$y$$$ is also assigned to $$$B_y$$$ because we know that $$$p_{sy}$$$ can't minimize the answer while $$$p_{sx}$$$ is there. Therefore we don't have to iterate over $$$y$$$'s and only take the minimum of $$$min_{1 \leq i \leq n, i \neq x}(p_{B_ii})$$$ and $$$p_{sx}$$$. So let's iterate over different $$$x$$$ and $$$s$$$. But we have to find a way to ensure that there is at least one $$$y$$$ such that $$$p_{sx} \leq p_{sy}$$$ holds for a fixed $$$x$$$, $$$s$$$.

Here is a way to check it: We can store for every shop the value of its most valuable gift and its count. Call it $$$V_s$$$ and $$$C_s$$$ for shop $$$s$$$ respectively. If $$$p_{sx} < V_s$$$ or $$$p_{sx} = V_s$$$ and $$$C_s \geq 2$$$ then it is a valid $$$(x, s)$$$ pair.

Complexity is $$$\mathcal{O}(nm)$$$:

In case 1, checking is done in $$$\mathcal{O}(nm)$$$. In case 2, at every iteration of $$$x$$$, you first find $$$min_{1 \leq i \leq n, i \neq x}(p_{B_ii})$$$ in $$$\mathcal{O}(n)$$$ and iterate shop $$$s$$$ in $$$\mathcal{O}(m)$$$. Total runtime is $$$\mathcal{O}(n(n + m))$$$, which is bounded by $$$\mathcal{O}(nm)$$$ because $$$n \leq m$$$ must hold at case 2.

See example submission: 140114559. Note that I have swapped the dimensions of $$$p$$$ in the problem for implementation simplicity. I also have a vector $$$d$$$ to count the number of distinct shops for case 1.

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

I can't figure out what's wrong in my solution? It's failing on test 2. Can anyone please help? my code.

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

1619A — русский текст разбора не соответствует коду (код верный, в тексте ошибка какие символы сравниваем между собой) — исправлено

1619B — предложено решение O(sqrt(n)), при этом есть решение за O(1), ответ int(sqrt(n)) + int(cbrt(n)) — int(cbrt(int(sqrt(n))))

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

    думаешь функция sqrt(n) работает за O(1)?

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

      практически да, тайминг расчетов sqrt(2) и sqrt(1e17-1) неотличим

      в целом "под капотом" sqrt зависимость только от требуемой точности

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

        это понятно, но это не O(1). Ты же делаешь бинпоиск или что там делает sqrt чтоб корень взять

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

          есть разные реализации sqrt, в том числе просто вызов одной процессорной команды. на реальном железе (офисный ноутбук i3) я вижу, что и 10 млн вычислений sqrt(2) и 10 млн. вычислений sqrt(10^17-1) выполняется за 500 ms, множитель не появляется

          по сути моего вопроса — решение за три операции с плавающей точкой точно эффективнее, чем set на количество элементов, равное ответу и оно точно заслуживает публикации :)

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

            Фактическая скорость не имеет отношения к асимптотике, асимптотика показывает количество операций, а оно не зависит от мощности железа. Реализаций корня за O(1) я еще не видел, чаще всего используется бинпоиск, то есть асимптотика вычисления корня — O(log n).

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

              если асимптотика это количество операций и вычисление корня O(log n), то операций для вычисления sqrt(2) должно быть меньше, чем sqrt(1e18) и sqrt(1e18) фактически должен вычисляться дольше, чем sqrt(2) а это не так

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

                log 1e18 = 60

                log 2 = 1

                операций на самом деле больше, но с нынешним железом разница практически незаметна.

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

At first, I think the permutation in problem H can be considered with a graph with n nodes and n edges (A Base loop tree)

Finally, I realize that it is just a graph with serval loops.

What a pity!

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

In problem B, replacing sqrt(n) with sqrt(n+ 0.5L) give correct answer. Why is this happening? Thanks in advance.

Hacked solution : https://mirror.codeforces.com/contest/1619/submission/140041728

Accepted solution : https://mirror.codeforces.com/contest/1619/submission/140180623

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

    Because of representation of real numbers in binary. For example, pow(10^9, 1/3) = 999.9999... and not 1000 as it should be. By adding 0.5 you're avoiding this problem.

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

problem F is actually a joke

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

    Can you please explain the joke part in it?

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

      it's easier than D and E. look at this submission

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

        Only after you realize it/read the editorial :)

        D/E are like just do whatever said, F needs a lil bit of thinking

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

          No buddy, he is right, problem F is comparable to C, just a little bit of implementation and knowledge of deque(I used it for putting last to front), D involved more than 5x thinking than F... I am more convinced on this fact also due to the line mentioned in the announcement also that problems may not be in their proper order... According to me, the order could be A B C F E D.

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

Why need to sort the input array of problem E? As we use the frequency array later, any need to sort the input array?

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

    you are completely right, filling and sorting of vector a are not required

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

Please help me debugging my code for problem G. It is getting WA on test case 2 line 6. 140296294

I think I am committing some mistake in calculating ans at the very end of the code.

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

I solve B using inclusion and exclusion principle. here's my submission:

140032787

I was worried about the case where I use both sqrt and cbrt but it passed all testcases!

After the contest I found that most of the contestants solved this problem using set or any other data structure. However, I find this solution much easier.

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

    for someone who can't understand this idea...

    • count numbers of the form x^2 such that x^2 <= n (say A2)
    • count numbers of the form x^3 such that x^3 <= n (say A3)

    numbers of the form x^6 are counted twice so we subtract them once.

    ans = A2 + A3 — A6

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

No need to sort the array in problem E.

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

Did anyone solve prolem H with treap?

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

    Indeed, it's quite reminiscent of this problem from SecondThread's treap educational contest. Just need to figure out the right treap operations to do, and implement a few new ones.

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

In the question named "Squares and Cubes".....just use unordered_set rather than ordered_set, it will reduce time complexity. :D

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

I think I have an O(n + qlogn) solution for problem H:

A permutation is a composition of circles (i -> p[i] -> ... -> i). We can represent those circles with treaps, one for each circle, when the nodes are i, p[i], p[p[i]], ... from left to right. Note that we can use split and join to make any element the leftmost.

first-type queries can be answered — When we swap p[i], p[j] and i,j are in different circles, we merge two circles with O(1) split & join operations to receive: (i) -> (p[j] -> ... -> j) -> (p[i] -> ... i). When we swap P[i], p[j] and i,j are in the same circle, we split two circles with O(1) split & join operations to receive: (p[j] -> ... i), (p[i] -> ... -> p[j]).

Second-type queries can be answered easily — we will keep for each subtree it's size.

*We will keep an arrays of pointers, Arr[i] is a pointer for the node that represents i.

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

last problem is crazy!!!

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

I implemented E with a std map instead

145083862

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

For those who also struggled to understand the code in the sample solution of D, inside the given sample code, variables n and m actually have the opposite meaning compared to the actual meaning stated in the question.

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

Problem E can be solved in linear time (without sorting mentioned in the editorial):

Lets create a list $$$f$$$, where $$$f_v$$$ is the amount of times $$$v$$$ occurs in the input $$$a$$$. Firstly, notice that $$$ans_i$$$ for $$$i \leq mex(a)$$$ is simply $$$f_i$$$, because we only need to increment the values occupying our target MEX.

Our goal now is to calculate answers for target MEXes greater than $$$mex(a)$$$. Let's introduce a pointer $$$lst$$$, which, during our evaluation of MEXes, will always point to the first index less than the target MEX such that $$$f_{lst} \geq 2$$$. This ensures that we can increment $$$1$$$ or more values of size $$$lst$$$ to assist in reaching the target MEX.

We will now start calculating the remaining answers from $$$ans_{mex(a)+1}$$$ to $$$ans_n$$$. If $$$f_{i-1} = 0$$$, then $$$ans_i = ans_{i-1} + i-1-lst$$$, as we can just increment a value of size $$$lst$$$. Otherwise, $$$ans_i = ans_{i-1}$$$. Remember to decrement $$$f_{lst}$$$ for the sake of updating $$$lst$$$. If there are no valid $$$lst$$$ in this situation, the remaining answers will all be $$$-1$$$. Note that if $$$f_i \geq 0$$$, we will instead print out $$$ans_i + f_i$$$ rather than just $$$ans_i$$$, as we need to move those $$$f_i$$$ values out of the way.

Also notice that if $$$f_{i-1} \geq 2$$$, we must set $$$lst$$$ to $$$i-1$$$, due to it's definition.

Accepted submission: https://mirror.codeforces.com/contest/1619/submission/165354843