DmitryGrigorev's blog

By DmitryGrigorev, history, 4 weeks ago, translation, In English,

(Idea of the problem Div2A — ScreaMood)

(Developer of the problem Div2A — DmitryGrigorev)

Tutorial is loading...

Code

(Idea of the problem Div2B — Choopa_choops)

(Developer of the problem Div2B — DmitryGrigorev)

Tutorial is loading...

Code

(Idea of the problem Div1A — Mr.Hakimov)

(Developer of the problem Div1A — Mr.Hakimov)

Tutorial is loading...

Code

(Idea of the problem Div1B — DmitryGrigorev)

(Developer of the problem Div1B — PeregudovSergey)

Tutorial is loading...

Code

(Idea of the problem Div1C — osaaateiasavtnl.)

(Developer of the problem Div1C — osaaateiasavtnl.)

Tutorial is loading...

Code

(Idea of the problem Div1D — DmitryGrigorev)

(Developers of the problem Div1D — osaaateiasavtnl. и DmitryGrigorev)

Tutorial is loading...

Code

Read this comment of socketnaut about another approach for this problem.

(Idea of the problem Div1E — DmitryGrigorev)

(Developer of the problem Div1E — TheWayISteppedOutTheCar)

Tutorial is loading...

Code

 
 
 
 
  • Vote: I like it
  • +105
  • Vote: I do not like it

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

For Div1 D can someone help me prove/disprove how is this strategy working:
For any node L to get minimum sum we choose two children u and v such that dp[u]-2*n*sz[u] and dp[v]-2*n*sz[v] are smallest among all the children?

My code: 55909246

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

    I'm not sure about your strategy. But I find that the complexity of your code can be reduced into O(n) by using bubble sort to obtain the minimum and second minimum value.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I support the question.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It looks like your code also fails on socketnaut's test case here.

    Correct answer is 1019. Your code outputs 1018.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Here's the input:

      35 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 19 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35

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

      I just ran my code on this example. Its giving correct output- 1019
      https://ideone.com/UAyyqj

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Interesting. I guess the order of input data matters. We need the degree three vertex to be the root.

        Input I used

        https://ideone.com/kPEg0m

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

Thanks for the great editorial!

I have a question about Div1C editorial. In definition of x, isn't it supposed to be the maximum x (instead of minimal) that satisfies the mentioned condition?

If I'm wrong, can you please tell me why?

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

    But money isn't a problem at all for Serge, so Serge is buying the most expensive dish if there is at least one remaining.

    There is a typo in the editorial. Also if you check editorials source code for that problem, you will see that it finds maximal X.

»
3 weeks ago, # |
  Vote: I like it +53 Vote: I do not like it

