super speedy editorial, BucketPotato orzzzzzz

Nice ProblemSet :)

Fast editorial.. Why D2 has an unusual memory limit?

I enjoyed the round! In particular, want to share a sol for E that involves kruskal tree (reachability tree/line tree). So lets say for each $$$i$$$, you gave the $$$i$$$'th edge wegiht $$$i$$$. Then you can find the MST (min spanning tree) of the graph. Define $$$f(u, v)$$$ as the maximum value of any weight on the path from $$$u$$$ to $$$v$$$ on the MST. The answer will end up being the max value of $$$f(u, v)$$$ for all $$$u, v \in [l, r]$$$.

When it comes to reachability/max path weight on an MST, we can use a kruskal tree. In particular, the answer will be the weight of $$$lca(l, l+1, l+2 ... r)$$$ on the kruskal tree. A cool property of lca is that $$$lca(lca(u, v), w) = lca(u, lca(v, w))$$$. So this means we can build a segment tree over all the nodes. Some node on the segtree stores the lca of all the nodes $$$[l ... r]$$$ in the kruskal tree. The merge function in this segtree will be finding the lca.

The final complexity is $$$O(n \log n + q \log^2 n)$$$ since you have to call lca $$$\log n$$$ times per query.

Good contest. The difficulty of Problem A is very appropriate, and Problem B and C are very interesting. D1 and D2 are also good. Thank you.

My submission for B that doesn't use DP: 164767537.

For D2, https://codeforces.net/contest/1706/submission/164790931 logically maintains only n elements in the 'hold' vector, yet MLE's. Any clue if this is because CF counts total memory allocated throughout the execution of the program, or am I actually using more space than I think?

c in the even case just checked left and right leaning cool building's should have checked all possibilities.. this is the closest i've ever been to solving div 2 C. hope i'll solve c in next div2 rounds

Posting a comment to edit it when problem ratings arrive, so I can say how right/wrong I was

Edit: So yeah, you know how they say:"Humans are very bad when it comes to predicting something". Well, I can confirm that I am, indeed, a human!

Great contest though!

.

I haven't seen the $$$t\le 100$$$ constraint in D2, so I only count the $$$a_i$$$/x or ($$$a_i$$$/x)+1 place, let the complexity be strictly $$$O(\sum \sqrt a)$$$.

Please someone explain C

a very beginner question: what does parity mean??? from problem B

Is there a proof that the maximium value X such that A//X >= B is A//B ?

For the minimim X such that A//X <= B it is not working.

Alternative solution to E without much thinking, do parallel binary search, to check if everything between l and r is connected, get rightmost node to l where everything between is connected and check if it's >= r

Don't understand solution of D1,can someone explain it to me in detail

Solution 2 in D2 by AlperenT doesn't open.

B is really harder than C and D1

How to do C using DP?

E is cool, could not figure out that connecting $$$i^{th}$$$ vertex to $$$(i+1)^{th}$$$ vertex is the key, the editorial is really smart.

Video Solution for Problem C. Will upload Problem D in the morning :)

I think there is a slight mistake in the alternative solution for D: "Continuing this logic, for all integers u=1,2,…,k, we should check the elements a_i satisfying (u−1)⋅v+1≤a_i≤u⋅v, and set all these p_i=u."

It seems the condition should be (u-1)(v+1)<=a_i<u(v+1). For example, if we take a_i=2v+1 then p_i=2. Or if we take a_i=3v+2 then p_i=3

Here is my solution to D2: First initialize $$$p_i = 1$$$ \forall i$ the greedy action is always to reduce the actual maximum $$$c_i = \lfloor {\frac{a_i}{p_i}} \rfloor$$$ because we can only increment $$$p_i$$$ ($$$p_i > 0$$$) and reducing the actual minimum will make the differcence increment, so the idea is in a priority_queue add all the pairs $$$(c_i, i)$$$ in each iteration get the maximum value, reduce it with an increment of $$$p_i$$$ by $$$x$$$ such that $$$\lfloor {\frac{a_i}{p_i + x}} \rfloor < \lfloor {\frac{a_i}{p_i}} \rfloor$$$ (p_i += x), we can get $$$x$$$ with $$$x = (a_i - c_i * p_i) / c_i + 1$$$ (for each $$$a_i$$$ there are at most $$$\sqrt {a_i}$$$ updates of $$$p_i$$$). Next update the answer if the differcence of the maximum and minimum value is smaller than before until a $$$p_i > k$$$ or maximum value of $$$\lfloor {\frac{a_i}{p_i}} \rfloor$$$ is $$$0$$$. To optimze the solution i used an vector to replace de priority_queue and save the indices, because all values are in range $$$[0, 10^5]$$$ so no sorting is needed, to update a maximum with value $$$c_i$$$ (position $$$c_i$$$ in the vector), update $$$p_i$$$ and get the new $$$c_i'$$$ and move the index to position $$$c_i'$$$, 164794465

