When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Kilani's blog

By Kilani, 4 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +48
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

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

    I think authors didn't want to cut off solutions with such complexity.

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

      Authors solution seems to be a lot faster. Mine works in nearly 1.9 sec, which is very tight.

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

        I wrote this approach (which works in O(n*(nm + q))) and it works about 1076 ms on the worst test-case.

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

      Looks like it is impossible to distinguish between log n log m, which is approximately 100, and n / 2, which is 250.

      BTW the math markup appears to be broken, as a line break is added everywhere after using it.

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

        It makes sense but they could make q equal to 2e6.

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

        Do you know solution with such comlexity O(min(n,m)*nm + q)?

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

          Yes, I wrote it in my first comment.

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

            Can you explain it please?

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

              Well basically I reduce the problem into $$$O(n^2)$$$ arrays of length $$$n$$$ and then use some imple of RMQ. Stupid one is $$$O(n)$$$ per query, but (we all know) it can be solved in $$$O(n)$$$ precount and $$$O(1)$$$ per query using the method of four Russians.

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

                I'm sorry, but I still couldn't understand your algorithm. Would you mind elaborating it or posting your submit?

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

                  At first I precount a cubic dp[i][j][len] — best ans for a square len * len at position (i,j). Now when a query comes we need to check $$$O(n)$$$ squares to find the optimal answer. That's where I use RMQ (so it can be implemented in many ways). You can read more about best RMQ algorithms on wiki.

                  Submission is here 70999212.

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

                  I'm sorry, I mean the algorithm with the time complexity of O(n^3+q), which you have mentioned previously.

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

                  I suppose you can go here RMQ solution and follow Farach-Colton and Bender algorithm link.

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

    Because I haven't learnt 2D sparse table,I tried to solve the problem in

    $$$O(n^3+nmlog^2n+qlog^3n)$$$

    .But it seemed to be failed... In this problem,

    $$$O(log^3n)$$$

    is much slower than

    $$$O(n)$$$

    ...

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

      The problem is $$$log^{3}n$$$ is actually a lot more than $$$n$$$. Does anybody know what's wrong with math parsing?

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

        Yeah,you are right,so I have to rewrite my code now...

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

    Why I got TLE in O(n^3 + qn)??

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

      The TL is very tight, you must write optimal code to pass.

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

    can you tell me proof that the required element for problem number 2 is always the average of the lowest number and the highest number in the array? Thanks in Advance

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

      Formal proof: for any two numbers $$$a$$$ and $$$b$$$ we need to minimize $$$max(|a-x|,|b-x|)$$$. This happens when those functions intersect which occurs in $$$(a+b)/2$$$.

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

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)$$$

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

    You're right, sorry I will fix it.

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

      In the editorial of problem C, it's mentioned that (k+1) zeroes are given to (z mod g) groups and the remaining groups are given k zeroes.

      That means the number of substrings which need to be subtracted from the total

      $$$= \dfrac{k\cdot(k+1)}{2}\cdot(g-(z \mod g))+\dfrac{(k+1)\cdot(k+2)}{2}\cdot(z \mod g)$$$
      $$$= \dfrac{(k+1)}{2}[(k\cdot g-k\cdot(z \mod g))+(k+2)\cdot(z \mod g)]$$$
      $$$= \dfrac{(k+1)}{2}[(k\cdot g-k\cdot(z \mod g))+k\cdot(z \mod g)+2\cdot(z \mod g)]$$$
      $$$= \dfrac{(k+1)}{2}[(k\cdot g+2\cdot(z \mod g)]$$$
      $$$= \dfrac{k\cdot(k+1)}{2}\cdot g+(k+1)\cdot(z \mod g)$$$

      Despite being written in the explanation about the count of substrings having 'L' zeroes, the final equation was directly written.

      But nevertheless the editorial is very well written.

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

        Can You please explain, why are we assigning (k+1) zeroes to first z mod g group?

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

          See we that there are total z zeroes in the string and we want to equally divide it into the string in sets of continuous substrings of zeroes so that the substrings removed from the total possible substrings of the complete binary number get reduced.

          So, z zeroes need to be divided into g groups.

          $$$\left\lfloor{\dfrac{z}{g}}\right\rfloor=k$$$

          Let

          $$$r=z \mod g$$$

          So,

          $$$z=kg+r$$$

          Now if (g-(z mod g)) groups are assigned k zeroes and (z mod g) groups are assigned (k+1) zeroes, then total should come as z (as it's the total number of zeroes present).

          $$$k\cdot (g-(z \mod g))+(k+1)\cdot (z \mod g) $$$
          $$$= kg-k\cdot(z \mod g)+k\cdot(z \mod g)+(z \mod g)$$$
          $$$= kg+(z \mod g)$$$
          $$$= kg+r$$$
          $$$= z$$$

          Thus, (g-(z mod g)) groups are assigned k zeroes and (z mod g) groups are assigned (k+1) zeroes. Now we simply apply the formula of possible substrings when we have a string of length L as mentioned in the tutorial.

          It is not necessary that you assign the (k+1) zeroes to the first (z mod g) groups only. You can assign (k+1) zeroes to any of the (z mod g) groups out of the g groups available.

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

        thanks i was also unclear about (k+1)*(zmodg)

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

      In the D problem, the contraints for the number of steps is too weak (1<=a<=3000) when all the paths can be traversed in just 1500 steps only (even mentioned in the editorial as 3n steps).

      Kilani, I really have to admit the round as a whole was very well written along with the tutorials to the problems. Despite being a little tough round and getting a dip on my ratings, I have to say, I loved upsolving the questions of this round. Learned new concepts, especially from the E problem.

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

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

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

    Can you point where in the problem statement that "at most" is? I missed it.

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

      I mean here in the tutorial of F " you may use an edge that goes from a cell to another one with the same color at least once"

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

        Yes, I understand. But I cannot find that in the problem statement. So, I do not understand why this sentence is there.

        I think the problem statement says we can use edges between cells of same color as many times as usefull, no limit at all. Not at least, not at most.

        Can you explain?

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

          As i understood , you don't have to use two edges or more and stay in the same color .. because if you at the cell x and go to y with the same color then go from y to z with the same color.. that is not optimal because u can go from x to z directly .. so that i say you may use "at most" one edge

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

            Ahh, ok, makes sense. Use every color at most once.

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

              But what about going from color c1 to c1 then to c2 and then c2 again. Here we have used the "same-color type" edge twice!!

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

                The path never used the same color twice, because it would be shorter using the color only once.

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

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

    We can do this during the BFS.

    We need to BFS for $$$k$$$ times and every time we calculate one color. Now we only consider one BFS which calculates color $$$a$$$.

    Let $$$d$$$$$$i$$$$$$s$$$$$$[$$$$$$i$$$$$$]$$$ the minimum cost from color $$$a$$$ to cell $$$i$$$.

    During the BFS, when we reach cell $$$u$$$, whose color is $$$b$$$, we update all the cells in color $$$b$$$ by $$$d$$$$$$i$$$$$$s$$$$$$[$$$$$$u$$$$$$]$$$$$$+$$$$$$1$$$, because we can go to them from $$$u$$$ in one second.

    In this way, when finding pathes we can use "tunnels" of more than one color.

    Here's my code. 71045624

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

      I see. Since you have to do this for every pair of colors only once you use cvis[]. Thanks!

»
4 years ago, # |
Rev. 4   Vote: I like it -29 Vote: I do not like it

Nevermind, I messed up with author's solution

»
4 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

.

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

    Imagine that you have a set of 1D points and need to find a point such that maximum distance between this point and any point in the set is minimised.

    This is exactly the same problem here. The point that will minimise that distance is the mid point.

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

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

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

    Place all the determined numbers on an axis, and your mission now is to find a point where the maximum of the distance from that point to any other points is minimized. There are three conditions: on the left of the min, on the right of the max, and in between the min and the max. It's obvious that the first two conditions are not better than the third one, and in the third one You'll find out by intuition(apparently) that the mid point of the min and the max is the optimal choice. On top of that, you have to consider the determined numbers adjacent already, which have to be calculated, and is hinted in the sample.

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

"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 ?

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

Can someone explain the binary search version of B?

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

    The problem asks to find the smallest number of an absolute value function. If you plot an absolute value function (for eg. f(x) = |x|) on a graph, it's V shaped — both negative and positive values of x converge at a minima (in case of f(x) = |x|, that minima is 0). The goal is to find this minima.

    In the given problem, f(x) generates a similar graph — if mid is too large, then f(x) (which returns the max between mid and every element in the array) can be very large. Same thing when mid is too small (the absolute difference between max value and mid can be very large). You want to find the right middle ground.

    So, by comparing f(x) with f(x+1), you can get a sense of which direction to go: - If f(mid) <= f(mid+1), you want to go the direction of mid. Drop the second half of the array (mid+1 through high), and focus on low through mid - If f(mid) > f(mid+1), you want to go the direction of mid+1. Drop low through mid, and focus on mid+1 through high.

    So in a gist, keep comparing mid with mid+1, and go in the direction of the smaller value. Stop as soon as l>=h. (Reference: https://codeforces.com/contest/1301/submission/71083423)

    There's another approach (https://codeforces.com/contest/1301/submission/70970135) which seems to follow a similar concept though I'm not clear on the implementation details.

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

      Can i suppose that ternary search is easy to think/realise in case of mod based problem than binary. Binary seach is also logical but need more implementation. I should apply ternary seach algo in case of mod/parabolic functions ?

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

    Actually, a ternary search may be more appropriate than a binary search here: https://cp-algorithms.com/num_methods/ternary_search.html

    (Reference: https://codeforces.com/contest/1301/submission/70967290)

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

Thanks for the quick editorial <3

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

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please tell me how you come up with this solution?

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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://codeforces.com/contest/1301/submission/71003726.

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

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…

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

    Read the code, then you can understand it.

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

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

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

    Let us denote minimum value by min, maximum value by max. Let us assume that k is best at some point other than the average say t, this gives the cost to be maximum(abs(max — t), abs(min — t)). Case 1: t > average, cost = t — min > average — min >= average — min + 1 (since average can be 1 more from the right than left). Therefore the calculated cost is greater or equal to the cost when we choose k to be the average of minimum and maximum value. Similarly, we can show for the case when t < average. I hope that helps.

    `

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

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

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

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.

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

    Because you can consider ,Test_case: 1 -1 100 -1 101 So as per your logic k=67 so m=66 but if you do k=(max+min)/2 k=51 so m=50 I hope this helps!!!

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

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.

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

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

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

    Can you please explain me the proof for it

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

    Yes can anyone give the proof for this?

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

      Well the hint to the proof is: you can see that for

      $$$f(x)=\frac{x\cdot(x+1)}{2}$$$

      and you have $$$x_1=t-d$$$ and $$$x_2=t+d$$$, $$$x_3=t$$$ and $$$x_4=t$$$,

      we have, $$$x_1+x_2=x_3+x_4$$$ and,

      $$$f(x_1)+f(x_2)>f(x_3)+f(x_4)$$$

      so, reducing the "distance" between variables always minimises the value of the function.

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

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

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

B's second test's 369th testcase sucks

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

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}$$$.

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

Hi, Kilani, 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.

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

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

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

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;

}"> ...

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

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 !

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

Nice and Useful Contest

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

174332065 i tried problem B using binary search but it is giving wrong answer on test case 2 ? anyone please help ?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I really don't know how to binary search it , but you can visualize a line of points( a rope) going up from min to max values in the array adjacent to the -1. you can see that the only two points that we want to care about is the max and the min why? because our maximum will really be impacted by the maximum and the min more than the other points because the maximum value of abs value can't actually come from other points (visualize it and try to convince yourself)

    now let's proove for maximum-min even and do the odd yourself,

    let's proove that the best answer is X=(maximum-minimum)/2

    this way we can say the maximum Abs Value is X right? right .

    it's obvious that we can't make X above maximum because we can minimize the max by lowering X :) (same for below the minimum)

    now let's discuss the case the new X is between maximum and minimum and not the old X (maximum-minimum)/2 , so let's say X=X+delta,

    say delta > 0 (the same thing for delta <0) this way we got further from the minimum -> our max abs value will be bigger by that delta

    I think this method of proof is called the exchange arguments.