In D, we only need to consider the two best dp values for each unique subtree size. With that observation, there's no need for CHT: we can just check all pairs quadratically and it will still be fast enough.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry for my not understanding…… But doesn't it have a complexity of $$$O(n^2)$$$ when facing a graph that each vertex has an edge to the same vertex?

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

      At each node, it’s quadratic in the number of distinct child subtree sizes. Your tree has a node with many children, but they have only one distinct subtree size.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same idea. This clearly takes O(n sqrt n) but I'm wondering if there's a tighter bound.

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

      I think it's way faster than that, like $$$n \log \log n$$$. Credit due to dinosaurs and danielfleischman.

      Suppose $$$f(n)$$$ is an upper bound on work done on a tree with $$$n$$$ nodes. We need $$$f(n) \geq k^2 + \sum_i { a_i \cdot f(i) }$$$ for any $$$a_i$$$ where $$$\sum_i a_i \cdot i = n - 1$$$ and $$$a_i$$$ has $$$k$$$ non-zero elements.

      Let's write $$$f(n)$$$ as $$$n \cdot g(n)$$$, and let's rewrite $$$\sum_i { a_i \cdot f(i) }$$$ as $$$\sum_{i < \sqrt{n}} { a_i \cdot i \cdot g(i) } + \sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(i) }$$$.

      The first sum is at most $$$\sum_{i < \sqrt{n}} { a_i \cdot i \cdot g(\sqrt{n}) }$$$ which is at most $$$n \cdot g(\sqrt{n})$$$. The second sum is at most $$$\sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(n) }$$$ which is at most $$$\sqrt{n} \cdot g(n)$$$.$$$^\dagger$$$

      Finally, $$$k^2 \leq 2\sqrt{n}$$$. So $$$f(n) \geq k^2 + \sum_i { a_i \cdot f(i) }$$$ becomes $$$n \cdot g(n) \geq 4n + n \cdot g(\sqrt{n}) + \sqrt{n} \cdot g(n)$$$.

      Dividing by $$$n$$$ gives $$$g(n) \geq 4 + g(\sqrt{n}) + g(n)/\sqrt{n}$$$. $$$g(n) = 4\log \log n$$$ satisfies it for sufficiently large $$$n$$$.

      $$$\dagger$$$ The root of a tree on $$$n$$$ nodes cannot have more than $$$\sqrt{n}$$$ child subtrees each with at least $$$\sqrt{n}$$$ nodes.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        I think that $$$n \log \log n$$$ is also the worst case. We can construct a tree with a structure similar to the Sqrt-tree in which each node with subtree size $$$x$$$ has $$$O \left ( \sqrt{x} \right )$$$ children with distinct subtree sizes of at least $$$O \left ( \sqrt{x} \right )$$$. There will be at least $$$O \left ( \log \log n \right )$$$ layers that take $$$O \left ( n \right )$$$ time each.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        Could you explain why $$$\sum_{i \geq \sqrt{n}} { a_i \cdot i \cdot g(n) }$$$ is at most $$$\sqrt{n} \cdot g(n)$$$ with more detail? For example, what if the node has only one child whose size is $$$n-1$$$ ?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am wrong, sorry. Do you see how to fix it?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            I don't know how to fix it either. A progress is that there exists a worst case in which $$$a_i \in \lbrace 0,1\rbrace$$$.

            Proof: First observe that $$$f(a+b) \geq f(a)+f(b)$$$. Let $$$m$$$ be the largest number which satisfies $$$a_m > 0$$$. If there exists an $$$a_i >1$$$, it doesn't take less time to let $$$a_i=a_i-1, a_m=a_m-1,a_{i+m}=a_{i+m}+1$$$(after this operation, $$$m$$$ becomes $$$i+m$$$).

            And I wrote a dp program which runs in $$$O(n^{2.5})$$$ to calculate the worst time. When n=500, the worst time is about 2700 operations. When n=5000, the worst time is about 31000 operations. It seems the time complexity is really something like $$$O(n \log \log n)$$$ or $$$O(n \log n)$$$.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
              Rev. 2   Vote: I like it +10 Vote: I do not like it

              If we assume that $$$f(n)$$$ is convex, it means that $$$f(x-1)+f(y+1) \ge f(x)+f(y)$$$ where $$$x \le y$$$. Following from this convex property and $$$a_i \in \lbrace 0,1\rbrace$$$, there is a worst case such the sizes of the children of any node with subtree size $$$n$$$ are $$$1, 2, 3, ..., k, n-1-\frac{k(k+1)}{2}$$$.

              Consider the heavy path from any node with subtree size $$$n$$$ to a leaf. Whenever we do $$$O \left( k^2 \right)$$$ work and move down to the heavy child, the size of the subtree decreases by $$$O \left( k^2 \right)$$$, so the total work of this heavy path is $$$O(n)$$$.

              Each time a node changes the heavy path it's on while moving to the root, the subtree size will be squared, so each node will be included in $$$O(\log \log n)$$$ heavy paths. It follows that the time complexity is $$$O(n \log \log n)$$$.

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

                Good proof!

                We can prove $$$f(n)$$$ is convex as follows, i.e. $$$f(n+1)-f(n) \geq f(n)-f(n-1)$$$.

                If $$$f(n)$$$ is convex when $$$n \leq k$$$, then it can be proved that $$$f(n) \leq c \cdot n \log \log n+d(n \leq k+1)$$$ using your proof. Just let $$$f(n)=n \log \log (n)$$$ since the constants $$$c,d$$$ make no sense(by now) and $$$f$$$ represents the upper bound. We only need to prove $$$g(x)=x \log \log x - (x-1) \log \log (x-1)$$$ is an increasing function.

                Though $$$g$$$ isn't always increasing, it's increasing when $$$x > 10$$$. We can assign some constants to $$$f(x) (x \leq 10)$$$ to ensure $$$f(x)$$$ is convex when $$$x \leq 10$$$. Then we add a proper constant $$$d$$$ to $$$f(x) (10<x\leq k+1)$$$ to ensure $$$f(x) (1 \le x \le k+1)$$$ is convex.

                So $$$f$$$ is convex.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Oh, we knew this solution but we thought it`s something like $$$n^{\frac{3}{2}}$$$. Great thanks to you for this comment.

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

DmitryGrigorev for div 1 c what you mean by the line.. "Now to find the answer we can use a segment tree that maintains a balance between the number of dishes and the number of pupils for all suffices of values"

which segment tree to use what balance we need to mantain. what to add in segment tree?. can you explain this more.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sort all pupils and dishes with value, add them from big to small, dishes are $$$+1$$$, pupils are $$$-1$$$, the answer is the maximal $$$k$$$ that sum of $$$[k,1000000] > 0$$$.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But how to find this maximal k? What to store in nodes?

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

        Use segment tree to count the maximum suffix sum.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          And check every suffix? It'll be comething like O(n log n). Or maybe there is more efficient algo? Can you help me plz?

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

sir , my approach was same for question 1180b , but it failed at 9 th pretest .. reason was the big product value. i used 'long long int ' and i am not aware of any data type bigger than that. i solved using c language . please help ,how to overcome that.

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

      C++ can't handle big integer using inbuilt data type, at max i saw int128 something, so instead u can deal with logarithm of numbers and operation performed will be addition .even if u implement in python for handling big integers,it will rise tle,i guess.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You don't need to calculate the product, just work out its sign. This is easy, since after the loop all the ais are negative (if x>= 0 then |-x-1| > |x|). As such the product is negative if and only if n is odd.

      See my code (in Python)

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

sir , i got the same approach in 1179b ,but was confused to think about the case in which case is not possible and we need to print -1 there ..... by this algo even if some points repeat , it will be very hard to keep on check on each point visited and will further will take a long time ,resulting in TLE ...... can you please give me an example where we cant visits all cell block and hence -1 prints .... thank you;

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we never will print -1 because we always have a way which is mentioned above to visit the all cell block.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ohh, i wasted alot of time thinking that where will we use -1 ,even though i got basic algo concept of it within two minute . so i didn't attempted that at last. very sad.

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

What is CHT?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    where i have written CHT ??? or its a general question?

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

    I would like to point out here, to editorialist, that it would be appreciated not to use short forms in tutorial/explanation so that people who don't know about it don't get further confused with something else. Even if you don't write the full form in the paragraph, maybe mention at the end, like below. If you let's say talk about CHT, and DSU.

    Here ( just example )

    CHT means Convex Hull Trick.

    DSU means Disjoint Set Union, etc

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      To me it is not hard to get the acronyms provided that they are aforementioned in a short paragraph, because I got that CHT thing by quickly skimming through the tutorial for 1179D again when I saw his comment, but that is probably just me though :|

      Also I think it is just as good to write a word's acronym right after itself, like "Convex Hull Trick (CHT)."

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In DIV2 problem B why is the following statement required: "if (n != 3 || (v[0] != -3 || v[1] != -3 || v[2] != 2))"

Even without this line the code is being ACCEPTED.

submission

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Didn't you answer your own question? If it is accepted then the statement is not required ( this is true, assuming tests are not weak ). And I can assure you, tests are not weak. A lot of people had submissions fail on system tests.

    To properly answer your question, No, that line is not required.

    Another tip: instead of trying to understand code provided, it is a better practice to read the explanation and try to write the code yourself.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I see. And thanks for the tip, I'll keep it in mind from now.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

" Now to find the answer we can use a segment tree that maintains a balance between the number of dishes and the number of pupils for all suffices of values. " What do they mean by maintaining balance and suffices of values? In div1 C.

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

Can someone please help me in fixing my code , it passed 8 pretests but blowed up on 9th one

the link of the code is given below https://codeforces.com/contest/1180/submission/55891316

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this: 5 -3 -3 1 1 -1

    I think you need to use operation on minimum element (not abs min) when n%2==1 my acc output: 2 -3 -2 -2 -1 your: -3 -3 -2 1 -1 In second and third tests all values equals after using operation on non-negative elements and it's not important what element changed.

    (sorry for my english)

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice editorial.

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

Maybe in problem A for di2 you mean O(1)?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Although the editorial code calculates it in O(1), it’s still possible to calculate it in O(n).

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, can you help me in understanding the function used in editorial code? How did he got that?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can calculate the answer for small values of n by hand (draw a picture) and look for a pattern.

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

I think solution of Problem B of DIV 2 (1180B) is wrong. Because it's written that if the product is already positive, it's the answer. Else to apply the operation to the minimal number is obviously optimal. But I got the solution accepted when I applied the operation to the maximal number in the array and found it more sensible. Am I right here ? if not please correct me.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes it's the minimal number

    In your code you chose the minimal number too

    PS: The minimal number is the maximum after taking absolute values of all

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think I understood the meaning of Minimal as the smallest number in an array. Now I understood the solution. Thanks!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Author solutions means, that you should do all numbers maximum on modulo (because abs(-a-1) > abs(a)). And if we have even count of numbers, which are maximum on modulo it is the answer.(because — * — = +). But if count of numbers is not even we sholud find minimum of these negative integers, and we will do maximum positive integer. Maybe you mean find maximum on modulo?

»
3 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

In case you're looking for a proof/ intuition behind why the approach in 1180B — Nick and Array — works, here is some food for thought:

When n is odd, increasing the magnitude of all the elements will leave us with a negative product because of odd number of negatives.. So we have to apply the transformation on one of the elements again -- which will make the product positive again.

Let's just concentrate on the magnitude of numbers - we have a series of numbers to multiply — a1 * a2 * a3 * ... an — we have to decrease the magnitude of one of these by 1. Which element do you pick? — You pick the one with the highest magnitude
Why does this work?
we have to maximize (a1 * a2 * a3 * ... an) -- so we can think of it as maximizing the sum of their logarithms — (log|a1| + log|a2| + log|a3| + .. log|an|) .. Because of how log function "straightens out", the decrease in log value will be the least when |ai| is the highest -- we are looking further right on the log graph — that's why you choose the one with the highest magnitude and decrease it

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great to see how you put it in logarithms.

    I did pick the lowest element (in magnitude) at first smh, but later found out a test that invalidated my solution.

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

In Div. 2 E/Div. 1 C, shouldn't it be the maximum x instead of the minimum?

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

In div1B, the coordinates can be expressed as one dimension,that is i,j=x*m+(y-1). The jump is i->j->i... for all i-j and j-i are different, the algorithm is proved.

My code:55987211

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

For div1 C it is not written anywhere that people will leave after buying one dish so it is possible that people buy other dishes with remaining money but the solutions accepted doesnt seem to handle these cases for example- 2 1 99 1 1 1 2 1 100 for this testcase answer should be -1 but output is coming 1 can someone explain how??

»
3 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

https://codeforces.com/contest/1180/submission/56009139 Any idea why I am getting TLE for 1180B?

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

Why I got TLE in the problem DIV2 D when I use endl but got AC in the '\n'? TLE Submission: https://codeforces.com/contest/1180/submission/56012176 AC submission: https://codeforces.com/contest/1180/submission/56012511

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

    When you use endl, it is basically the same as '\n' but it also flushes cout and thus works a little bit slower. In fact, this optimization is usually pretty useless, in this problem replacing long long with int was enough.

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

In problem C-Div1, shouldn't the answer be "maximum" x which satisfies the condition that the number of dishes with cost ≥x is strictly more than the number of pupils who have more than x togrogs?

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

The std of Div1 D prints 180 while my program prints 181 when inputting this data onto them:

15

2 1

3 2

4 2

5 4

6 3

7 1

8 6

9 1

10 9

11 2

12 11

13 11

14 4

15 2

When we connect node 8 and node 10, we can get a better answer 181.

So is there a bug in std? Or have I misunderstood the problem?

My submission: http://codeforces.com/contest/1179/submission/56058316

(By the way, the data are so weak that both my code and std accepted the problem...)

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

Can anybody explains the idea behind how segment tree is used to solve this problem https://codeforces.com/contest/1180/problem/E? From the editorial its not clear.

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

can somebody help me with the following code: https://codeforces.com/contest/1180/submission/56155460

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your declaration takes a very huge amount of memory, namely.

    ll a[101001111];
    

    This is a (long long) array of 101001111 elements of 64-bit size. The amount is approximately: 101001111 * 64 / (8 * 1024 * 1024) ~ 770.58 MB, which is larger than 256 MB allowed in the problem statement.

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

i still didn't understand div 2 B why aren't we considering the fact that pos nos are even or odd??because on converting odd no of postive integer we will end up with negative product. pls reply

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I find this approach to be easier and intuitive. First you need to convert all elements to non negative integer that is either zero or positives. Now you just need to sort the array and then make elements negative pairwise so that you can get maximum product at the end. If your array length is odd then you don't need to add any condition you just need to leave the last element as it will handle itself the maximum product. For example if your array is -2 -4 -1 0 0 1 2 3 then after converting them to non negatives it becomes 1 3 0 0 0 1 2 3 now after sorting and making the elements pairwise negative you will get 0 0 0 1 1 2 3 3 --> -1 -1 -1 -2 -2 -3 -4 -4 now you can restore your array order by sorting it with index for that you can store it in pair.

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

Can someone please explain div2 A editorial? I am not able to understand the sequence given in the editorial code.

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

Div1D problem statement not clear. and how is the no of simple paths for

1

1 2

2

we cannot get a simple path of len>=2 max it could be 1 as its only one pair of vertices.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D, Div. 1, from what I understood they say that dp[L] = min(dp[p1] + dp[p2] + (n — szp1 — szp2) ^ 2). I agree with that, but then they say that we get n^2 + dp[p1] − 2⋅n⋅szp1 + dp[p2] − 2⋅n⋅szp2 + 2⋅szp1⋅szp2. Shouldn't it be n^2 + dp[p1] − 2⋅n⋅szp1 + dp[p2] − 2⋅n⋅szp2 + 2⋅szp1⋅szp2 + szp1^2 + szp2^2?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 B can someone help me in telling the basic idea of the problem and how will we achieve the strategy discussed in the tutorials