thanks for super fast editorial

Super Fast！！

there is also an O(n) solution for D.

we call the number of turn that a monster gets killed its colour.

we know that someone's colour is at most its degree +1.

if just maintain the two minimum colouring's and its colours for a subtree we can update our answer as follow:

we can fix the root colour from 1 to degre+1 and in each colourthe colouring for its children is the minimum colouring except the ones that its colour are same as the root. so their colouring is the second minimum one.

so we can solve it with a dp in O(n) time.

my code: 270694011

omg fast editorial :-)

I felt A >>> B in terms of difficulty

Possible proof for A: Think of number n as n '1's in a chain, connected with n-1 bonds. Each step could break a maximum of k-1 bonds. Hence the answer.

Before attempting E: Range Minimum Sum, try these standard and easy version of the problem.

Standard

• Minimum Sum
• Imbalanced Array

Easy Variations

• Left Terminal Minima
• Right Terminal Minima
• Max Rectangle Area in Histogram — Easy
• Max Reactangle Area in Histogram — Hard

Difficult Variations

• Modify the Array
• Array Collapse

In the past, I have also created a video on this topic.

Alternate for D : Note that a monster $$$v$$$ will die within $$$\leq deg[v]+1$$$ rounds. The problem could be formulated as follows , assign $$$t[v]$$$ (round number in which the monster gets killed) to each vertex $$$v$$$. Then you have to minimize the sum of $$$a[v].t[v]$$$ . For each vertex $$$v$$$ , we can keep a $$$deg[v] + 1$$$ sized vector , where each corresponds to the round number at which it was killed. Now using dfs and suffix / prefix minima , we can evaluate this value is $$$O(N).$$$

Can somebody explain what is being done in D. Or at least direct me to relevant resources.

can someone point out my mistake in c i did the same thing as editorial submission of c

These Python codes are really cute.

ty for fast editorial)

Whats the counterexample for solving D by making the tree into a bipartite graph, then removing the side of the graph with the greater attack amount?

Today first time i have solved 3rd problem

best contest, but in my opinion E is easier than D

I so almost solved D. Nice problems. Thanks for super fast editorial.

Can someone give me an example for problem D where $$$b_i$$$ is greater than $$$3$$$ for any node?

Is it true that the total rounds in D is $$$ \le 3$$$?

Why I can not solve a with brute force?

I have a different solution for B. Compress adjacent 0s into just one 0 (ex. 0010001 -> 0101). Note that replacing every substring with majority 0 is of the form 0 + 10 * k such that k is an integer, so removing these strings doesn't change the number of 0s and 1s. Thus, just check if there are more 1s in this compressed string than 0s. Here is my submission link. I'm surprised that the intended solution is casework.

A case for Bonus: Find a counterexample for $$$b_i≤18$$$ when $$$n=300000$$$.

Explanation: we delete all leaf nodes at a time. Then the tree becomes the largest subtree of the previous tree.

Problem B :(Make Majority) Video Editorial YOUTUBE VIDEO LINK (Make Majority) --Click Here

Another solution to B

First, all continuous $$$0$$$ can be transformed into one $$$0$$$ using one operation. Then we can consider the simpler form.

It's obvious that the pattern like $$$101$$$ can be reduced into $$$1$$$, so all $$$0$$$ except the first and the last character. so we can just compare the number of $$$1$$$'s and the number of longest continous $$$0$$$ segment.

what's the expected rating of D?

There's an $$$O(n\log n)$$$ solution to E without using the cartesian tree by calculating the contribution of each $$$a_i$$$

https://codeforces.com/contest/1988/submission/270728340

C Video Editorial

https://www.youtube.com/watch?v=-asiN-_tqb0

English

There is another solution for problem E. The point is to look at the contribution of each element in the permutation to the answers.

For each element we calculate the first and second element smalller than them to the left and to the right. This can be done in $$$O(n\cdot logn)$$$ using binary search and sparse table.

Then for each element we want to analyse the contribution of subarrays for which the current element is the minimum. We look at the segment of elements until the first smaller one to the right, let's say it has size $$$A$$$ (not including the element itself) and let's call the right one $$$B$$$. To everyone that is in the left segment, the number of subarrays for which the current element is the minimum is $$$A \cdot (B + 1)$$$ and for everyone in the right segment its $$$(A + 1) \cdot B$$$. For the first eleement smaller than the current element to the left, the number of subarrays is $$$(B + 1)\cdot ($$$ size of segment to the left including all elements up until the second element smaller than him $$$)$$$ . Same logic can be used to calcuate contribution of current element to the first ellement smaller to the right. For everyone else, that is everyone left of the first smaller element to the left and everyone right of the first smaller element to the right, the contribution is $$$(A + 1) \cdot (B + 1)$$$. Some edge-cases need to be handled for when there is no element smaller to the left or to the right however this is the gist. The contribution can be added up with lazy segment tree or even with prefix sums.

