How Can I read Such a big editorial for B. havoc editorial to read...

In the B problem, I think we just need to compare a + a with b + c

Solution for B looks like some neural network ;)

Contest has become mathforces with B

All comments are related to B :D

Is there any easier understanding of problem B?

can anyone write the bruteforce solution for problem A.

B looks so hard in the editorial:)

I would like to understand D. Why we use bit mask of size k?

What does it mean if "we can find free bit and create match to this segment" to create the dp?

Can someone please help me find error in my logic with question B.

my submission

For minimum case, I started making pairs such that their score is one greater than our score. Then after that, some scores in first contest remain which are greater than a, and some in second contest which are greater than b. we take min of these to give additional people with score greater than us.

sg1 = min(n-1-x, y-1)

sg2 = min(n-y-1, x-1)

og = min(n-x-sg1, n-y-sg2)

mn = n - sg1 -sg2 - og

Similarly I do for max, but for this case, we search for equal score. After that we search for scores less than a in first contest, and scores less than b in second contest. We add min of these to give additional people that may come at or before us in position.

gr1 = min(n-x, y-1)

gr2 = min(n-y, x-1)

ol = min(x-1-gr2, y-1-gr1)

mx = gr1+gr2+ol+1

Problem B

// worst rank
part1 = min(x-1,n-y)
part2 = min(y-1,n-x)
w = part1 + part2 + min(x-1-part1,y-1-part2)

worst = 1 + w

// best rank
part1=min(y-1,n-x-1)
part2=min(x-1,n-y-1)
part1=max(part1,0)
part2=max(part2,0)

