Error_Yuan's blog

By Error_Yuan, history, 3 months ago, In English

Thank you all for participating in the round!

We apologize for the wrong checker in problem E at the beginning of the contest, as well as the weak tests in problem B. To be honest, all the hacked submissions have similar logic and codes in B, which made me suspicious. Anyway, we are sorry for the inconvenience! >_<

Rating Predictions

2029A - Set

Author: Otomachi_Una
First Blood: Benq at 00:00:51

Hint
Solution
Code (C++)
Code (Python 3)
Rate the Problem

2029B - Replacement

Author: wyrqwq
First Blood: Benq at 00:02:30

Hint
Solution
Code (C++)
Code (Python 3)
Rate the Problem

2029C - New Rating

Author: Error_Yuan
First Blood: ksun48 at 00:05:34

Solution 1 (with hints)
Solution 2 (with hints)
Code (Solution 1, C++)
Code (Solution 2, Python 3)
Rate the Problem

2029D - Cool Graph

Author: Error_Yuan
First Blood: ksun48 at 00:13:24

There are many different approaches to this problem. Only the easiest one (at least I think so) is shared here.

Hint 1
Hint 2
Solution
Code (C++)
Rate the Problem

2029E - Common Generator

Author: Error_Yuan, wyrqwq
First Blood: ksun48 at 00:23:50

Hint 1
Hint 2
Hint 3
Solution
Code (C++)
Rate the Problem

2029F - Palindrome Everywhere

Author: sszcdjr
First Blood: taeyeon_ss at 00:16:50

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
Code (C++)
Bonus 1
Bonus 2
Rate the Problem

2029G - Balanced Problem

Author: wyrqwq, Error_Yuan
First Blood: taeyeon_ss at 00:56:22

This problem has two approaches. The first one is the authors' solution, and the second one was found during testing.

Solution 1 (with hints)
Solution 2 (with hints)
Code (Solution 1, C++)
Code (Solution 2, C++)
Rate the Problem
Bonus

2029H - Message Spread

Author: sszcdjr
First Blood: Benq at 02:04:40 (though unintended brute force), jiangly at 02:55:12 (intended, orz!)

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)
Rate the Problem

2029I - Variance Challenge

Author: Error_Yuan
First Blood: rainboy at 01:33:40 (intended, the only solve in contest, orz!)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Code (C++)
Rate the Problem
  • Vote: I like it
  • +136
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

fast edi yay!

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

I do C with binary search. It's really crazy to see the binary search in this problem.

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

I screwed up the 3rd claim for E I thought only primes less than equal to $$$\frac{A}{MinDiv[A]}$$$ will work (for composite A)

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

    Same here. I made a false proof.

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

    Exact same bro, I didnt realize you get 2 as divisor by just going to 2*p. Realized a minute too late

»
4 weeks ago, # |
  Vote: I like it +116 Vote: I do not like it

I had a slightly different approach for D: for each edge (u,v) with u!=1,v!=1, do operation (1,u,v). then you have a star-tree centered at 1, and a bunch of lone-nodes, then do as in the editorial to connect the lone-nodes

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

    Cool solution! Nice idea, easier to implement than the solution in the editorial (in my opinion) and linear time complexity.

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

    And here is what I think to be good implementation of this idea in $$$O(n+m)$$$

    Implementation

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

