Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Medeowex's blog

By Medeowex, 5 months 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

»
5 months 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$$$.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.

    • »
      »
      »
      5 months 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.

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

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

      • »
        »
        »
        »
        5 months 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)?

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

          Yes, I wrote it in my first comment.

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

            Can you explain it please?

            • »
              »
              »
              »
              »
              »
              »
              5 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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.

  • »
    »
    5 months 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)$$$

    ...

    • »
      »
      »
      5 months 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?

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

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

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

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

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

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

»
5 months 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)$$$

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

    You're right, sorry I will fix it.

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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?

        • »
          »
          »
          »
          »
          5 months 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.

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

            Yeah now understood completely Thanks alot!!

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

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

    • »
      »
      »
      5 months 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).

      Medeowex, 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.

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

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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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"

      • »
        »
        »
        »
        5 months 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?

        • »
          »
          »
          »
          »
          5 months 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

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

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

            • »
              »
              »
              »
              »
              »
              »
              4 months 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 months 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.

»
5 months 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?

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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!

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

Nevermind, I messed up with author's solution

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

.

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months 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.

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

      Nicely Explained!

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

      Thank you!!! I understood at once B as soon as read "Place all the determined numbers on an axis".

»
5 months 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 ?

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Can someone explain the binary search version of B?

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

    I think in that way too but can't find its correctness. here my partial solution :- why have range of k from 0 to 10^9. for every mid we check if it is lower from both its adjacent elements if it is then thats may be answer(i think it might be local minima where there is a trick). if not then it may be either non increasing or non decreasing which is again a trick.

    I dont know whether binary search may work If someone have solved it or wanna add up in it please explain.

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

    I would say it's rather a standard ternary search problem. It is easy to observe that k varies on a convex function,i.e there is a local minima which is our required answer. In each iteration, we check the function value at mid and mid+1 and accordingly reset our low and high till the while loop ends.

  • »
    »
    5 months 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.

  • »
    »
    5 months 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)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the quick editorial <3

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B, why can't I just take all the non missing elements instead of taking only adjacent to missing elements?

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

    because that will make the answer worse, consider the following testcase 1 4 100 -1 1000 1000 the answer is 450 550 if you take those adjacent elements. but if you take all non missing element then you answer will be 600 700.

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

      I got such test cases. Can you please expalin why adjacent numbers like 1 4 100 or 1000 1000 always make the answer worse ?

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

        because the extra 1000 has nothing to do with the answer consider 1 -1 100 1000 -1 1000 10000 , in this case the only best thing you can do is to find a integer such that it will give minimum absolute difference with 1 & 1000. ' Why only 1 & 1000??? Because they are adjacent to -1 but now the question is , 100 is also adjacent to -1 why we are not considering it?? Because it is not contributing to the answer. As we have to minimise the absolute difference, only two integer(1 & 1000) are affecting the answer like if we choose k=500 as then (1000-500)=500 && (500-100)=400 && (500-1)=499; so you can see in absolute difference ,100 is not contributing to the answer, it will always come from MAX and MIN adjacent element.Similarly all the element which are not adjacent to the -1 are not affecting the answer coming from replacing the -1 with k. They have their constant absolute difference(which might be greater, but k has nothing to do with it).As in our case the answer will 9000 (10000-1000).

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

          got it..thanks

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

          Thanks a lot. Now I understood mistakes in my reasoning.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me why this solution fails? https://codeforces.com/contest/1301/submission/71037252

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

@Medeowex by this line in problem C:-"we should give every group k zeroes, except for the first (zmodg) groups, we should give them k+1 zeroes." you mean there are infinite no of strings are made having maximum substrings since you placed (xmodg groups with k+1 zeros at starting remaining spaces? btw thanks for really good problems and contest!!

»
5 months 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.

»
5 months 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…

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

    Read the code, then you can understand it.

»
5 months 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.

  • »
    »
    5 months 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.

    `

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

Cam someone please tell me why my binary search solution is getting timed out

https://codeforces.com/contest/1301/submission/71014146

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me how to solve 'B' by using Binary search??

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

    Do a binary search with:
    low = smallest element
    high = largest element
    if both low and high remains -1 then answer will be 0 and any number can be treated as K.
    otherwise:
    find mid and calculate the maximum absolute value of the adjacent element with K as mid and do same for mid-1 and mid+1
    See the Solution to know about how low and high will change.

»
5 months 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

»
5 months 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 months 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!!!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I cannot seem to pass Test Case #2 for C...However, I don't know how to improve my code. Any help would be appreciated!!

PyPy3:


T = int(input()) for case in range(T): n, m = [int(x) for x in input().split()] g = m + 1 z = n - m k = int(z/g) A = n*(n + 1)/2 - (k*(k + 1)/2)*g - (k + 1)*(z % g) print (int(A))
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It turns out that doing:

    n, m = [int(x) for x in input().split()]
    

    is too slow. Instead, this is better:

    from sys import stdin
    
    n, m = [int(x) for x in stdin.readline().split()]
    
»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone help why this code for problem B gets wa ??:( tnx in advance.this

»
4 months 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 months 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B's second test's 369th testcase sucks

»
4 months 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}$$$.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months 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

»
6 weeks 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;

}"> ...