liouzhou_101's blog

Editorial of Codeforces Round #700
By liouzhou_101, history, 4 years ago, In English

UPD: Solutions are added.

1480A - Yet Another String Game

Tutorial
Solution

1480B - The Great Hero

Tutorial
Solution

1479A - Searching Local Minimum

Tutorial
Solution

1479B1 - Painting the Array I

Tutorial
Solution

1479B2 - Painting the Array II

Tutorial
Solution

1479C - Continuous City

Tutorial
Solution

1479D - Odd Mineral Resource

Tutorial
Solution

1479E - School Clubs

Tutorial
Solution
  • Vote: I like it
  • +185
  • Vote: I do not like it

Comments Comments (176)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -64 Vote: I do not like it

Will this round be unrated?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -176 Vote: I do not like it

Problem C is noice!

→ Reply
»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Div 1A/2C was a nice use of binary search!

→ Reply
»
4 years ago, # |
  Vote: I like it +107 Vote: I do not like it

Thank you for the original problems and strong pretests.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the speedy and high-quality editorial with elaborate proofs :) . Keep up the good work!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +61 Vote: I do not like it

For problem D, you don't need to consider an xor of 4 paths; we just have $$$f(u, v, l, r) = f(1, u, l, r) \oplus f(1, v, l, r) \oplus \mathbf{1}_{A_{lca(u,v)}}$$$; then you can special case $$$A_{lca(u,v)}$$$ and the rest just needs to find one unequal index, which doesn't require any special mod 2 properties of XOR.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -88 Vote: I do not like it

    have the same doubt. I think div2 B and div1 D both wrong questions or no proof they have for correctness. so MikeMirzayanov u gonnna re test all submissions with test case

    Spoiler

    or no? tell fast. even many top rankers have different answer for the test case. tell me

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

      I don't think we're talking about the same thing, I'm giving a simplification to the solution of Div 1 D.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello.

What is the answer for this test (Div.2 B) :

1 1 10

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