In B, if(count of 1 in s — count of 0 in r(don't check for last element in r)==1) cout<<"YES";

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hah, I like the Palindrome one

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I thought of C as dp but screwed up because for some reason my mind didn't tell me that it's enough to store the maximum rating in the dp

»
4 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

rainboy is like just so cool ! is he indian ( i saw some grp photo ) ?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +85 Vote: I do not like it

H: Thanks for setting the time limit just above my solution's runtime! :)

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Our testers' solution (which is $$$\mathcal{O}(n^2\cdot 2^n)$$$) runs for ~10s. :(

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

for c can any one show there recursive dp solution ?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

O(n+m) solution for problem D 290751143

»
4 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

in problem E,why are we only considering lowest divisor of x i.e mind(x) for checking if x can be obtained from any generator?

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

    Because for any x, the minimum divisor is either an odd prime or 2, if it's 2 then it can easily be obtained, if it's not 2 then x — mind(x) is even which reduces the problem to checking even numbers only, and for a prime generator p not equal to 2, we can generate all even numbers >= p * 2

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      why is it necessary that we get x from x-mind(x) only,its just written as a statement,why cant we get x from (x-y)+y where y is some other divisor other than the minimum one?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        We can always get x from another x — y. mind(x) is taken for proof's sake.

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

        Because, we can generate all even numbers from a certain point. x — mind(x) basically gives you the largest even number smaller than x that can produce x, let's call it y. That is because if mind(x) | x then mind(x) | x — mind(x). It's kind of like the euclid algorithm for gcd. If you subtract a divisor of a number from the said number, the result will still be divisible by the said number. Basically, you can use larger divisors but there is no point because the difference will always be even, and if we can generate an even number n then we can generate any larger even number. So if any divisor works, then any smaller one does too

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

      why are we sure that x-mind(x) can generate x?

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

        X-mind(x)+mind(x)=x,mind(x) divides (x-mind(x)) so we can add it in x-mind(x) to get x

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually for problem E it turned out that it's possible to get AC with time complexity $$$\mathcal{O}(\sum n + tV)$$$, though it required me to use bitsets, fast input/output template and some number of identical submissions till i got the lucky one 290762920.

Also one of my TL'ed submissions during the contest passes with 1.3s after the system testing. Is there any reason? 290772979 and 290758813

»
4 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I had a simpler DP approach for problem C:

Let $$$ \text{dp}[i] $$$ represent the maximum rating that can be achieved such that $$$ r \leq i $$$.

The base case is $$$ \text{dp}[1] = 0 $$$.

Either $$$ r < i $$$ or $$$ r = i $$$. Hence,

$$$ \text{dp}[i] = \max\left( f(\text{dp}[i-1], \, a[i]), \, \underset{1 \leq j < i}{\max} (f[j]) \right) $$$

The definitions of $$$ f(a, \, x) $$$ and $$$ f[i] $$$ are the same as given in the editorial.

The final answer is simply $$$ \text{dp}[n] $$$.

Code: 290775108

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    i cant process this at all

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

      I think it's pretty clear for $$$r < i$$$, it's $$$f(dp[i-1], a[i])$$$.
      Now coming to $$$r = i$$$, you have to choose $$$l$$$ such that after skipping $$$[l, r]$$$, you get the maximum rating possible, that's what the second term represents. Let me know if it's still unclear!

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

    thanks!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

script>hihi<\script

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I feel like the problem statement of B could have been better

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

There's an $$$O(V^2)$$$ solution in G, see here: 290755809

»
4 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

My solution for D is a bit different:

First I try to remove all cycles, I do so by erasing all edges (u,v) with u != 1 and v != 1, so that all the remaining edges are in the form (1,u), we can achieve this by making moves of the type (1,u,v).
You keep track of the edges being added and removed using a set, this is useful because you keep track of which nodes are connected to 1 or are isolated.
Now all that remains are some isolated nodes and a tree with root 1: all I do is choose a random node A different from 1 in the tree, and for each isolated node B I make the move (1,A,B), as to add B to the tree, then I assign B to A and continue adding isolated nodes to the tree.
Of course, if the tree only consists of 1 and A doesn't exist, you stop there.

»
4 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

Thanks for the contest! About Problem H:

For the $$$\Theta(3^n)$$$ passing, I received too much bonus :) && :(

The problem itself is interesting, and upsolving in $$$O(2^n n^2)$$$ was a nice practice to me. Perhaps "to optimize it." in the editorial hides a tough detail — something like semi-relaxed convolution is unavoidable, right?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I'm afraid your $$$\Theta (3^n)$$$ is way too fast, sad as one of the setters, but anyway congrats!

    On "hiding a tough detail", here is sszcdjr's opinion: nearly every Chinese knows it.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      Can you provide more details? I feel that there's a lot of room for improvement in the editorial quality for this problem. I'm stuck on $$$\Theta(2^nn^3)$$$ right now which is slightly too slow.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        I'm sorry but the editorial is written by sszcdjr... Judging from your time complexity, I guess you are having difficulty with the so-called subset convolution technique. (idk if my explanation is correct and clear but I hope so, so plz correct me if there is any mistake)

        We are given $$$f_{0\dots (2^n-1)}$$$ and $$$g_{0\dots (2^n-1)}$$$. We want to calculate

        $$$h_k = \sum_{i \operatorname{or} j = k, i \operatorname{and} j = 0} f_ig_j$$$

        Assume you know how to perform FWT. Then one can see $0$ (why I have to add a random LaTeX here to make the following LaTeX showing properly), $$$i \operatorname{and} j = 0 \iff \operatorname{popcount}(i) + \operatorname{popcount}(j) = \operatorname{popcount}(i \operatorname{or} j)$$$, so let's denote

        $$$F_{i,j} = \begin{cases} f_j, & \operatorname{popcount}(j) = i \\ 0, & \text{Otherwise.} \end{cases}$$$

        (the same for $G_{i,j}$), thus for each $$$s = \operatorname{popcount}(k) \in [0, n]$$$, we can calculate $$$H_s = \operatorname{IFWT}\left( \sum_{j=0}^{s} \operatorname{FWT}(F_j)_i \cdot \operatorname{FWT}(G_{s-j})_i \right)$$$ (it works because it's a linear transform), then $$$h_k = H_{\operatorname{popcount}(k), k}$$$.

        This would work in $$$\mathcal O(2^nn^2)$$$.

        Naturally we can do no adaptation to make it "online", because we calculate $$$h_k$$$ in the ascending order of $$$\operatorname{popcount}(k)$$$ so it still works in the same time complexity when $$$f, g$$$ turn out to have something to do with $$$h$$$ (but for NTT, the case is somehow different).

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 3   Vote: I like it +36 Vote: I do not like it

          Thanks. I understand how subset convolution works but the part that I don't get is the "online" part that you mentioned in the last paragraph.

          Edit: I think I might understand now... will try to implement later.

          Edit 2: Here's a sort of high-level explanation in case anyone has the same issue as I did.

          Like the editorial says, we have some formula where $$$f(S\cup T)$$$ depends on $$$f(S)$$$, $$$g(T)$$$, $$$h(S\cup T)$$$ where $$$g$$$ and $$$h$$$ are precomputed functions. I was calculating $$$f(S)$$$ in layers based on $$$|S|$$$, and at each step I did one subset convolution to get the contributions to $$$f(S\cup T)$$$. This involves doing one SOS transform on $$$f(S)$$$, multiplying with the SOS transforms for $$$g$$$ (precomputed), and then doing the reverse SOS transform afterward. The last step of doing the reverse SOS transform takes $$$O(n\times 2^n)$$$ time, and furthermore iterated over $$$|S|$$$ and $$$|S\cup T|$$$ for $$$O(2^nn^3)$$$ time complexity. The solution is to defer the reverse SOS transform step until you are on the relevant value of $$$|S|$$$, so it's only done once per size for $$$O(2^nn^2)$$$ time complexity.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you came to this time complexity, you definitely understand the editorial much better than I am. I am basically stuck on the first line. What does "Let $$$dp_S$$$ be the probability such that exactly the points in $$$S$$$ have the message" even mean? Probability at what point in time? And then the formula following about $$$\sum_S dp_S \cdot tr_S$$$ I also don't understand the meaning of. Could you please help me a bit here?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          $$$dp_S$$$ means that the probability that there exists some certain time, such that exactly the points in $$$S$$$ have the message.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I ENJOYED ALL PROBLEMS, KUDOS to the authors

»
4 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

In solution 1 of problem G, the notations are not clear at all. Can anyone can explain what does "saved" s pairs of LR mean? Also, what is preL and preR?

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

    preL and preR are just the prefix sum array of cntL and cntR.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

am I the only one who thought C was easier than B

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Conclusion Forces

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Amazing problem C. I had thought about binary searching the answer but didn't come up with the solution, but I managed to solve it using dp. It's really cool to see that both approach work.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey! can you pls tell me about the binary search approach.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D problem's solution is short and useful.My solution is find the rings and delete them, but I can't realize it.

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I'm sorry to hear that... We didn't know the existence of this problem before :(

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Although the statements are very similar, solutions are different enough, no need to apologize :) had a lot of fun solving the problems!

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

C — Kevin's hacking shouldn't go in vain so he must choose at least one element to skip even it reduces his rating.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone explain my tle in problem E 290847100 I think my time complexity is

nlogn + √mx*loglog(mx)*logn + n where mx=max of all ai, i varies from 1 to n and n<=10^5

how do it in my way? can we do it?

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

    For each testcase you allocate vectors (prime and small) of size mx, it takes O(mx) time. You can create and calculate these vectors one time at the beginning.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could anyone help me prove why my solution for problem B https://mirror.codeforces.com/contest/2029/submission/290742944 is correct?

As it's binary, considering string s+r(exclude the final character of string r, as it's irrelevant to the result), only when the number of '0' equals to that of '1' do we return "YES". Otherwise, it would return "NO". Is it just a coincidence for my correctness?

pls help <3

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

    In essence, your solution mirrors AaravSin's solution. Let $$$x$$$ represent the number of 1's in s, and $$$y$$$ represent the number of 1's in r, excluding the last character. AaravSin's solution uses $$$x - (n-2 - y) = 1$$$, which is equivalent to your solution, expressed as $$$x + y = n - 1$$$. Hope it helps.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why I *3400, is this rainboy's opinion?

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem C, can someone explain something lies in this line .

if (a[i] < curg) curg++;
else curg--;

I'm confused about the case when $$$a_i=curg$$$, I understand both cases when $$$a_i>curg$$$ and $$$a_i<curg$$$, but I can't understand $$$a_i=curg$$$, why doing $$$curg$$$-- works just fine?

I'm assuming that when $$$a_i<curg$$$ that means when we take this number it will decrease our rating, so will increase $$$curg$$$ so we can try to get the point we just lost, and when $$$a_i>curg$$$ that means when we take this number our rating will increase so now we need to try to get $$$curg-1$$$ instead of $$$curg$$$, because we just got a new point.

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

    Note that:

    • Now $$$curg = g_i$$$, and we want to calculate $$$g_{i-1}$$$ based on it.

    Then we see that if $$$curg=a_i$$$, when the rating is $$$curg-1$$$, it will increase by $$$1$$$ after the $$$i$$$-th contest, because $$$curg-1<a_i$$$. Thus, $$$g_{i-1}=curg-1$$$ instead of $$$curg$$$.

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

      Thanks for explaining.

    • »
      »
      »
      9 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hey buddy , In problem C , while using Binary search technique , i am confused within this code section ,

      auto check = [&](int k) {
      
      		int curg = k;
      
      		for (int i = n; i >= 1; i--) {
      
      			if (pre[i - 1] >= curg) return true;
      
      			if (a[i] < curg) curg++;
      
      			else curg--;
      
      		}
      
      		return false;
      
      	};
      
      

      For a particular value k , if pre[i-1] >= curg does not hold true and then we move to the first if statement if(a[i] < curg) curg++ . Then will it be worth to check further back because prefix[n-2] will be holding maximum value for every prefix of that index . If at that point prefix value is not maximum then how can we sure that even after increasing curg++ in first if statement answer will exist . Should not we should break the loop in the first if statement . I am confused in the above scenario , please guide or if possible provide any testcase .

»
4 weeks ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the proof of how the array g is constructed in the editorial of solution 1 of problem C (new_rating)?

This my current thought process but for some reason it does not reach me to the conclusion in the editorial?

So, our base case starts from the back. We know that g[n + 1] = k because before we take another contest after finishing the first n contests (all of them) we need a rating of at least k.

Because we have g[n + 1] we can start populating it backwards. So the general question is what is g[i] in terms of g[i + 1]. g[i + 1] basically gives us the minimum rating after the first i contests, so what that means is that I can get my rating for the first i — 1 contests, g[i], and somehow compare this with a[i] to see what g[i + 1] is. If (a[i] > g[i]), we perform better on the ith contest than we should, g[i + 1] = g[i] + 1, thus g[i] = g[i + 1] — 1. However, I'm stuck because the casework for g[i] depends on g[i], which we don't have yet, so it seems impossible.

May someone tell me how to fix my logic?

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

    For $$$a_i > g_i$$$, since all $$$a$$$ and $$$g$$$ are integers, we have $$$a_i \ge g_i + 1 = g_{i+1}$$$.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Wait that's genius thanks. We can just add one the other side, to turn g[i] to g[i + 1].

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in D why we dont pop elements of s?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution to D is very well explained.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does "the minimum x equals # of L-s+# of R-s−# of adjacent LR-s" and what means adjacent LR-s. Is it like if we have L at number i and R and number i+1. Can somebody explain? Thanks in advance!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I did B, by first calculating what's the max amount of 0's and 1's string s can absorb such that it cant be modified further(using stack), then i just iterated the 2nd string, checking if 0 absorption count or 1 absorption count falls to 0, and then we break,the loop.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The dp used in this is called state machine dp https://jimmy-shen.medium.com/dp-state-machine-ae3177c93a03 .

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

(degi for every i)->(The graph is a forest). what's the meaning of this hint? I can't see any connection with the solution. In the solution, the author doesn’t make any vertex’s deg to be 1. Actually, he add degree.

»
11 days ago, # |
  Vote: I like it +38 Vote: I do not like it

This is a bit late, but I solved the problem I in $$$O(NM(N+M))$$$ time, so I'll explain it.

Let's consider the following problem.

You have a sequence $$$a=(a_1,\dots,a_n)$$$ and a fixed value $$$x$$$.
Perform $$$m$$$ operations to minimize the sum $$$\sum (a_i-x)^2$$$.

The model solution solves this in $$$O(nm)$$$ time using a greedy approach, but I did something different.

Let $$$f_i(j) = (a_i + (j+1) \times K - x)^2 - (a_i + j \times K - x)^2$$$.
This represents the cost of performing an operation on the "layer" $$$j$$$ of the element $$$i$$$.

In the original setting, when we perform an operation on layer $$$j$$$, we must have already performed an operation on layer $$$j-1$$$.
However, we can drop this constraint because $$$f_i(j)$$$ is increasing for each element $$$i$$$.

Therefore, for each layer $$$j$$$, we can calculate the value
$$$c_j[\text{cnt}] =$$$ "the minimum cost of applying $$$\text{cnt}$$$ operations on layer $$$j$$$," and then we can "merge" $$$c_1, c_2, \dots$$$ to get the answer.
Note that each $$$c_j$$$ is a convex sequence, so merging can be done in linear time.

To calculate $$$c_j[\text{cnt}]$$$ efficiently, we need to calculate $$$w[\text{cnt}][\text{len}]$$$, which is defined as follows:

  • Let's consider selecting $$$\text{cnt}$$$ disjoint segments such that the sum of the lengths of the segments is $$$\text{len}$$$.
    Then let $$$w[\text{cnt}][\text{len}]$$$ be the minimum sum of $$$a_i$$$'s in those ranges.

We can calculate all $$$w[\text{cnt}][\text{len}]$$$ in $$$O(NM \min(N, M))$$$ time.
By using the convex hull trick, we can calculate $$$c_j[\text{cnt}]$$$ from $$$w[\text{cnt}][\text{len}]$$$.

Now let's get back to the original problem.
We need to find the minimum of $$$\sum (a_i-x)^2$$$ for many $$$x$$$'s.
The key observation is that, if you have a cost sequence for some $$$x$$$, you can calculate the cost sequence for $$$x-K$$$ by adding just one layer.
Adding a layer takes $$$O(m)$$$ time, so calculating costs for all $$$x$$$ can be done in $$$O(NM^2)$$$ time.

The overall complexity is $$$O(NM(N+M))$$$ time.

293429392

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice explanation Orz. Thanks for sharing the amazing solution!

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C , while using Binary search technique , i am confused within this code section ,

auto check = [&](int k) {

		int curg = k;

		for (int i = n; i >= 1; i--) {

			if (pre[i - 1] >= curg) return true;

			if (a[i] < curg) curg++;

			else curg--;

		}

		return false;

	};

For a particular value k , if pre[i-1] >= curg does not hold true and then we move to the first if statement if(a[i] < curg) curg++ . Then will it be worth to check further back because prefix[n-2] will be holding maximum value for every prefix of that index . If at that point prefix value is not maximum then how can we sure that even after increasing curg++ in first if statement answer will exist . Should not we should break the loop in the first if statement . I am confused in the above scenario , please guide or if possible provide any testcase .