164793050 D1 solution with bitsets using for indices storing. Works due to low count of divisors

Thank you for the contest the problem was clear and fun and this editorial is so easy to read thanks alot

Hey everyone,

I'm wondering about the solution to D2. I read AlperenT's solution because his strategy of fixing the maximum value is similar to what I did for D1. There are a few things I don't understand. Also just to preface this, I'm probably going to misquote the author at almost every point in this post, that is not intentional it is just a consequence of my foolishness.

First, in the fourth paragraph, he says that we need to find the best Pi for some maximum v by iterating through all possible values of k. Doesn't this immediately trigger a TLE, because in the worst case we need to iterate through all k for all n --> n^2?

Second, AlpertenT says that the minimum value for our fixed maximum will come from the smallest Ai. But this can be disproved with a simple example: 6, 10 with a maximum of 6. To get 10 under the maximum, we must divide by 2, leaving us with 5, 6 --> 6 is not the maximum. The author says that this is only true for samples with the same "u", which does make sense, but at that point, aren't you just iterating through all values in the array regardless, since you need to check for the minimum of every value at every "u"?

At this point, I think I'm lost to the extent that I can't ask any more intelligent questions, but I guess the final things I'm wondering about is how we generate the "next" array in less than n^2 time, and how that will help us for a fixed maximum rather than a fixed minimum.

Thank you so much for reading, this is a long comment.

An alternative solution to E without using LCA and minimum spanning tree.

The idea is to keep a persistent DSU data structure to be able to query whether 2 nodes are connected at any point (after adding some edges from the beginning).

Then for every $$$i$$$ and $$$i+1$$$ nodes. We do a binary search to find the first time the 2 nodes become connected. Then we can continue in the same way using a range max query structure.

To construct a persistent DSU data structure we need to keep snapshots for updates for every change for node’s parent. Also, we need to do small into large merges instead of path compression to get the required complexity.

The overall complexity for the first part is $$$O( \thinspace n \thinspace log(m) \thinspace log(log(n)) \thinspace )$$$

submission

I solved E by keeping track of all the intervals formed after connecting $$$k$$$ edges, using DSU.

In DSU, similar to parent/size, we store the ranges covered by each set in the form of a set of $$$[l, r]$$$ pairs. Anytime two intervals are merged, our goal is to recalculate the $$$[l, r]$$$ ranges in the larger set, after having added the elements of the smaller set to it. Whenever a new range is formed, we note the time when it was formed. This will give us all the possible ranges of the form $$$[l, r, k]$$$, which means that it is possible to connect all vertices within $$$[l, r]$$$ using the first $$$k$$$ edges.

See my DSU class for more clarity : 164821167

Now the problem reduces to this: We have a bunch of ranges of the form $$$[l, r, k]$$$, and queries of the form $$$[x, y]$$$. For each query, we have to find the range with minimal $$$k$$$ such that $$$l <= x$$$ and $$$r >= y$$$. This can be solved by using a segment tree for the minimum. Sort the ranges and queries by their left ends. Try to minimize $$$k$$$ for each right end of a range. For a query, find the minimum $$$k$$$ for all $$$r$$$ such that $$$y <= r <= n$$$.

Time complexity : $$$O(N Log^{2}N)$$$ for merging sets using DSU.

I liked the problems a lot, though B seems a bit hard for a Div2 B problem..

Thank you now I finally know how to keep std::vector's memory

I love problem E. Thank you for the contest

Nice contest, finally became expert :)

for me, B is really tough at the first glance, but sample figures are really inspiring

in D1 tutorial, you directly enumerate min value from 0 to a[0], does this mean we can always obtain all numbers smaller than a[0] using that operation on array?(at least [1, a[0]]?) . looking forward to some formally prove, im not good at number theory. thanks

also, E looks really great, maybe will become another standard graph problem.

great contest!

This set of problems is very good, harvest a lot

I don't really understand the Solution D1.

It's said that we iterate v as the minimum value, but what if it can't derived from the array p and the array a?