Can anyone tell me why my solution for Div2B is wrong? (https://codeforces.me/contest/1480/submission/106778511)

Edit 1: It's fixed now. This solution gave WA during the contest but they rejudged it later and it's now AC.

Apparently the problem-setter's code didn't correct for the possible long long overflow which occurs when taking a sum of all the damage the Hero is going to take.

→ Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

The problem Div 1A/2C , could be many local minimals ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1 B caught me completely off guard.

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

good problems but weak pretests

→ Reply
»
4 years ago, # |
  Vote: I like it +54 Vote: I do not like it

If you like videos, here's one that happens to have all the div. 2 solutions

→ Reply
»
4 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Nice Div1 B1 editorial

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Man my Div2 C/Div1 A Binary Search solution with 5*Log2(n) gave TLE on test 11 this is not right man. can anyone tell me the reason for TLE in this solution https://codeforces.me/contest/1480/submission/106790379

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was anyone able to figure out why TC 11 of problem C gives FST?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are not storing the values after the query. This results in repeated queries. I did the same thing. :`(

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah but I'm using only 3 queries at max. each time before reducing binary search range,which happens 18 times(worst case). That is still less than 60 queries.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's exactly what I thought. But the accepted solutions I have seen differ from mine in just this one aspect. Well the sys tests are almost over. Let's see what was the reason.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the proof of div2C why is binary search working here

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Imagine it as hills. If you are at a valley, you don't need to move. If you are at a peak, you can go in either direction. If you are at a slope, just go down the slope until you get to a valley.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      for n=7, if the array is — 3 4 5 6 7 1 2 ,then the only local minima is element 1 at index 6.but firstly the mid is element 6 ,which is greater than the previous element 5,so,according to gfg solution i have to go to the left portion doing high=mid-1,but there is no local minima in the left. Can you explain this?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        3 is also a minimum since the ends are +inf (in the question).

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but will the solution work if the numbers are not distinct?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Idts there will be cases of flatland and you wouldn't know if it is a plateau or a basin. It also depends on the way you define local minimum. Since 3 points at same height can be considered local minimum then this idea should work.

        → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Can hos.lyric and maroonrk explain their solutions to Div1E? It seems that they used different solutions from the one in the editorial (which uses very advanced generating function techniques).

(I know maroonrk's solution got TLE, but the fact that it only failed on test 76 indicates that it is probably a correct solution with a high constant factor.)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    My solution is light $$$O\left(\sum_{i=1}^m a_i + m \log \mathit{MOD}\right)$$$.

    The calculation of the potential function is the same as the editorial. After that (using the notation of the editorial) we keep track of $$$g(0) + \cdots + g(a)$$$ as a fraction with denominator $$$(n - 1) \cdots (n - a)$$$ so that we can compute the numerator and the denominator without division modulo $$$998244353$$$. We only conduct divisions only when $$$f(a_i)$$$ or $$$f(n)$$$ is actually needed. The bottleneck is $$$3 n$$$ multiplications modulo $$$998244353$$$, which I hoped to pass.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +21 Vote: I do not like it

    There's a simple form for $$$f(a)$$$. Define $$$prod(r,l)=l\cdot (l+1)\cdots r$$$. From the editorial, $$$f(a)=0$$$ and

    $$$g(a)=f(a+1)-f(a)=-2\cdot \frac{prod(2n-1,2n-a)}{prod(n-1,n-a)}.$$$

    You can verify that

    $$$f(a)=-2\cdot \frac{n}{n-1}\cdot \left(\frac{prod(2n-1,2n-a)}{prod(n,n-a+1)}-1\right).$$$

    Looks like maroonrk precomputed some factorials to evaluate $prod(r,l)$ quickly, but as noted above, this is not necessary to pass.

    https://codeforces.me/contest/1479/submission/106861209

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it +55 Vote: I do not like it

    I think the editorial is a little long winded; here's my high level summary.

    Section 1 of the editorial: finding a closed form

    First, it's not too hard to convince yourself that the expected stopping time from any state is of the form $$$f_n(n) - \sum f_n(a_i)$$$ for some function $$$f_n$$$. We can write out a system of linear equations using the transition probabilities, and explicitly solve it to get a solution $$$f_n(0) = 0$$$ and $$$f_n(k) - f_n(k-1) = \prod_{i=0}^{k-1} \frac{2n-i}{n-i}$$$. (Note that there are actually many solutions, $$$f'_n(k) = f_n(k) + ak$$$ is a valid solution for any $$$a$$$, and we can even pick it so that $$$f'_n(n) = 0$$$ so that the stopping time is just $$$\sum -f'_n(a_i)$$$. This is the simplest form though.)

    Section 2 of the editorial: evaluation

    All that remains is to evaluate $$$f_n(\cdot)$$$ efficiently. The submissions you're referring to all just evaluate $$$f_n$$$ in $$$O(n)$$$ time using the formulas given above; if you take some care to avoid doing modular divisions, you can just squeeze it through. That's why these submissions look so much shorter than the editorial; they are using the exact same closed form though.

    The editorial describes ways to evaluate everything in $$$\tilde{O}(\sqrt{n})$$$ time. These are very similar to the techniques to compute large factorials quickly; essentially, you expand the product of $$$\prod_{i=0}^{\sqrt{n}} (x+i)$$$ as a polynomial in $$$x$$$, and then use multipoint polynomial evaluation with FFT to evaluate it for $$$x = \sqrt{n}, 2\sqrt{n}, \ldots, n$$$. The formulas in this version are slightly more complicated, but the techniques are pretty much the same.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I haven't seen anyone else fail for test 55 for problem C, could someone point me in the right direction/test case as to why my solution is wrong? I can't see the test for it as of yet.

submission:

I've considered the case for n == 1 & 2.

I'm not using an array to store the values which apparently could lead to repeated queries, but people seem to be getting a TLE in an earlier test case for this.

Perhaps my binary search implementation is skipping over an element for the minimum.

As always, apologies for the god awful formatting, it's my first time solving an interactive problem.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're querying for out of bound indices. When mid = 1, you'd query for index 0 as well.

    → Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Solution of Div1 B1 is so... big.

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Any idea why my code fails for Test Case 55?

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +26 Vote: I do not like it
Did somebody order a heartbreak?
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    B passed on rejudging! ily liouzhou_101.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      liouzhou_101 I feel my submission is wrong. And there are many submissions like mine. The mistake I did is I checked if the hero's health before giving the final blow is >= 0 instead of > 0 (i.e. totalAttack — max(a) <= B instead of < B).

      Please rejudge (I know I'll lose my rating but a mistake is a mistake :))

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Ah yes, I did the same mistake but got AC in B. I guess they trimmed the test cases in a hurry. Should rejudge or just revert the ratings. Latter would be easier I guess.

        → Reply
»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

My incorrect solution passes for D1.. Weak main tests as well :/

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please help me understand why I got a WA? 106825850. I can see that my fundamental understanding of binary search is wrong, but I'm not able to understand why there's a problem when taking the range as [l m-1] instead of [l m]

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you update the range to [l m-1] instead of [l m] in the case a_m < a_m+1, you disregard the possibility that a_m might be a local minima itself(it's already lower than a_m+1, it could be lower than a_m-1 making it a local minima) and exclude it from your range.

    → Reply
»
4 years ago, # |
  Vote: I like it +39 Vote: I do not like it

liouzhou_101 I don't think changing the constraint after the contest makes sense, as we solved for the given constraints only and overflow wasn't handled then I think the author should rejudge with correct answers instead of changing constraints after the contest.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I think authors would rather change constraints and keep the round rated than get 90% (according to Anton) of solutions FST and a massive outrage.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      But how is that fair to remaining 10%. Also, the reason for massive outrage wouldn't be 90% FST but the weak pretest leading to such outcome.

      Anyway please avoid such solutions in future.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I can see your point, and I understand why you would be upset about the changing of the constraints. However you also have to look at it from the authors' perspective. They really only have three options:

        1. Make the round unrated
        2. Keep the constraints and cause 90% of all solutions to FST
        3. Change the constraints so unintended overflows are no longer an issue

        What would you do?

        → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +62 Vote: I do not like it

Alternate solution for Div1B/Div2D, works for both versions of the problem:

Consider painting the array one element at a time, from left to right. After painting $$$a_i$$$ either white or black, one of the two subsequences $$$a^{(0)}$$$ or $$$a^{(1)}$$$ must have $$$a_i$$$ at its back. Since the only relevant properties of the subsequence are their last elements and total number of groups so far, we can almost solve the problem with a DP, where $$$dp[i][x]$$$ is the largest (smallest for B2) number of groups that can be achieved after coloring $$$a_1, \ldots, a_i$$$ such that the two elements at the end of the subsequences are $$$a_i$$$ and $$$x$$$. The DP transitions are not hard to figure out, but are a bit messy. This isn't quite enough to solve either problem, though, because the bounds are too large for an $$$O(n^2)$$$ DP to pass directly. But for all values of $$$i > 0$$$ and $$$x \neq a_{i-1}$$$,

$$$ dp[i][x] = dp[i-1][x] + \left\{\begin{array}{cl} 0 & \text{, if } a_{i-1} = a_i \\ 1 & \text{, if } a_{i-1} \neq a_i \end{array}\right\}, $$$

...and by keeping only the most recent row of $$$dp$$$, and storing it as a segment tree, all $$$n$$$ transitions of this type for a given value of $$$i$$$ can be performed in $$$O(\log n)$$$ with a single lazy range-increment. The value of $$$dp[i][a_{i-1}]$$$ can be calculated using a few range-max queries (range-min in B2), also in $$$O(\log n)$$$ time. This leads to a total time complexity of $$$O(n \log n)$$$.

For ugly nearly-identical implementations, compare 106829611 with 106850293.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +43 Vote: I do not like it

    I do solved Div1B1 also using DP but with a little trick.106809164

    My DP was $$$O(N^3)$$$ dp[i][last value painted white][last value painted black]. Which is TLE/MLE obviously.

    I had to reduce it so I renumerate the array a with numbers 1,2,3,4.

    If an element is different from the last three I renumerate it with a value not in the set of new values of the last three elements.

    Else I renumerate it with the same new value of the one that match it in the last three.

    Then I run my O(N*4*4) DP and get the answer .

    I don't know if my idea is correct or the system test are weak. But I passed system test (^_^). Anyway my delta is -13 and I get back to expert(-_-).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Any idea why your solution does not work for B2? BTW, I really liked your solution. Mine was...........quite nasty.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        check this testcase-

        n = 11

        array a = 2 3 10 3 3 8 9 2 11 10 3

        array b would now be = 1 2 3 2 2 1 3 4 2 1 3

        so when we perform dp on this new array for example the 1 at index 5 can get merged with 1 at index 0 which is not originally possible for array a and the result will be less than original answer

        → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Also, this idea can be implemented in $$$O(n)$$$ without a segment tree, consider the changes to dp array, you will add 1 to each but one element, or change only one element, so you'll need a variable that stores a lazy value, the dp array, and the minimum dp (or maximum), see my D1B2 code for further understanding.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate your solution and approach?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        As i said, my idea is the same as the one explained here, for the implementation I used the Venice Technique, you can find more information about this in this tutorial.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hey! Thank you for providing the tutorial for the technique.

          In the original solution it is mentioned "The value of dp[i][ai−1] can be calculated using a few range-max queries"?

          I understand the transition of dp[i][x], can you explain how are we calculating dp[i][ai-1] perhaps?

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain what you meant by storing the dp array as segment tree? I am new qto this approach, it'll be great help. Thanks

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a test-case for which my code fails (Div2 B)?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    "In each fight, the hero can select an arbitrary living monster and fight with it."
    You can check this.
    10 10 2
    11 5
    5 5
    The Answer will be "YES" if he fight with the second monster first and then the first monster.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked the problemset

Especially div2 C, it increased my understanding of binary search.

I loved solving div2 C.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, could you please help me with this

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your program stops for all cases where the array is a[i]=i (1-based) without outputting any "! x" prompt.

      You need to output variable "hi" after the binary search if you are unlucky enough.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ahh, I got it now, thank you!! In general though, I'm not able to understand why sometimes, the range is fixed as [l mid] [mid r] or at other times like: [l mid] [mid+1 r] or like how I'd mentioned earlier (I've tried variants earlier and realised they either get a WA or TLE). Are there are generalisations to binary search? Could you also clarify that/ suggest any resources where they've explained this?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It depends if you round down or up when getting the "mid" value. If you round down, you need to have [l mid][mid+1 r] (For example range [2,3] and you round down to mid=2, [2,2] and [3,3]) but if you do [l mid-1][mid r] you either get a case where r<l or an infinite loop (TLE).

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ahh! All the while I was only thinking that we take the range as [l, mid-1] because we don't require the mid value (if eg, mid > x) and likewise for eliminating the unnecessary mid value in the higher end, the range is made [mid + 1, r]. I now understand that it's also about maintaining proper values in the boundary.

            How exactly to round down though? Or is it recommended to round up? One more query... how to find when to round up/down.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              C++ automatically rounds down when there is a decimal if the data type is int. There is no difference to round up or down in time complexity or ability to find the target, you just need to change the ranges. Therefore, you can choose to round up or down in any case

              → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Please help me to find bug in my code it's failing at test case 21

        div2 C

        106868099

        UPDATE: GOT IT, I was printing '?' instead of '!' at one place

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

106841211 why does my submission for div2 D1/div1 B1 fail ?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I am not asking if my binary search is correct because I sort of just believed the pretest would sort it out for me. But I think its impossible my loop breaks without having found the answer.

It said my answer was wrong instead of query limit exceeded. So it must have broke but it wasnt the answer?

https://codeforces.me/contest/1480/submission/106784965

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are comparing the query responses as strings rather than as ints.

    → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I know a solution for div1D that is not randomised. I know that it's correct but I can't make it fit the TL a little bit. It works 6.1 seconds on codeforces.
Let cnt[i][j] = s(v, 0, j) mod 2. This array takes O(n^2) memory so we have to make it smaller. We can do this using persistent segment trees and dfs. Now we can calculate cnt in O(n log n) time and memory.
How to answer queries using cnt? The answer is any non zero number in
(cnt[u] ^ cnt[v] ^ [1 if k == a[lca(u, v)] else 0 for k in range(n)])[l..r]
Let's change a[lca(u, v)]th bit in cnt[u], then we need to find any different bits in 2 isomorphic segment trees from l to r. That can easily be done using perfect hashing on subtrees of segment trees.
Sorry for my English. If you have any questions feel free to ask.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    not randomised

    hashing

    Choose one.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      You can do non-randomized perfect hashing on binary trees.
      Suppose that we have only 0 and 1 as values at leafs. This values will be leaf vertices’ hash. Every other vertex has two subtrees. If you don’t know the hash of some tree you calculate hash of left subtree, then of right subtree, then look up at some map: hash[{left_hash, right_hash}]. If the map has no such key you set it’s value to counter++, which is set to 2 in the beginning. Otherwise, you already know the hash.
      So my solution is still not randomized.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +13 Vote: I do not like it

        Hey, I also have a deterministic $$$O((N+Q)\cdot \sqrt{N})$$$ solution, it passes in 3 seconds on codeforces. For the queries on a path, you can use Mo's algorithm on trees. Then when we do Mo's algorithm, we keep track of the evenness/oddness (0/1) of all the minerals. On top of that we keep for each block of $$$\sqrt{N}$$$ minerals the sum of the minerals' oddness values. We can update this structure in $$$O(1)$$$ and check if there is an odd mineral in a range in $$$O(\sqrt{N})$$$. We update many times, but we query only Q times. This makes the above time complexity.

        Edit: I just saw that mohammedehab2002 had exactly the same idea...

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        So you either use an unordered_map which is randomized, or usual map, which adds extra log, so good luck fitting that into TL.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +36 Vote: I do not like it

          Even though unordered_map is randomized, it still has some merit as "better randomized" because it turns the algorithm from Monte Carlo (could be wrong) to Las Vegas (only runtime is randomized). Also, I think the existence of a deterministic dictionary is still open, so we can hold out hope.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it -20 Vote: I do not like it

            Only runtime is randomised, so it's not $$$O((N+Q) \log)$$$.

            → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Optimized AC solution: 106873608. The lesson here is probably not to use std::unordered_map for anything, ever (except maybe strings), because holy crap it's slow. Use __gnu_pbds::gp_hash_table or __gnu_pbds::cc_hash_table instead.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had a few problems where I tried to use gp_hash_table to speed up my solution but it didn't help at all. It only slowed it down. Also strings are not hashable by default so you can't use unordered_map for them.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Also strings are not hashable by default so you can't use unordered_map for them.

        The following seems to be working for me (for example):

        ...
unordered_map<string, int> occ;
occ["abcd"] = 1;
...

        So I don't understand what you mean by that statement; maybe you were referring to something else?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, I thought strings can't be used that way like vectors and pairs. That's pretty cool actually.

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to prove Div1A/Div2C mathematically? I mean how can we prove that there exists a local minima in the left side of the array if $$$a_{mid} < a_{mid + 1}$$$?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    Consider the current mid $$$m$$$, if $$$a[m] > a[m-1]$$$ then the values in the left side (a[m-1] , a[m-2] , ...) must be decreasing untill some index $$$idx$$$ then increasing, then it will be guarnteed that a[idx-1] > a[idx] and a[idx] < a[idx+1].

    You can proof the right side in the same way.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Apply Rolle's Theorem

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In Div2B, my Submission with the condition max(H(k)) >= 0 works. But I believe the correct condition is strictly greater than zero as is mentioned in the editorial. Is this hackable or am I missing something?

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Hello, Can anyone tell me why my solution to Div2 problem B got wrong answer on test 2?
I tried alot, but couldn't find the mistake.

→ Reply
»
4 years ago, # |
  Vote: I like it +96 Vote: I do not like it

Tester here. I have another solution for 1D using MO's algorithm on trees. If you don't know what this algorithm is about, it flattens a tree so that for each path, there's an interval (or maybe a union of $$$2$$$ intervals) in the flattened array such that the nodes in the path occur exactly once in it, and the rest of the nodes occur $$$0$$$ or $$$2$$$ times. And then you use the normal MO's algorithm on the flattened array. Tbh, I thought this problem was custom made for this algorithm, but apparently I was wrong.

So in MO's algorithm, we extend or shrink an interval, and then we update the value on the boundary. Here, we'll flip the parity of the number of occurrences of $$$c_u$$$, where $$$u$$$ is the node on the boundary, and then we want any color that occurs an odd number of times in an interval. So the problem turns into an update-query problem on a binary array which says:

  • update: flip an index in the array.
  • query: find any $$$1$$$ in a range.

Now, this is easy with segment trees, but the complexity will be $$$O(q\sqrt{q}log(q))$$$. However, notice that the number of updates is way bigger than the number of queries. You do $$$O(q\sqrt{q})$$$ updates, but you only do $$$O(q)$$$ queries, so we can instead try to do the updates quickly, on the expense of the queries.

The idea is to use sqrt decomposition instead. Divide the array into blocks of size $$$\sqrt{q}$$$, each maintaining the sum of the elements in its range. Now, you can do the updates in $$$O(1)$$$, but the queries will take $$$O(\sqrt{q})$$$.

Code

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me? Why are these two solutions different?(first, second). Same idea, but different verdict.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the last line in the Greedy Strategy 1 under the intuitive proof of Div2 D1. It says, "Suppose $$$b$$$ results in the two subarrays $$$s′xzs′′$$$ and $$$t′yt′′$$$, while there is indeed another optimal assignment that agrees with our strategy and results in $$$s′xt′′$$$ and $$$t′yzs′′$$$ ".

I don't understand how did our strategy result in $$$s′xt′′$$$ and $$$t′yzs′′$$$ ", why are $$$s′′$$$ and $$$t′′$$$ interchanged and why is this also considered optimal?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    have you figured it out? Can you tell me?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lol no I haven't figured it out yet, no one replied, so I'm still in the same doubt.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        You have to see the difference that it creates.
        With greedy strategy we have
        $$$s'xt"$$$
        $$$t'yzs"$$$
        let's say answer for greedy strategy is $$$ans_{greedy}$$$
        And as for optimal sequence $$$b$$$ we have
        $$$s'xzs"$$$
        $$$t'yt"$$$
        let's say answer for optimal sequence is $$$ans_{optimal}$$$
        Now, $$$t'yzs"$$$ will have one more contribution in the answer than $$$s'xzs"$$$ (x==z). And till now we have $$$ans_{greedy}$$$=$$$ans_{optimal} + 1$$$
        And now in the worst case, $$$t'yt"$$$ will have one more contribution than $$$s'xt"$$$ (worst case is when $$$t"=xt_1$$$ i.e. $$$t"$$$ start with $$$x$$$).
        And now for the worst case we can have $$$ans_{greedy}$$$=$$$ans_{optimal}$$$.
        So, we have shown that our answer with greedy strategy is not worse than optimal sequence.
        Tell me if I am wrong

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah I understand what you're saying, but my main doubt still remains, why is the answer for the optimal strategy $$$s′xzs′′$$$ and $$$t′yt′′$$$? I don't understand what is it in the optimal answer that leads to the exchange of $$$s′′$$$ and $$$t′′$$$ from the greedy answer. According to me, the answer for the optimal answer should be written in the form $$$s′xzu$$$ and $$$t′yv$$$ where $$$u$$$ and $$$v$$$ are arbitrary sequences which are not related in any way to $$$s′′$$$ and $$$t′′$$$.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Editorial is using exchange arguments here. The point is, you're trying to decide whether some decision ( like, where to place $$$z$$$ in case $$$x=z$$$ ) is not worse than the optimal one.

            So, now you say, let's suppose the optimal answer contains criteria other than what our strategy tells us, that is, the optimal answer has form $$$s'xzs^{"}$$$ and $$$t'yt^{"}$$$, where $$$x=z$$$ and $$$y \neq z$$$. Now, this is against our strategy, so we show that if we had also placed $$$z$$$ according to our strategy, we could have made a possible assignment that would not be worse than the optimal. Our assignment would say $$$s'x$$$ and $$$t'yz$$$ and then we have to place the remaining elements, but using a generic $$$u$$$ and $$$v$$$ like you said, you can't compare it to the optimal assignment in question, so we consider 2 assignments specifically ( keeping the internal result of $$$seg(s^{"})$$$ and $$$seg(t^{"})$$$ constant ). (Assuming first characters of $$$s^{"},t^{"}$$$ as $$$S,T$$$ respectively )

            Assignment 1
            Assignment 2

            So, both assignments show that our strategy is not worse than optimal. Also, the editorial just happens to mention one, but any placement of $$$s^{"}$$$ and $$$t^{"}$$$ turns out to work.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah now I understand, thank you. They should include this in the editorial that would be really helpful. Now that you explain it, it seems so obvious, dunno what I was thinking. Nevertheless, thanks a lot!

              → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

liouzhou_101 doesn't look like the Contest Materials have been updated with the link to this editorial post — just FYI.

Thanks for the great contest! Really enjoyed the problems :D

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i wasted all my time on problem B div. 2 because in the contest it told me that my solution had not passed the pretests, and now I see that my solution has been accepted, ok ....

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I became red in the round and I'm so happy!!!

But I have to say I didn't like D very much — its Mo's algorithm on tree solution require not much thinking but the limits were quite tight. My first solution ran for 4960ms and I was afraid that it would fail system tests so I resubmitted after optimizing constant factors (making me rank 70 -> 150) but it turned out that the pretests were just all system tests.

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

I have an alternative $$$O(n)$$$ greedy solution for Div2D12/Div1B12, which is different from editorial and is pretty short, but I am still trying to prove that.
Div2D1/Div1B1: 106865184
Div2D2/Div1B2: 106845535
The preprocessing is combining the same neighboring elements and store it as {$$$val, len$$$} in first problem and {$$$val$$$} in second problem. We call this new array as $$$b$$$.

The basic idea for both questions is that, we want to greedily choose better result when we process current element $$$b[i]$$$ (need proof).
Besides, when we process $$$b[i]$$$, we know $$$b[i-1] \neq b[i]$$$ in our preprocessing. $$$b[i-1]$$$ is the last element in one color, so for another color we want to see what potential elements we can choose. We will maintain a set $$$alter$$$ to record potential available elements. We want to choose a different element in first problem and a same element in second problem.
The elements in $$$alter$$$ can be placed in same or different color with $$$b[i-1]$$$. We can reorder to place any element in $$$alter$$$ to the end of another color. For example, if we have $$$b[i-1]=3$$$ and $$$alter=[1, 2, 4]$$$, then we can make $$$1$$$ as last element of one color by reordering two colors like: $$$[..., 2, ..., 4, ..., 3]$$$ and $$$[..., 1]$$$.

For first problem: when $$$len \geq 2$$$ for some $$$b[i]$$$, then we will distribute it to both colors (need proof). When $$$len = 1$$$ for some $$$b[i]$$$, we need to decide which color to place it. We know that $$$b[i-1] \neq b[i]$$$, so we want to check can we find an element in another color that is different from $$$b[i]$$$, so we check $$$alter$$$. If so, it means that we can place $$$b[i]$$$ in either color, so $$$b[i-1]$$$ is in same color or different color with $$$b[i]$$$, so we can place $$$b[i]$$$ into $$$alter$$$. If not, it means that $$$b[i-1]$$$ must be placed before $$$b[i]$$$, so $$$b[i-1]$$$ is fixed.

Second problem has the same idea and even simpler. We just need to check whether $$$b[i]$$$ in $$$alter$$$ and update $$$alter$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Whose solution for problem D yesterday did not use long long and WA on pretest #2？

Because of this，I waste almost 40min ……

→ Reply
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Did anyone else solve div1B2 with min cost max flow?

→ Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

The data of Div1.D is not strong enough cause my solution with complexity $$$O(n\sqrt{q})$$$ can pass.

Link of my solution -> https://codeforces.me/contest/1479/submission/106839336

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello, could anyone help me with my Div2.C? I used the ideas from gfg after contest but I still get the wrong answer on test 11.Thank you!My submission-> https://codeforces.me/contest/1479/submission/106868187

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

thanks for all. But editorial could be better. You could explain better.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody tell why my solution fail for problem 1479B1?

https://codeforces.me/contest/1480/submission/106875875

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in case:

    6

    2 2 1 3 2 2

    The answer is 6 but your output is 5

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone find out the error in my submission in DIV2D2 ? https://codeforces.me/problemset/submission/1479/106881116 THANK YOU!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have already understand my error in the problem D2,When we use the vector or other data sturctures to solve this problem,We should update the Nxt[i](It's that the next a[i]'s position) when we push or merge to number ,such as this:[1,1],when we make them both are color 0,we should update the Nxt[color0[color0.size()-1]].

    If you have this error,you will be Wrong Answer in test 6.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1A/Div2C

After Learning L02 — Peak Finding, I write this code submission 106878273 but get WA on test 22.

Can anyone give me a hand?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Try for: 6 5 4 3 2 1

    a[n + 1] should be inf.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh! This little bug.

      My mistake a[0] = a[n] = INF, it should be a[0] = a[n + 1] = INF.

      Thanks a lot.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

For Div2 C, My submission got TLE on 7th pretest. I had the same intuition and implemented as given in tutorial. If someone can find out the mistake, it will be a great help. Thanks in advance.

Submission Link : 106890877

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are not changing the values of left and right for the case when curr > left && curr > right.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh Yes! I checked. Just If I had put a simple else it would have got AC. Thanks a lot dude for your time. Really appreciate :)

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem authors please next time google your problem or select testers for it

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem:1479B2

I think there is a typo in editorial, in line before lemma 1, f(i) = max (g(j)) should me min if I am not wrong.

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Best contest ever!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can watch this https://youtu.be/sUFMuqQlL6M if you are stuck in C

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am facing some problems finding why my program is failing for test case 6 in Painting the Array I (Div2 — D1) problem. If anyone could point out what's going wrong, it would be great. Thanks in advance!!

Link:- (http://codeforces.me/contest/1480/submission/106896644)

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

I have another explanation (or solution) for Div1B1/Div2D1. Sorry I'm not very good at English, you can just read my code(106872452).

First, let $$$a^{(0)} = a$$$(all elements in a) and $$$a^{(1)} = []$$$(empty). Let's move some elements from $$$a^{(0)}$$$ to $$$a^{(1)}$$$. If a segment in $$$a^{(0)}$$$ has two or more elements, then we can move one element in this segment to $$$a^{(1)}$$$. After that, $$$\mathit{seg}(a^{(0)})$$$ will not decrease and $$$\mathit{seg}(a^{(1)})$$$ will increase or stay unchanged. For example, If $$$a^{(0)} = [1,1,2,3,4,4]$$$, after such operations, $$$a{(0)}$$$ became $$$[1,2,3,4]$$$ and $$$a^{(1)}$$$ became $$$[1,4]$$$. Let answer = $$$\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$$$.

But that's not enough. Consider a case $$$a = [1,1,2,3,1,1]$$$. We can construct $$$a^{(0)} = [1,2,3,1], a^{(1)} = [1,1]$$$ using the method above. But we can move $$$2$$$ in $$$a^{(0)}$$$ to $$$a^{(1)}$$$, decreasing $$$\mathit{seg}(a^{(0)})$$$ by $$$1$$$ and increasing $$$\mathit{seg}(a^{(1)})$$$ by $$$2$$$. So we should perform another type of operation. If there exists $$$a_i$$$ between two segments($$$seg_x$$$ and $$$seg_y$$$), and all elements in $$$seg_x$$$ and $$$seg_y$$$ are equal to one value $$$v$$$, and $$$a_i \neq a_{i-1}, a_i \neq a_{i+1}, a_{i-1} \neq a_{i+1}, a_i \neq v$$$, then we should increase answer by $$$1$$$, because we can move $$$a_i$$$ from $$$a^{(0)}$$$ to $$$a^{(1)}$$$.

Examples
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain it again I didn't get that

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I added some examples to explain it.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I used same method but instead of checking this much inequalities,if we have A[i]!=A[i+1] && A[i]!=v&&A[i+1]!=v because if this is true then we can simply break sequence here only. And this condition is enough because only structure of example which don't follow this looks like 1 1 5 1 2 1 2 1 3 1 1, Here we can see no a[i]!=v && a[i+1]!=v simultaneous.(v) is 1 here. In this case answer will increase only by 1 always otherwise always by 2 if we break sequence at i and i+1. For example [1 1] 5 1 2 (4 2) 1 3 [1 1] sequence a can be like 1 5 1 2 4 1and sequence b be like 1 2 1 3 1.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
1000 1000 4
200 300 500 400
1000 1000 1000 1000

For a testcase like this for problem B, the answer should be "NO" since the hero dies after the 3rd round. However, the solution given in the editorial gives us "YES".

This is confusing. Am I missing something?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Explain this please
Corner case that is inside the new limits removed..
Problem D2B
This was Test #23 earlier
1
3 10 1
2
16
liouzhou_101 MikeMirzayanov

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

In the editorial of D, what does "consistent segment tree" mean? Is it persistent segment tree?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in Div2 C how come we sure that when l==r that is minimum?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We are not required to find the global minimum, just a local minimum which is defined as — a[i] < min(a[i-1], a[i+1])
    — or equivalently — a[i] < a[i-1] and a[i] < a[i+1].

    Notice that before and after every step of binary search the range [l,r] satisfies the condition: — a[l-1] > a[l] and a[r] < a[r+1].

    Hence when l==r we obtain a local minimum

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Div1 C reminds me of this problem on AtCoder.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div2.D1 I submitted this code and got AC. But in fact it's quite different from the tutorial! Can anyone hack it or prove it right? Thanks!

PS: I had run thousands of testcases on my computer with n<=20, and it is always right.

Sorry for my bad English :(

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Super short solutions for Div1.B:

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain it please?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

      I will describe the full solution for B1 that I came up during the contest and simplify it.

      Let $$$dp[s][i-1] = (v_{s,i-1}, k)$$$ be the state of current solution when $$$a[i-1]$$$ is added to the sequence $$$s$$$ ($$$s \in \lbrace 0,1 \rbrace$$$), in which $$$v_{s,i}$$$ is the best score ending at $$$i-1$$$ and $$$k$$$ is the index of the last item of the other sequence $$$s' = 1-s$$$ (of course, $$$k < i-1$$$ and $$$k = 0$$$ when $$$s'$$$ is empty as I read the input into an 1-indexed array).

      Let's focus on $$$s = 0$$$. When reaching item at index $$$i$$$, we have two options:

      1.1 Adding $$$a[i]$$$ to the sequence $$$0$$$: we update $$$dp[0][i] = (v_{0,i-1} + [a[i] \neq a[i-1]], k)$$$

      1.2 Adding $$$a[i]$$$ to the sequence $$$1$$$: we update $$$dp[1][i] = (v_{0,i-1} + [a[i] \neq a[k]], i-1)$$$ as now $$$a[i]$$$ is appended to sequence $$$1$$$ that is ending with $$$a[k]$$$ .

      Similarly for $$$s = 1$$$, we have two updates:

      2.1 $$$dp[1][i] = (v_{1,i-1} + [a[i] \neq a[i-1]], k)$$$

      2.2 $$$dp[0][i] = (v_{1,i-1} + [a[i] \neq a[k]], i-1)$$$

      So, $$$dp[0][i]$$$ can be updated by one of two ways 1.1 and 2.2. Of course, we choose the one giving the better score, so $$$dp[0][i] = max((v_{0,i-1} + [a[i] \neq a[i-1]], k), (v_{1,i-1} + [a[i] \neq a[k]], i-1))$$$ (1)

      In 1.2, there one important point is that there can be many values $$$k$$$ that yield the same best $$$v_{0,i-1}$$$. In this case, $$$a[i] \neq a[k]$$$ is always true as we are always able to chose one $$$k$$$ that $$$a[i] \neq a[k]$$$. The trick I did is, as the input array is 1-indexed, and $$$a[0] = 0$$$, when updating $$$dp[0][i]$$$ by formula (1), if two scores are equal and $$$k \neq i-1$$$, I set $$$k = 0$$$ , so $$$a[i] \neq a[k]$$$ is always true for subsequent steps.

      Simplification

      There are two simplifications to make the code shorter:

      • As the role of $$$s = 0$$$ and $$$s = 1$$$ are the same, we can remove the first dimension of $$$dp$$$ and only need to handle $$$dp[i]$$$.
      • As we only need $$$dp[i-1]$$$ and $$$dp[i]$$$, $$$dp$$$ is reduced to an 2-element array, i.e. $$$dp[2]$$$.

      The idea for B2 is similar.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain Div2/ D2 problem?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it the following way. First of all, i merged every contiguous segment of equal elements into one (since every segment of the form $$$[5, 5, 5, 5]$$$ will always belong to either $$$a0$$$ or $$$a1$$$). Then let $$$dp[i]$$$ be the minimum total number of segments up to position $$$i$$$. For each element $$$a[i]$$$, we either append it in the same set of the previous element $$$a[i-1]$$$, so we get $$$dp[i] = dp[i-1] + 1$$$ or we try to append it to the previous occurrence of this value (if there is any), therefore having : $$$dp[i] = dp[lst[a[i]+1] + i -lst[a[i]] - 2$$$ ($$$lst[a[i]]$$$ is the index of the last occurrence of this value in our array), because we need to put all elements between two equal numbers in a different set. Finally, the transition for each $$$i$$$ is:

    $$$dp[i] = min( dp[lst[a[i]+1] + i -lst[a[i]] - 2, dp[i-1] + 1)$$$.

    Solution code : https://codeforces.me/contest/1480/submission/106923311.

    I hope i made myself clear.

    → Reply
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Could someone explain how you get $$$\mathcal{O}((n + q) \log n)$$$ in div 1 D?

The way I see it, with the persistent segment tree solution, for a fixed path, you can check in $$$\mathcal{O}(\log n)$$$ time whether there is a working value in the range $$$[l, r]$$$. Don't you need to binary search for what that value actually is, thus taking $$$\mathcal{O}(\log^2 n)$$$ time?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Additional binary search is not necessary. You can get what the value is through a binary search on segment tree.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The 20th input of test #2 for problem '1480B — The Great Hero' reads:

320995 -54033 3
783399 76765 77638
140538 647490 973129

That is, the hero is dead on arrival since B is negative. Yet the answer for the 20th token is YES. How can the hero start fighting when he is already dead? Shouldn't the answer be NO?
I am sure I fail to grasp something, but it eludes where I am wrong.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You got B = -54033 after you changed its value. Move your check to the beginning of program, or localize B variable.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for very clean solution codes and pretty understandable tutorials!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Liked problem C. If anyone wants the reason that solution works - http://www.dsalgo.com/2013/02/index.php.html

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"O(MO)" — One more alternative approach (or explanation) for Div.2 D1.

Step 1. It is obvious that we can remove all excesses of consecutive equal elements from an initial array without influencing the result. The excess is when >2 equal elements come in a row. We then reduce to 2 elements.

Now every second element would come to different array except of the pathological pattern (step 2).

Step 2. We search for patterns /OO(MO)+O/. Here M stands for "not O" or for . (i.e. any element) because of reduction by step 1. The middle side O(MO)+ gives us one unsqueezable array, and concat('O','O') gives us another which is sqeezable by one (so it reduces an answer by one). Patterns may overlap by 2 elements.

Answer is a number of elements in reduced array (after step 1) minus a number of patterns found (in step 2). $$$O(n)$$$

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Btw, 22 vertices is sufficient in div1C.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please check my code and tell me the error in my logic for Div2 D1:/ https://codeforces.me/contest/1480/submission/107013163

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I wrote the following part to get random numbers. (Div.1 D)

srand(time(NULL));
for(int i=1;i<=n;++i)
	for(int j=0;j<64;++j)
		X[i]=X[i]<<1|(rand()&1);

It failed to pass test 7.

After debugging for a really long time, I changed it into the following.

srand(time(NULL));
for(int i=1;i<=n;++i)
	X[i]=1ull*rand()<<60|1ull*rand()<<45|1ull*rand()<<30|1ull*rand()<<15|1ull*rand();

Then it got AC but I haven't known why. Can someone please explain the reason that the first one failed but the second one passed? Thanks in advance.

PS: You can have a look at the two submissions here and here.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you conclude D in $$$O(n \log n)$$$ time? I did basically what you have described but my final complexity is $$$O(n \log^2 n)$$$ and squeezing it into TL was pretty painful. Each of these values $$$f(1, u, l, r)$$$ that you mention I compute in $$$O(\log n)$$$ but in order to find desired $$$c$$$ I perform binary search on this interval which adds extra log. And tree that you describe is called persistent, not consistent. To be precise, in my tree "time" corresponds to colors, I have a root for every single segment tree corresponding to vertices with colors $$$\le r$$$ and in particular I compute $$$f(1, u, l, r)$$$ as $$$f(1, u, 1, r) \oplus f(1, u, 1, l - 1)$$$

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Here's my $$$O(n \log n)$$$ solution:

    First notice $$$f(u,v,l,r) = f(1,u,l,r) \oplus f(1,v,l,r) \oplus f(lca(u,v),lca(u,v),l,r)$$$ (note that $$$f(lca(u,v),lca(u,v),l,r)$$$ is simply $$$X_{a_{lca(u,v)}}$$$ if $$$l \leq a_{lca(u,v)} \leq r$$$ and $$$0$$$ otherwise).

    Therefore it's enough to maintain a persistent segment tree for each vertex $$$u$$$ which answers queries $$$f(1,u,l,r)$$$, I'll denote its root as $$$ST_u$$$. We can get $$$ST_u$$$ from $$$ST_{parent(u)}$$$ by updating position $$$a_u$$$ with $$$X_{a_u}$$$.

    To answer a query for path $$$(u,v)$$$ of mineral resources in $$$[l,r]$$$, we can as usually split this into $$$O(\log n)$$$ ranges $$$[l_1,r_1],\dots,[l_k,r_k]$$$ which correspond to the segment tree nodes. Then notice that a range $$$[l_i,r_i]$$$ will contain the answer iff $$$f(1,u,l_i,r_i) \oplus f(1,v,l_i,r_i) \oplus f(lca(u,v),lca(u,v),l_i,r_i) \neq 0$$$. Therefore, while querying, when we're in some range, we can see whether the current range contains an answer without descending further. Then, to retrieve it, we only need to descend one of these $$$O(\log n)$$$ ranges (any one for which we know it contains the answer), adding $$$O(\log n)$$$ to the complexity (since at each step of the descent we know which subtree will contain the answer), and together it's still $$$O(\log n)$$$ per query. Turns out this is very easy to implement, we can always just check if an answer exists in the left subtree, if it does return it, otherwise try finding it in the right subtree of the current segment tree node. All we need for a query is $$$ST_u$$$, $$$ST_v$$$ and $$$lca(u,v)$$$.

    int query(Node *a,Node *b,int l,int r,int ql,int qr,int lc)
{
    if(ql>qr) return -1;
    if((a->h^b->h^(l<=val[lc]&&val[lc]<=r?x[val[lc]]:0))==0) return -1;
    if(l==r) return l;
    int m=(l+r)/2;
    int res=query(a->l,b->l,l,m,ql,min(qr,m),lc);
    if(res!=-1) return res;
    return query(a->r,b->r,m+1,r,max(ql,m+1),qr,lc);
}

    Full code: 107109427

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Oh wow, it makes perfect sense, thanks. The difference between your and mine approach is that I created persistent trees in a line by adding colors from left to right and each tree is over space of preorders, but your persistent trees create original tree since you are adding persistent tree for each vertex of a tree and each tree is over space of colors. I didn't think you could pull off tricks like that

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the case 2 of the intuitive proof of the div.2D, how do you guarantee that t1 must be following z when putting z after x according to your greedy strategy? what if next(z) > next(y)?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks a lot for including such a detailed proofs!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you please tell me the meaning of this line in B1: Suppose b results in the two subarrays s′xzs′′t′yt′′, while there is indeed another optimal assignment that agrees with our strategy and results in s′xt′′t′yzs′′. Update: Got it.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Managed to solve ProblemD deterministically using (MO's on tree + sqrt decomp) to find first odd beteween l and r. Is not very hard solution 108831828. Is it intended to not pass, since it it $$$(N+M)sqrtN$$$. However I have to admit I quite like more the author's solution since it has high enough probability and is faster, and probability of success could be increased easily.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

sorted

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

With C++ 20, the slower $$$O(q\sqrt{n})$$$ solution for 1D can actually run in <1 seconds which is quite faster than most implementations of the $$$O(n\log{n})$$$ intended solution.

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

About the editorial for 1479E — School Clubs, what is an event, and what is does ϕ(At+1)−ϕ(At)∣A0,A1,…,A mean?

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a counter test for this submission of Div-2 D1

https://codeforces.me/contest/1480/submission/227039682

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What algorithms div1 D's test 51 hacked?

→ Reply