LOL, my solution for E in $$$O(n^3+qn)$$$ passed. Although, I know how to make it $$$n^3+q$$$.

Typo in C, should be $$$\dfrac{n\cdot(n+1)}{2} - \dfrac{k\cdot(k+1)}{2}\cdot g - (k+1)\cdot(z\mod g)$$$

AntiBsayer Thank u for this Editorial But i thnik you mean "at most" instead of "at least" in the last problem tutorial !

Problem F, how do we find a path where we have to use "tunnels" of more than one color, one after the other?

Nevermind, I messed up with author's solution

.

I don't understand why the solution works for problem B

"The current mid is correct if the maximum element in that 2D range is greater than or equal to (4⋅mid⋅mid)". How does the existence of such an element guarantee that the answer >=4*mid*mid for the given submatrix ?

Can someone explain the binary search version of B?

Thanks for the quick editorial <3

Let me show a solution for problem D with quite short code. 71031620

Move like this: Pictrue

1. Constuct the "ans" string to go through all the grids with 'R' 'U' 'L' 'D'.
2. Cut out the first k characters of the string.
3. Merge the consecutive characters as one step.

The largest number of steps is 2996.

E can be solved in O(n^3 + q log n) without the use of data structures. Call a red point such that they are part of the center of a Nanosoft logo a "critical" point, and it's "range" half the maximum subsquare that can be a Nanosoft logo. Then we can run binary search on answer. In order to check if subrectangle (r1, c1) — (r2, c2) can contain a subsquare of size m such that it is a Nanosoft logo, the subrectangle (r1 + m — 1, c1 + m — 1) — (r2 — m + 1, c2 — m + 1) must contain a critical point with range m (and it's green, blue, yellow counterparts as well). In order to check this in O(1), we can use prefix sums, and since you need to calculate it for all values, it works in O(n^3). Here is my code: https://mirror.codeforces.com/contest/1301/submission/71003726.

Question of problem F "But visiting all other cells that has the same color every time is too slow, so we can only visit these cells when we reach the first cell from every color." what does that mean? How do you complete bfs while skipping grids with same color? I did not understand this part…

Can anyone mathematically prove for problem B that the best k is equal to (minimum value + maximum value)/2 ? Thanks.

I am having problem in question C for k size string their will be k*(k+1)/2 substring but for k+1 size why the total substrings are k+1 ? UPD: i got it now

Hello,

In Problem 1301B, why doesn't calculating the mean(average) of all the non-negative numbers adjacent to -1s, instead of (minimum value + maximum value) / 2, give the correct answer. Really stuck at this :) Thank you for the help.

Why did no one ask about whether you can rotate the square in problem E to make it a valid logo...? I think this should be made a clarification for future virtual pariticipants.

The hard part of the proof in C is proving that it should be "as equal as possible". The author conveniently skips that.

Why does this straightforward $$$ O(n * m * k + q * k) $$$ solution fail for problem F https://mirror.codeforces.com/contest/1301/submission/72293018

B's second test's 369th testcase sucks

I have an alternate solution to E with time $$$O((nm+q)\sqrt[3]{nm})$$$.

A logo with radius $$$k$$$ has area $$$4k^2$$$, and logos can't overlap. So, there are at most $$$\frac{nm}{4k^2}$$$ logos with radius at least $$$k$$$.

Because large rectangles are rare, we can check each of them with every query. And for smaller rectangles, we can build a DP table of size $$$n\times m\times k$$$ to quickly check for small logos in a subrectangle.

Preprocessing takes $$$O(nmk)$$$ time and each query takes $$$O(k+\frac{nm}{k^2})$$$ time, which is optimal when $$$k=\sqrt[3]{nm}$$$.

Hi, AntiBsayer, somethings puzzled me in problem F:

1. what's the "+1" for in "Otherwise you should find the best color that you will use that edge in it, the cost will be (the minimum cost between any cell of that color with first cell + the minimum cost between any cell of that color with the second cell + 1)."?

2. don't we need to consider the possibility of jumping using multiple colors? As I see from your code, it seems it just use one color for jumping in the min solution.

In problem C can someone please explain me the proof for why the greedy strategy of dividing m+1 groups "as close as possible" works

Here my Binary Search approach for B, I check all the difference using binary search and choose the smallest one.

<spoiler summary="#include<bits/stdc++.h> using namespace std;

define ll long long int

define ul unsigned long long int

define speed ios_base::sync_with_stdio(false); cin.tie(NULL)

int main() { speed; int t; cin>>t; while(t--) { ll n,l=0,h=INT_MAX,ans=0,diff; cin>>n; ll a[n]; ll m=-2; bool minus=true; for(ll i=0;i<n;i++){ cin>>a[i]; m=max(m,a[i]);

    if(a[i]!=-1)
      minus=false;
    }
    h=m;
    if(minus==true)
    {
      cout<<0<<" "<<0<<'\n';
      continue;
    }
    while(l<=h)
    {
       ll m=l+(h-l)/2,rl=0,rr=INT_MAX,p,q;
       bool possible=true;
       for(int i=0;i<n;i++)
       {
         //cout<<a[i]<<" leftrange="<<rl<<" rightrange="<<rr<<'\n';
         if(i<n-1&&a[i]==-1&&a[i+1]!=-1)
         {
          p=rl;
          q=rr;
          rl=max(a[i+1]-m,rl);
          rr=min(a[i+1]+m,rr);
          if(!(rl>=p&&rr<=q))
          {
              possible=false;
              l=m+1;
              break;
          }
         }
         if(i>0&&a[i]==-1&&a[i-1]!=-1)
         {
          p=rl;
          q=rr;
          rl=max(a[i-1]-m,rl);
          rr=min(a[i-1]+m,rr);
          if(!(rl>=p&&rr<=q))
          {
              possible=false;
              l=m+1;
              break;
          }
         }

             if(i<n-1&&a[i]!=-1&&a[i+1]!=-1)
             {
                if(m<abs(a[i]-a[i+1]))
                {
                   possible=false;
                   l=m+1;
                   break;
          }
          }
       }
       if(possible)
       {
         ans=(rl+rr)/2;
         h=m-1;
       }
    }
    for(int i=0;i<n;i++)
    {
       if(a[i]==-1)
       {
         a[i]=ans;
       }
    }
    diff=-1;
    for(int i=0;i<n-1;i++)
    {
       //cout<<a[i]<<'\n';
       diff=max(diff,abs(a[i]-a[i+1]));
    }

    if(ans>=0&&ans<=m)
    cout<<diff<<" "<<ans<<'\n';
}
return 0;

}"> ...

My Pattern for D:

1. From [1,1] go Right to [1,n]
2. Go down to [2,n]
3. Go left to [2,1]
4. Go down to [3,1]
5. Again Go right to [3,n]... i.e. keep repeating steps 1,2,3,4 till possible i.e. until you reach [n,n]
6. Made bool right to handle odd/even length of n.
7. Now we are either at [n,n] if n is odd, or at [n,1] if n is even
8. If we are [i,1] we go UDR until we reach [i,n] then we go Up then goto step 9.
9. If we are [i,n] we go UDL until we reach [i,1] then we go Up and goto step 8.
10. Keep Repeating steps 8 and 9 until you reach [1,n] and make the final call to go only L to [1,1].

I agree the Editorial's approach is a bit simplier.

Also, I was unable to fix an upper bound to as how many number of steps were required, so I simply checked the Max. Case 500 500 998000 and submitted. I'm not sure though. I think constraints for 'a' could be tightened.

Anyways, Great Problemset !

Nice and Useful Contest

we can use Parallel Binary Search to solve problem E