All problems in this contest are very nice!

Why isn't there anyone to point out the nearly same problem as Problem C on Atcoder ? Actually it's ABC162F. Select Half , and to make an equivalent transformation you just have to define the "a[i]" of the i'th building as the minimal cost of making it higher than both of its neighbors.

Sorry for my poor English.

Can anyone explain the problem no. D1 because I am not getting from tutorial

他奶奶的全他娘的是外国佬？？

Bad E, it is too common so that people who know kruskal reconstruction tree can pass it very fast but it is very diffcult to people who don't know this algorithm like me :(

164856513 164742302

ST table can also be used to pass E.My solution is $$$O(n\log^2n)$$$.

Can someone explain solution 1 of problem D2 in details please?

The way using dsu to find the maximum weight in problem E was new to me.

Here is how i understand it (I'll be so glad if anybody fix it if I get anything wrong).

1.) The function weight doesn't find the lca in the actually graph, it finds the maximum weights.

2.) The function doesn't itterate all the edge between u and v.

3.) The reason it can be sure that the weight we found will be the maximum is follow:

• The order of merging must be from smaller weight to large weight.
• If weight(u, v) = k then before the k-th edge being added to the dsu, u and v will be at two different subtree, so to be connected, it must pass the k-th edge.

Apply all of this, we can find the maximum weight on the path between u and v without actually using the lca of two vertices.

In my solution for E, I used DSU with small to big merging to calculate $$$f(i)$$$, everytime while inserting the elements of the smaller set (say $$$x$$$), I checked if the larger set has $$$x+1$$$ or $$$x-1$$$ in it, and if it does then I updated the value of $$$f(x)$$$ or $$$f(x-1)$$$.
It was a pretty small implementation
My submission

Very neat solutions BucketPotato

I saw the first sample code for D2 and I wanted to show how to iterate the distinct values of $$$\lfloor{\frac{a}{b}}\rfloor$$$. I'll leave it here if anyone is interested.