best = N — (part1 + part2 + min(n-x-part1,n-y-part2)

Problem B. I forgot about the borders and place max(1,min(n,x+y-n+1)) wrote max(1,x+y-n+1). and finally I didn't solve the problem during the time of the Contest

Why cant I view other people's code ? :/

What is the approach of finding "nearest" numbers to the right and to the left that are smaller than the current one?

How to search the "nearest" in c2 (second solution)?

Problem C. in editorial(second solution). please help. can you this code O(n*n) optimize to O(n log n) or O(n). I could not find j faster.

for (int i = 1; i <= n; i++) {
  int j = 0;
  for (int k = 1; k < i; k++) {
    if (m[k] <= m[i]) {
      j = k;
    }
  }
  l[i] = l[j] + (i - j) * m[i];
}

What if in C2 we have more than one min element??

Please explain solution of problem 'D' in detail

I am getting Runtime error "Exit code is -1073741571" on problem C2 with C++14

71730114

while the same code is ACCEPTED with C++17

71727975

What could be causing the difference?

In the recursive approach for C2 how to make choice after finding minimum i.e, if we have to recurse on the right or left part?

deleted

Thanks for the tutorial <3

what stand between me and the rating add,is the math

I wrote a segment tree & divide and conquer solution for C2, based on the first idea in this tutorial of problem C2. But I get TLE here: https://mirror.codeforces.com/contest/1313/submission/71738916. I tried many times at my local machine, using a variant to count the time complex and found the divide and conquer procedure is O(N), and my segment tree is O(17) = O(logN).

So I used ST table to reduce complex from O(N logN) to O(N) here: https://mirror.codeforces.com/contest/1313/submission/71741474, get Accepted.

.

Can anyone just explain D more clearly ? I'm too stupid to understand the given editorial.

How to solve the problem C2 recursively in first solution,isn't it got a comlexity 2^n?

Help needed in problem c2.

My approach: for selecting the pick index I calculated the following for each index.

sum=dpl[i]+dpr[i]-a[i] here dpl[i] is sum from 1..i making non decreasing segment and dpr[i] is same from n..i

for which index I get the maximum sum I selected that index to be the peak index. And then just calculated the final result.

Can someone please tell me why this is wrong or any test case? my code: 71701033

In (B) some proofs may become much more symmetrical if you notice that you can make the substitutions

• $$$x\leq y$$$
• Change $$$x,y$$$ so that (case 1) $$$x=y$$$, or (case 2) $$$x+1=y$$$.

Also an observation is that you don't have to solve a completely new problem for the minimum after solving the maximum problem; specifically if $$$x+y = c$$$, then the worst possible for $$$x,y$$$ corresponds to the best possible for some imaginary opponent with $$$x'+y' = c+1$$$; one just needs to subtract the number of "ties" in the $$$x',y'$$$ case, and add in a $$$+1$$$ because $$$x,y$$$ beats itself.

(https://mirror.codeforces.com/contest/1313/submission/71990013)

In C2 editorial second soln, what's an optimal way to find "nearest" numbers to the right and to the left that are smaller than the current one.

Can anyone help me with problem Skyscrapers (Hard Version), I am getting memory limit exceeded for my solution I used Sparse Table for finding range minimum query and did a recursive method My submission

I struggled a lot with problem C / C2 (skyscrapers). Some comments said to use a monotone stack, which was a big hint, however I have only done a few problems with this approach and I didn't know what the stack actually represents. Finally I came up with it:

For now we'll focus our attention on nondecreasing skylines. For every index $$$i$$$, we will identify the optimal skyline from index $$$1$$$ to $$$i$$$ inclusive. For $$$i=1$$$, clearly we use $$$a_1=m_1$$$. More generally, for $$$i=1$$$ to $$$n$$$, we push $$$i$$$ onto the stack $$$s$$$ after popping all elements $$$j$$$ such that $$$m[j]>m[i]$$$. Finally we push $$$i$$$. The stack right now describes the optimal skyline ending at $$$i$$$; Specifically, if $$$s$$$ contains $$$i=i_k > i_{k-1} > \cdots > i_1$$$, then we make assignments as follows: indices $$$(i_{k-1},i_k]$$$ get height $$$m[i_k]$$$, indices $$$(i_{k-2},i_{k-1}]$$$ get height $$$m[i_{k-1}]$$$, $$$\ldots$$$, and indices $$$(0,i_1]$$$ get height $$$m[i_1]$$$. It is a little exercise to see that this is a valid assignment and optimal.

Let's call $$$maxIncreasingSkyline[i]$$$ the sum of the heights of this optimal skyline. It can be computed in amortized $$$O(1)$$$ at each step while doing the popping/pushing.

One can do the same procedure for nonincreasing skylines, by iterating from $$$n$$$ to $$$1$$$, and similarly obtain $$$maxDecreasingSkyline[i]$$$, which represents the optimal skyline that "begins" at index $$$n$$$ and ends at $$$i$$$.

Now the actual optimal skyline will be one of 3 possibilities: a nondecreasing skyline (whose value is $$$maxIncreasingSkyline[n]$$$), a nonincreasing skyline (whose value is $$$maxDecreasingSkyline[1]$$$), or a combination of the two, in other words, there is some $$$j$$$ such that $$$maxIncreasingSkyline[j]+maxDecreasingSkyline[j+1]$$$ is maximal. The latter can be computed in $$$O(n)$$$ time since we have already prepared the two arrays. Then one does another linear scan to reconstruct the assignments $$$a[\cdot]$$$ from the stack.

My submission is here but hopefully the explanation above is adequate.

Hardest Div2B ever. Were past Div2B's always this hard? :(

In problem C2, what is the neatest way to implement the recursive approach? Recursive approach is prone to exceed the default stack size limit.

Are there any restrictions for i = 1 and i = n? see 79077157 for more details. Please someone tell me where my code is not correct. Thanks in advance.

Solution for C2 using the divide and conquer approach: 85811938

EDITORIAL OF C2

OBJECTIVE: Find the Optimal Peak by both Methods:

Method 1: Create a Segment Tree which returns the index of the smallest element in [l,r].

Now , we search for the smallest element in [l,r]. Suppose it is at minindex. Then we make 2 recusrive calls,

-> First we assume that all a[l....minindex] have been changed to a[minindex] , so we have a value of a[minindex]*(minindex-l+1) . Then we make the recursive call on [minindex+1,r].

-> Second is when we change all a[minindex+1....r] to a[minindex]. Then we have a value of a[minindex]*(r-minindex +1 ). Then we make a Recursive call on [l,minindex-1].

In our base case, (l==r) , we have the value i.e. final sum of the array if l(or r) were the Peak. We simply find the Optimal Peak, i.e. the one with max. value. (Have a look at the code, I have made 2 special checks in case [l>r].See just below the recursive calls)

Once we have the optimal Peak, we can easily calculate the Array.

Method 1 Code

Method 2: This Method is nicely explained in the editorial. I referred to this to make 2 arrays pre and suf to find the smallest element on the left and right of a[i] with overall O(n).

Then I calculate value for each a[i] in left[] and right[] as per described Method in Editorial and found out the Optimal Peak. Then answer can again be calculated easily.

Method 2 Code

Can anyone help me in C1 . I m getting wrong answer at test case 9 . I m using divide and conquer technique .Provide me some test cases or check my soln . 1313C1 - Skyscrapers (easy version)

include<bits/stdc++.h>

using namespace std;

define ll long long

define pb push_back

int main() { ll n,i,j,k,l; cin>>n; ll a[n+1]; for(i=1;i<=n;i++){ cin>>a[i]; }

i=1;j=n; while(i<=j){

ll mi=1000000003;
  ll pos=-1;
  for(l=i;l<=j;l++){
      if(a[l]<mi){
          mi=a[l];
          pos=l;
      }
  }
  if(pos==i){
      i++;
      continue;
  }else if(pos==j){
      j--;
      continue;
  }else{
      ll a1=0,a2=0; 
      for(k=pos+1;k<=j;k++){
        if(a[k]>a[pos]){
            a2+=a[k]-a[pos];
        }
      }

      for(k=pos-1;k>=i;k--){
         if(a[k]>a[pos]){
            a1+=a[k]-a[pos];
         } 
      }

      if(a1<=a2){
         for(k=pos-1;k>=i;k--){
                a[k]=a[pos];
          }
          i=pos+1;
      }else if(a2<a1){
          for(k=pos+1;k<=j;k++){
              a[k]=a[pos];
          }
          j=pos-1;
      }
  }

}

for(i=1;i<=n;i++) cout<<a[i]<<" ";

}

Can anyone tell me the problem in my code for problem C2. I used Seg tree here.