For details of implementation you can look at my code. code

blazingly fast editorial

In editorial of pD, "taking max part" should be "taking min part"

Did poor in this round, but really nice problems! The other side of getting bad result is finding unseen shortages for improvement :)

nvm

I think for A, a simple proof (or rather intuition) can be : Let's say you do not divide the element into (k-1) 1's and (n-k+1), and lets say you divide it into some number (possibly zero) number of 1's and a bunch of other numbers. Let the minimum number be p, then, to make p into 1 again (which is our goal), you'll need another operation in the future to convert it. Thus, you are needing more than 1 operation to convert a number into 1. Greedily, we should ideally use only 1 operation to convert a number (or part of it) into 1's. Thus, the ideal strategy becomes to convert the numbers into (k-1) 1's and (n-k+1)

The suggested method for B feels unnecessarily complex and invites mistakes by having multiple cases. Instead, another approach is to collapse each continous sequences of 0 into a singular 0, then compare if there's more 1s than 0s.

My (python) code: https://codeforces.com/contest/1988/submission/270651964

B was a really easy question

For B I thought of splitting string into "101"/ "110" / "011". What is wrong with this solution? 270743982

In D, I used recursive DP[n][20] but still TLE in test case 20. Can somebody explain why?

Solution: https://codeforces.com/contest/1988/submission/270724498

Another proof for # turns for pD: notice vertices not chosen in a round should connect to at least one chosen vertex, otherwise we can also choose it, then consider CC form by non-chosen vertices, every vertex in same CC would have different adjacent chosen vertices, then if there exist a (non-chosen)CC with size > n / 2, there also have > n / 2 chosen vertices, which means total nodes > n, which leads to a contradiction, so max size of CC form by non-chosen node would halve.

Then to construct the case where $$$O(\lg n)$$$ turns is needed, we can use the idea of above proof:

start with single node with weight $$$2^1$$$, call such tree $$$T_1$$$, then define $$$T_i$$$ ($$$i > 1$$$) as the tree by first use a node with weight $$$2^i$$$ to connect two $$$T_{i - 1}$$$, then for each node haven't connect to a node with weight $$$2^i$$$, create a node with weight $$$2^i$$$ and connect to it, then $$$T_i$$$ would have about $$$2^i$$$ nodes and require $$$i$$$ turns to eliminate.

Hi, how to compute $$$f(n,i,j)$$$ in $$$O(n^3)$$$ in F editorial? I was only able to come up with $$$O(n^4)$$$ or $$$O(n^3 log(n) )$$$ solutions for this subproblem.

In problem D, Why does the maximum B of a node is deg(x) + 1? I cannot find any comment to prove it.