Let $$$\lfloor{\frac{a}{b}}\rfloor = q$$$. We want to find $$$b'$$$ such that $$$\lfloor{\frac{a}{b'}}\rfloor < q$$$. Then $$$\frac{a}{b'} < q \Rightarrow b' > \frac{a}{q} \Rightarrow b' > \lfloor{\frac{a}{q}}\rfloor \Rightarrow b' \ge \lfloor{\frac{a}{\lfloor{\frac{a}{b}}\rfloor}}\rfloor + 1$$$, which is the formula you can see in the loop in the sample code.

I think I have seen this in some Codeforces blog but I couldn't find it. I'm not good at this floor/ceil stuff so if anyone has related blogs/links, they are welcome.

Hey, can anyone please help me clear doubt in the editorial of Problem D1? It says that we can consider that the minimum can have a range of anything from (0....a[0]). But what if let say a[0] was 4, but constructing 3 was not possible by dividing any of the ai's with any value of p (and we might get the minimum difference when assuming the minimum value to be 3).

For example, Let A = [4, 4, 8, 16] and K = 2

Here we will also consider 3 as the minimum value when iterating from 0 to 4, but constructing 3 as a minimum value is not possible. We can also state that there might be an array for which having 3 as the minimum value is not possible but having 3 gives us the minimum difference

Thanks!

In tutorial for D2, Solution 2 (AlperenT) "Continuing this logic, for all integers u=1,2,…,k, we should check the elements ai satisfying (u−1)⋅v+1≤ai≤u⋅v, and set all these pi=u."

I think the range should be (u−1)⋅v+u-1≤ai≤u⋅v+u-1

With reference to the tutorial of D1, is it not possible to not achieve a particular value of the minimum value v at all?

Let's take this example,

1
3 5
7 7 14 

if we assume v = 5 then , 
Array p will be 1 1 2 , and Array a/p = 7 7 7 ( note that the value 5 is not achieved here)
max a/p will be 7
cost according to the tutorial = max (a/p) - v = 7 - 5 = 2 , but the answer for the case of v=5 should be 0.  

Am I missing something?

Can you explain to me . Why did my code get WA https://codeforces.net/contest/1706/submission/164908500

I have used linear Dp in 'C' for n==2. I don't know why it's giving wrong ans . Any assistance will be most welcomed.

#include <bits/stdc++.h>
using namespace std;

#define IOS    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define I =in()
#define S =sin()
#define C =chin()
#define rep(i,a,b)      for(int i=a;i<b;i++)
#define vfill(arr)       for(auto &x:arr)cin>>x;
#define all(x)          begin(x), end(x)
#define vi              vector<int>
inline int in(){int x;cin >> x;return x;}inline string sin(){string x;cin >> x;return x;}inline char chin(){char x;cin >> x;return x;}inline int In(){int x;cin >> x;return x;}

//Code begins here ----------
int dp[100001][2];
vi arr;
int check(int i,int num){
    if(i <= 0)return 0;
    if(dp[i][num]!=-1)return dp[i][num];
    int m = max(arr[i+1],arr[i-1]);
    int y = INT_MAX;
    int x = (arr[i]>m?0:m-arr[i]+1)+check(i-2,num);
    if(num == 0 )
        y=check1(i-1,num+1);
    return dp[i][num]=min(x,y);

}
void solve(){
    int n I;
    memset(dp,-1,sizeof(dp));
    arr.resize(n);vfill(arr);
    if(n%2==0){
        int x = check(n-2,0);
        cout<<x<<endl;
    }else{
        int sum = 0;
        for(int i=1;i<n;i+=2){
            if(arr[i]>arr[i-1]&&arr[i]>arr[i+1])continue;
            else{
                int m = max(arr[i+1],arr[i-1]);
                sum+= m-arr[i]+1;
            }
        }
        cout<<sum<<endl;
    }
}
// =======================================================================================================
signed main(){
    IOS;
    // int t =1 ;
    int t;cin>>t;
    while (t--){solve();}return 0;
}
// =======================================================================================================

Can someone explain D2 in the most childish way possible?

great contest

Solution of problem D1 using sets and lower_bound: 165982319

Could anyone help me explain why that the number of distinct $$$\lfloor\frac{a}{q}\rfloor$$$ is at most $$$O(\sqrt{a})$$$ ?

UPD: this idea gets AC

I wonder if my idea for problem E is wrong. I'm getting the wrong answer, however I might have a bug somewhere. So to the idea:

1. Let's have a DSU and unite set u_i and v_i processing edge i. We process the edges 1 to m. The dsu-node struct stores continuous ranges currently present in the set. Uniting the sets we rebuild some of those ranges if they get merged. E.g. merging set with ranges {(1...2), (4...4)} and set with {(3...3), (6...6)} results in set with ranges {(1...4), (6...6)}. Then we know what ranges are subjects to change at each merge. For the example above the merge yields new range (1...4) which is fully "walkable" (i.e. the answer for query l=1, r=4 is the edge i we used to unite the above sets).

2. Now on the queries. While performing the DSU-unite steps let's store new "walkable" ranges e.g. i-th edge yields (l...r) range so we store it like {(l...r), i}. Initially we have {(v...v), 0} for each v in the graph. Next let's sort the ranges we have after all edges processed through the dsu. It may look like {(1...1), 0}, {(1...3), 3},..., {(2...3), 2} ... . Suppose we have a query (l, r) now. The answer to that will be the the element whose left range-bound is less or equal to l and whose right range-bound is greater or equal. We can find smallest range that contains (l...r), the second value we store would be the answer. Note the way we construct the ranges: there are no intersecting ranges: the only possible case is one range contains the other. More formally there is no ranges {(<>...i), <>} and {(j...<>), <>} so that i > j.

To answer all queries offline we can sort them so that first come the ones with smaller l and then iterate the queries preserving a set of not-yet-closed ranges with their second values. The answer to current query (l_i, r_i) would be lower_bound({r_i, 0}) on that set.

May anyone tell if the logic is broken at some point?

As usual, would like to provide a shitty and overcomplicated solution for E.

Let's use persistent segment tree to keep track of updates — at the start we say that at position i (0 <= i < N), there stands number i + 1 (so we store the information about all components directly in the segment tree). Now, let's handle queries one by one — we use small-to-large merging to update the new parent for each vertex from the component with less size. As such, we will have to update O(NlogN) in worst case, making the total to O(Nlog^2N + M). To answer a query, run binary search. A segment is filled if and only if its maximum is equal to its minimum. A query is answered in O(logN), + logN from binary search -> the query answer time is O(Qlog^2N)

So the total complexity isO(Nlog^2N) space and O((N + Q)log^2N + M) time, and I believe that with enough pain that is squeezable into TL.

Why the problem name of D is "Chopping Carrots"???

$$$O(N\log{N})$$$ solution for problem E using two segment trees and DSU: Link

Note to self: Write explanation later.