First, thank for very good contest and fast editorial I am going to share my O(n) solution for D We can notice that in optimal solution, monster in node v can be kill in at mode |v| round (|v| is number of node have the same edge with D, round number from 0) So we can call dp[v][round]: minimum number of health decreases when kill monster in node v after "round" dp[v][round]= ∑_(u ∈chill of v) (min)⁡(dp[u][j]) (j ≠round) (sorry, i don't know how to write beautiful fomular)

we can use pref_min and suf_min to quickly calculate Node that we must update parent value from chill due to tle Here is my code 270747003

I see newbies solving C damn newbies these days are different breed,back when I was a newbie I couldn't even upsolve C by looking at editorial.But how does their submission looks alike?

can anybody write a more intuitive proof for problem D's max of logn sets ?

where you guys show the range of the output from 1 to n ? not 0 to n? (Problem C)

Or am i missing something?

Hi, I am finding it difficult to understand the solution provided to D. Can someone post a simple solution with an explanation or suggest updates in the existing editorial please?

For B I believe we can also "compress" any amount of '0' in a row into a single '0', then simply check if the number of '1's is greater than '0's in the resulting string: 270654643

For A, if we do in the reverse way, I think this is a problem like exchanging a new bottle by K bottle caps.

Like given [1, 1, 1, 1, 1, 1, ..., 1] containing n 1s, and we are going to combine at most K items once, and finally derive [n]. The process will be like [1, 1, 1, ..., 1] -> [1, 1, 1, 1, ..., K], containing N-K 1s and 1 K. Our target is to combine all numbers into 1 number, so the real number in the array doesn't matter at all, that it, there remains N-K+1 items to combine.

The maximum number of bottles that can be exchanged is floor((N-1)/(K-1)).

I think this is a classis problem, so you may find video explanations online. I elaborate one here: First give 1 bottle cap to your friend, and every time you exchange K-1 bottle caps with your friend's one, and give the exchanged bottle (cap) back to your friend. You can do this (N-1)/(K-1) times and you will finally exchange floor((N-1)/(K-1)) bottle caps and have remaining (N-1) % (K-1) bottle caps + 1 from your friend.

The difference between A and bottle exchange problem is that if (N-1) % (K-1) + 1 > 1, then you should do the final combine, so the answer is `ceil((N-1)/(K-1)) in this problem.

Problem D got accepted in exacly 3 sec

[submission:https://codeforces.com/contest/1988/problem/D]

Pretty surprise to see cartesian tree in $$$E$$$. Maybe it is the first time I see it in CF as well.

A felt hard. Came up with DP approach for A during the contest . Normal method was just not striking me.

#include<bits/stdc++.h>
using namespace std;
#define int int64_t 
int dp[1001];
int solve(int n,int k){
	if(n==1) return 0;
	if(n<=k) return 1;
	if(dp[n]!=-1) return dp[n];
	if(n >= k*k){
		int ret = 1;
		vector<int> x(k,k);
		n -= k*k;
		x[0] += n;
		for(int i=0;i<k;i++){
			ret += solve(x[i],k);
		}
		return dp[n] = ret;
	}
	vector<int> x(k,1);
	n -= k;
	int i=0 ;
	while(n){
		if(n>=k-1){
			x[i] = k;
			i++;
			n -= (k-1);
		}else{
			x[i] += n;
			break;
		}
	}
	i = 0;
	int ret = 1;
	for(;i<k;i++){
		ret += solve(x[i],k);
	}
	return dp[n] = ret;
}
void runcase(){
	int n,k;
	cin>>n>>k;
	memset(dp,-1,sizeof(dp));
	cout<<solve(n,k)<<endl;

}
int32_t main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen("cp.in", "r")) {
        freopen("cp.in", "r", stdin);
        freopen("cp.out", "w", stdout);
    }
	int t;
	cin>>t;
	while(t--) runcase();
}

Hello! Does my solution of D get RE because of dfs? 270748754

If yes, is there are way to bypass it nicely?

Shouldn't the edi also contain the dp states and transitions atleast instead of just mentioning that you can solve it by dp? (for D)

Another idea for B is that it is only possible iff the number of "0-streaks" is less than the number of ones.

Please someone explain the bi<=19 part of the editorial in more detail.

In fact, problem D has a $$$O(n)$$$ way

Considering that we actually only transfer from the smallest and subsmallest points of each subtree when we transfer, in fact, there are only $$$O(deg)$$$ effective transfer points of a tree point, that is, only the number of selection rounds corresponding to the minimum value of each point, and their mex and mex+1, taking into account this, we only need to maintain the smallest and subsmallest points of each point to implement the $$$O(n)$$$ algorithm.

It comes with an implementation that uses map, which is just for convenience and can be replaced with another $$$O(1)$$$ structure

https://codeforces.com/contest/1988/submission/270751383

Could someone provide an explanation of the DP used for Problem D?

Thanks!

Why does this code in java 270744757 tle but gives ac in c++ 270751728 :( Edit: I see that the c++ code also barely passes maybe i can do better with the transitions

In fact, problem D has a $$$O(n)$$$ way

Considering that we actually only transfer from the smallest and subsmallest points of each subtree when we transfer, in fact, there are only $$$O(deg)$$$ effective transfer points of a tree point, that is, only the number of selection rounds corresponding to the minimum value of each point, and their mex and mex+1, taking into account this, we only need to maintain the smallest and subsmallest points of each point to implement the $$$O(n)$$$ algorithm.

It comes with an implementation that uses map, which is just for convenience and can be replaced with another $$$O(1)$$$ structure

https://codeforces.com/contest/1988/submission/270751383

I enjoyed today's problems. Thanks to the setters.

nice

This codechef problem is harder version of B.

I believe my solution for problem E is also O(n), but doesn't require Cartesian tree. It is quite unpleasant to implement and debug though, I couldn't do so during the contest time.

thanks for editorial <3

What's wrong with this idea for D?

There are at most $$$O(\log n)$$$ rounds, so for round $$$j$$$, find the maximum weighted independent set, let it be $$$c_j$$$, then set the values of $$$a_{v_i}$$$ to 0 for each $$$v_i$$$ in the max ind set, and keep doing that until we get all zeroes in a. For round $$$j$$$, add $$$j \cdot c_j$$$ to the answer.

After all rounds, output answer. This fails on test 3 :|

How does the induction go in the proof of B?

Problem E can be done by looking at the contribution of each values. If an index is removed then the affected contribution will the - - The contribution from the index itself. This we can find by calculating the left and right index smaller than the value at index. - The contribution coming from the other index that uses this index in their contribution. Here the observation this value will only change if we change the value between the left and right minimum of this index. If we remove left and right, then we have to consider second minimum left and second minimum right respectively and add it accordingly. All the value that is between left and right will only reduce the contribution by 1.

For problem D, am I the only one who decided to use sqrt(n) instead of log2(n) as the bound for b (for safety because I couldn't prove it in contest), only to find out that there's exactly one singular case where sqrt(n) < log2(n)? QAQ

This is my approach for problem A, can you tell me what is the flaw in the argument? the picture link is the following, i don't know why it is not uploading: https://photos.app.goo.gl/VLXqFcDU2QHGFHap7

I came up with DP on subtrees solution for D right after the contest but it got WA on 3rd test. It maintains dp[2][i], the maximum sum of monster points on subtree i we can get in the current round if we skip/kill the root node of that subtree. Can somebody help me understand why that failed?

270745002

not come up with '0110110' and got an WA on B :(

$$$O(n)$$$ solution in problem E without cartesian tree (although it's long to explain what I'm actually doing): 270758048.

Edit: I miswrote the prev_greater and next_greater, it must be prev_smaller and next_smaller

Can someone explain why I have to cast here?

I made a function that converts a binary string to decimal but it breaks at higher numbers. Specifically this statement:

num += (Long.parseLong(binary.substring(i-1, i)) * Math.pow(2,binary.length()-i));

However when casting to long this statement works as intended.

num += (long) (Long.parseLong(binary.substring(i-1, i)) * Math.pow(2,binary.length()-i));

Here is the working submission: 270754810

I don't get this line in A proof

and the aforementioned sequence of operation achieves the maximum increment.

I think you can actually get the same increment with doing another type of operation in some cases
like for example 
n=200 and k= 5
we can make it 
37 37 37 37 52 

I solved E in $$$O(n log(n))$$$

void upd(int i, int val) {
  for(; i<bit.size(); i+=i&-i) {
    if(val >= bit[i][0]) {
      bit[i][1] = bit[i][0];
      bit[i][0] = val;
    } else {
      bit[i][1] = max(bit[i][1], val);
    }
  }

}

pair<int, int> que(int i) {
  pair<int, int> res(-1, -1);
  for(; i>0; i-=i&-i) {
    if(bit[i][0] >= res.ff) {
      res.ss = res.ff;
      res.ff = bit[i][0];
      res.ss = max(res.ss, bit[i][1]);
    } else {
      res.ss = max(res.ss, bit[i][0]);
    }
  }

  return res;
}

for(int i=0; i<n; i++) {
    tie(l1[i], l2[i]) = query(a[i]);
    update(a[i], i);
}

My Solution

I am unable to understand the reason for getting the following error in my code for Problem C 1988C][SUBMISSION:270720573 - Increasing Sequence with Fixed OR

wrong answer Integer parameter [name=a[35]] equals to 1000000000000000000, violates the range [1, 999999999999999999] (test case 102)

The question specifies 1<= n <= 10^18, and that a(i) <= n

Here is my code:- ~~~~~

include <bits/stdc++.h>

using namespace std;

int main() { int t; cin >> t; while(t--) { long long n, n2; cin >> n; n2 = n;

vector<long long> a;
    vector<int> pos;

    int size = 0;
    while(n2>0) {
        if(n2 & 1 == 1) pos.push_back(size);
        n2 = n2 >> 1;
        size++; 
    }

    a.push_back(n);
    for(int i=0; i<pos.size(); i++) {
        long long x = n;
        x = n - pow(2, pos[i]);
        if(x!=0) a.push_back(x);
    }

    cout << a.size() << endl;
    for(int i=a.size()-1; i>=0; i--) cout << a[i] << " ";
    cout << endl;                
}

} ~~~~~

The logic used here simply keep track of the places where the binary digit is 1 starting from position 0 at the right hand side (least significant bit).

Then I simply place 0 one by one in the in the positions where one are placed. For example: n = 1111, then

1111 1110 1101 1011 0111

Just shifting the 0 from right to left across all the positions that have 1, and keeping the position with zeroes as same.

If I have a n = 11100111, then

11100111 11100110 (0 placed at 0th pos from right) 11100101 (0 placed at 1st pos from right) 11100011 (2nd pos) 11000111 (5th pos) 10100111 (6th pos) 01100111 (7th pos)

I create the number with 0 in 6th pos by doing n — pow(2, 6) Which produces the same effect as placing 0 in the sixth position.

Please help me understand the flaw in my logic/code which is causing this unexpected error.

Missed B by just 1 more condition -_-