gyh20's blog

By gyh20, history, 2 weeks ago, In English

Upd: fixed author's solution links.

Sorry for the slow Editorial, I am new using Polygon.

Special thanks to csani for his help.

About one hour before the contest postscript found the same problem, then we changed it to $$$k=4$$$ and he found another same one again. We are running out of time so we didn't have time for a new one, so we changed $$$k$$$ to $$$5$$$. But we didn't know there is still a similar problem. Sorry again.

Tutorial is loading...

idea:gyh20 solution:gyh20 tutorial:csani

Jury solution:92671575

Tutorial is loading...

idea:tianbu solution:tianbu tutorial:tianbu

Jury solution:92671590

Tutorial is loading...

idea:gyh20 solution:gyh20 tutorial:tianbu

Jury solution:92671713

Tutorial is loading...

idea:isaf27 solution:gyh20 tutorial:csani

Jury solution:92671763

Tutorial is loading...

idea:gyh20 solution:gyh20 tutorial:gyh20

Jury solution:92671740

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

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

Thanks for the fast editorial! It was an amazing contest (besides problem B)!

UPD: Problem E editorial has a typo: tutotial -> tutorial.

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

    Hi, in 1406B — Maximum Product, after sorting in descending order, i think it is feasible to check only 3 values that are 5 entries from top and none from bottom, 3 from top and 2 from bottom, 1 from top and 4 from bottom and then simply find their max :)

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

      Yes, I did that way, you can see my submissions. I just said that because problem B could be easily googled.

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

        Oh okay, i thought you got stuck somewhere :)

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

Couldn't solve E, but it was interesting(atleast to me).

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

Auto comment: topic has been updated by gyh20 (previous revision, new revision, compare).

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

The solution link is not working sir!!!.. Please check it once. Thank you

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

Auto comment: topic has been updated by gyh20 (previous revision, new revision, compare).

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

nice problems, liked the centroid concept!! .... hope to see more like this

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

I used a different approach for C: 1. First I found the tree diameter. 2. Then I rooted the tree at one of the centres (if there are 2) and calculated the subtree sizes. 3. Then for each node of the tree diameter, I calculated the maximum subtree size that would be generated when I remove that node. 4. I found the minima over all these subtree sizes, the node/s which give this minima are the centroids. 5. If there is a unique centroid, I removed any edge and rejoined it. Else, I took a leaf, removed the edge between it and the parent, and joined it to one of the centroids. I don't know why my solution fails at test case 6. https://codeforces.com/contest/1406/submission/92644162 Thanks in advance.

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

    The centroid(s) does not necessarily lie on diameter.

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

      Thanks, Can you please explain me C, I didn't understand the editorial.

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

        If there are two centroids, they are adjacent and divide the tree into two components of size $$$\dfrac{n}{2}$$$ and $$$\dfrac{n}{2} - 1$$$.

        Pick a leaf from the subtree ( not containing the other centroid ) of any one of the centroids and link it with the other.

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

          why are there at most 2 centroids? Also, why do they have to be adjacent? An informal proof will be much appreciated! Thanks in advance.

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

            If you agree with the fact that 2 centroids must be adjacent to each other, then if there exists another centroid it must be adjacent to the previous 2 centroids but that will lead to a cycle. Therefore, there are at the most 2 centroids.

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

              Ah! Very smart! But again, why do the centroids have to be adjacent?

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

                If not, choose any other vertex on the path from one of the centroids to the other, and the size of the largest connected component after cutting it will be smaller than the original ones.

                And that is a contradiction.

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

            you can look up any centroid decomposition tutorials online. these are briefly explained over there.

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

          I get that when two centroids are there we have this property — each centroid has a max of size n/2 component(necessarily the one including the other centroid).IN editorial it is written that x will have max component size of n/2 still after operation. But it can be of n/2-1 also right? n/2-1 would be when x has more than two edges, one to the other centroid and the other edges to the other nodes. I even worked through an example for this. Although max disconnected of x can at most be reduced to n/2-1 and really has only these two choices{n/2,n/2-1}.

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

A few typos in the first line of the solution explanation for problem D. It should be:

Since sequence $$$b$$$ is non-decreasing and sequence $$$c$$$ is non-increasing, we need to find $$$max(c_1, b_n)$$$.

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

I had a different and much simpler approach to B.

Firstly, sort the array from smallest to largest (no absolute value). After the sort, it can be proved that the answer is either a[n-1]*a[n-2]*a[n-3]*a[n-4]*a[n-5], a[n-1]*a[n-2]*a[n-3]*a[1]*a[0], or a[n-1]*a[3]*a[2]*a[1]*a[0]. Take the maximum of these three values as the answer. The logic is pretty self explanatory.

My submission: 92587656

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

    I had a slightly more complicated to code but really easy to understand.

    I took the first 10 numbers and the last 10 numbers of the sorted array(handling the case when $$$1 \le n \le 20$$$). Then I bruteforced through all the combinations of 5 numbers from the 20 numbers. I then took the maximum of all of those products.

    Link to submission 92660785. Please tell me if you don't understand my code because of all of the macros.

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

    I also thought the same idea : 1. Think like this that the maximum answer should always be positive, so this is only possible when all numbers are positive or negative numbers exist even times.

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

    Hey , I also did same ( got AC too) , but my doubt is after sorting isn't the order of values is changed , so how the given i<j<k<l<t will satisfy?

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

      before sorting the five values have some indices. After sorting, those same five values now got new indices. As we are taking the product, the values of indices don't matter. Any five different indices will satisfy that condition.

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

"maxinum component size of x" it should say "maximum component size of x" (for problem C)

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

I have a slightly different solution for E using binary search that might be more intuitive. First, brute force all prime factors which are $$$\leq \sqrt{n}$$$, for $$$n = 1e5$$$, there are only $$$65$$$ such primes, and we can check each exponent for all in ~$$$200$$$ queries(even less if we binary search on the exponent). Then, for the higher primes only one such prime can appear, so we binary search on the rest of the primes with the following algorithm:

Let $$$num$$$ be the amount of numbers left in the set.

Consider some search space of primes $$$[l, r]$$$

Ask B for all primes $$$[l, mid]$$$, subtract the result of the query from $$$num$$$

Ask A 1

If the result of A 1 and $$$num$$$ differ, the last prime is in the range $$$[l, mid]$$$, otherwise it is in the range $$$[mid+1, r]$$$

This part takes at most $$$m + log(m), m = \pi(n)$$$ queries so it easily passes.

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

    After you ask B for all primes in [l,mid], how can you find the right factor if the result of A 1 and num differ?

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

      Cause corresponding to that factor the query A *(that number) will give 1 as the output and we can be sure that it is that number as the largest prime number factor

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

      Harshlyn94's method does work, but you can also continue to binary search that range, and so you don't need to write another check. Its not much of an implementation save, but it is a little easier.

      I found a submission that uses this idea: 92651206

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

I thought that there should be atmost most 2 centroids in a tree is it correct?

If it is how to prove it ? And if it's not then why, I was not able to find an example.

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

    Assume that node x is one of the centroids of the tree.

    Make x the root of the tree

    Here, we denote sz(a) as size of the subtree of a

    According to definition, sz(child of x) ≤ (n / 2). (1)

    We have another observation: The size of the subtree of a node < size of the subtree of its parent (2)

    If there are one centroid => We are done

    Else, let y be another centroid of the tree.

    When we delete y, the subtree that doesn't contain the subtree of y is connected, so its size must ≤ (n / 2) according to definition

    => sz(y) ≥ (n / 2) (3)

    From (1), (2) and (3), sz(y) = (n / 2) and y is a direct child of x

    If there is another node z which is another centroid of the tree (now we have 3 centroids), then sz(y) + sz(z) + 1 (node x itself) = n + 1, and since y and z are directed childs of x, their subtrees don't share any node.

    => The graph has ≥ (n + 1) node (contradiction)

    => There are at most 2 centroids in a tree (Q.E.D)

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

      "**When we delete y, the subtree that doesn't contain the subtree of y is connected, so its size must ≤ (n / 2) according to definition**"

      I don't get this, what is the subtree that doesn't contain the subtree of y ?

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

        The subtree that doesn't contain the subtree of y is the given tree without the subtree of node y.

»
2 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

SpeedForces
GoogleForces
CopyPasteForces

B and C seemed rather standard. I recognized B as an E problem from a recent ABC round. However, I didn't bother to go looking for it and then copy and paste a solution. For D, I googled "how to find centroid of a tree" and "how many centroids are in a tree". The latter gave me

Spoiler

Which basically trivialized the problem.

Nevertheless, A, D, and E seem quite nice. I found this round rather interesting (especially problems D and E).

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

    We are sorry for making problem B.

    But for C, the point of the problem is not to find the centroids, but what to do next. So in my opinion, I don't think C is very standard.

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

Can anyone tell me why my code is giving runtime error on test 1?

https://codeforces.com/contest/1406/submission/92659872

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

    it's because your centroid finding function is not working, centroid vector is empty and consequently indexing empty vector causes runtime error

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

      I know that some values are inserting to the vector, but sometimes this vector is empty. I struggle with fixing this bug. Do you know what exactly is not working in this function?

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

        There might be other problems too but one of the obvious thing is if(n - graf_size[u] > n / 2) this check should be outside loop for(auto v : graf[u]) so that you check condition only when you have calculated actual subtree size for node u.

        Edit : I made some more changes to Centroid function. now it seems to work. correct submission : solution

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

          What a stupid mistake with bracket. Thank you very much for your help.

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

In E I believe you should add $$$\sqrt{m}$$$ to your estimate. You do $$$\sqrt{m} \cdot \sqrt{m} + 1 \cdot \sqrt{m}$$$ and in at most 2 buckets you'll find a prime that divides $$$x$$$, so you need to add $$$2 \cdot \sqrt{m}$$$ for that. And later there is that $$$\log_2(n)$$$ and one for answer, so counting this way we get $$$m + 3\sqrt{m} + \log(n)$$$.

Also I don't understand why the first 3 paragraphs of its tutorial are there, in my opinion they are quite confusing.

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

    I don't understand why we can't find the smallest prime number by using the given method. Shouldn't it be largest prime number which is not possible to find.

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

      We can find all prime divisors this way, editorial is just confusing.

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

Can someone explain this line from the editorial of question E. After finishing asking a group, ask A 1 and check if the return value same as it supposed to be without x.

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

plz explain solution of problem c..

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

First, if all numbers are less than 0, then you should print the product of the five biggest numbers of them. Otherwise, the maximum product must be non-negative. Its false. How about -1 1 2 3 4?

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

    It will only make sense if n > 5.

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

Problem D. Three Sequences Youtube Video Explanation in Hindi. Solution Explanation Youtube Link

If SomeOne is Upsolving Problem D and needed some help in solution explanation in hindi. please watch above video and give feedback to improve quality. Thanks

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

can anyone explain solution of 3rd problem? I can't understand why dfs is used here?Can it be solved without dfs like if we can find out 2 centroids by checking the largest component which is smallest by removing each vertex one by one and than if there are 2 or more centroids we can remove one edge from one centroid and connect to other centroid??

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

    How do you find a centroid without doing dfs?

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

      I think by removing each vertex one by one and than checking for largest component than does not contain removed vertex and out of these components the centroids will be the ones that has minimum size component (obtained after removing those vertex). Please correct me if i am wrong.I can't understand how dfs is applied here to find centroid.It will be of great help if u could provide any source to solve this type of problems

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

        It is well explained in this blog https://codeforces.com/blog/entry/57593

        I did not know this algo before the contest, and implemented an alternative. Just find foreach vertex the maximum size of the subtree of its adjent vertex. Then find among all vertex the one or both with minimum value. 92620542

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

I think the problem C and E is interesting,but problem A is not easy enough to put it on A.It can be B.

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

Can anyone tell me why my code is wrong?(Problem E)

https://codeforces.ml/contest/1406/submission/92640804

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

About centroids. Editorial says "If not, choose any other vertex on the path from x to y and the size of the largest connected component after cutting it will be smaller than x and y". Looks like this is impossible and centroids are always connected. If I am correct, please remove this confusing comment

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

    yeah ... I also think so.

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

    The point of that statement is proving, by contradiction, that "centroids are always connected".

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

I cannot see the Jury's solution for E. It shows "You are not allowed to view the requested page".

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

I think there are some typos in the editorial of problem D:

  • sequence $$$b$$$ is non-decreasing and $$$c$$$ is non-increasing (as in the problem description).

  • and then, it should say $$$\max(c_1, b_n)$$$.

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

About problem E:

I didn't notice that $$$1\le a\le n$$$!

What a pity!I almost made it to the top 20!

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

    emmm, you are sure that you can solve E if you notice $$$1\le a\le n$$$ that time?

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

    Same here. I noticed the constraint after the contest. The solution I submitted during the contest ACed when I added the condition.

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

Auto comment: topic has been updated by tianbu (previous revision, new revision, compare).

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

I can't view pC's solution(submission), does it only happen to my account or is it private ><

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

Though I've lost so many ratings,I enjoy the contset very much.

THX for such a wonderful contest!!!

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

Does anyone have a neat proof that definition of the centroid given in C matches the standard definition of centroid (disconnecting it separates the tree into connected components all <= n/2 in size)?

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

    Let us root the tree at centroid (curren't problem's definition of centroid), and sz(x) be the size of subtree of vertex x, now sz(x) is the smallest possible largest connected component upon deleting a vertex s, now assume sz(x) > (n/2), now the largest connected component upon deleting x would be max(n-sz(x), max(sz(y1))) where y1 are x's children, sz(y1)<sz(x) and n-sz(x) < n/2 (as sz(x) > n/2), so either way the sz(x) would not be the smallest possible largest connected component and hence s is not the centroid, hence a contradiction. We can extend this to say that both the centroids should by adjacent, with the equation sz(x) + sz(y) = n (where y is another centroid)

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

      Excellent. Although hard to wrap my mind around "We can extend this to say both centroids must be adjacent". Could you explain a bit more? Thanks!

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

        Tree is still rooted at s, there is some other centroid out there y, let it's children be yi, now the largest component upon deleting y is max(sz(yi),n-sz(y)), now sz(yi) < sz(x) so if this also centroid, then n-sz(y) = sz(x), as both produce the smallest possible largest component, hence sz(x) + sz(y) = n, but sz(x)<=n/2, and sz(y)<=sz(x) as upon deleting the root, the largest component we get itself is sz(x), the only scenario where the above eqns can be satisfied is sz(x) = sz(y) = n/2 and y is child of s, but if y!=x then sum of subtree's of child itself becomes n, so the only way out is y equals x. So there can be atmost 2 centroids, both adjacent.

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

Can someone find me a video editorial for problem C. Thanks in advance!

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

It's easy to see that the size of y's subtree must be exactly n/2. After cutting and linking, the maxinum component size of y becomes n/2+1 while the maxinum component size of x is still n/2.

I think they exchanged x and y in tutorial of problem C if x and y are two centroids and x is y's father, then initially their sub tree size would be n/2 and n/2.this also tells that if n is odd then only 1 centroid exists. Now if we take leaf of y and add it to x, x sub tree size would be n/2 + 1 and y's would be n/2 — 1, but in editorial they have exhanged x and y i think !!

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

Can you anyone help to identify a failing test case for the below code for problem B ?

https://ideone.com/D5Wq6z

Approach : Seperate integers less than 0 (l0) and greater than equal 0 (g0). Sort both and reverse g0. Try all possible combinations in (l0,g0) that add upto 5 numbers i.e, (0,5),(1,4),etc. wherever the size allows. Take max of their products.

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

can anyone help ,where my logic get wrong for B. Maximum Product https://codeforces.com/contest/1406/submission/92678443

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

In Maximum Product(B) it is written that i<j<k<l<t .. then why sorting ? It will definitely change the order.

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

    If i>j,then you can see j as i,and i as j.

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

      It doesn't makes any sense to me

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

        i <j <k <l <t just means that you have to pick 5 numbers(from distinct indices). Moreover, you just want to find the max. product , so you need not worry about "indices".

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

    Does taking product require order of numbers. That's why. just ignore that relation(i<j<k<l<t)

    :)

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

Can someone tell what is wrong in my solution for problem B. It is giving me WA on test 2 for the 143rd input.Thanks in advance.

https://codeforces.com/contest/1406/submission/92649674

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

    consider the test case : -1 -2 -3 -4 -5 -6 your code gives -720 but the answer is -120.

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

There is another solution for problem B with dynamic programming. That approach seems not to be the easiest one, but I would like to share it just in case it may be interesting for someone.

Submission: 92600395.

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

will DP work for problem B?

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

    Yes, dp solution is possible. But, div 2 — B is not made for this. I saw i<j<k<l<t and concluded sorting won't work (This is wrong). I then use dp (as expected TLE). Sad :(

    t = int(input())
    for _ in range(t):
    	n = int(input())
    	arr = list(map(int, input().strip().split()))
    	
    	dp1 = [[-1e25 for i in range(n)] for j in range(6)]
    	dp2 = [[1e25 for i in range(n)] for j in range(6)]
    	
    	dp1[1][0] = arr[0]
    	dp2[1][0] = arr[0]
    	for i in range(1,n):
    		dp1[1][i] = max(arr[i], dp1[1][i-1])
    		dp2[1][i] = min(arr[i], dp2[1][i-1])
    	
    	for i in range(2,6):
    		for j in range(i-1,n):
    			for k in range(i-2,j):
    				dp1[i][j] = max(dp1[i][j], dp1[i][j-1],dp1[i-1][k]*arr[j], dp2[i-1][k]*arr[j])
    				dp2[i][j] = min(dp2[i][j], dp2[i][j-1],dp2[i-1][k]*arr[j], dp1[i-1][k]*arr[j])
    	
    	ans = -1e20
    	for i in range(4,n):
    		ans = max(ans, dp1[5][i])
    	
    	print(ans)
    
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you tell me what's wrong with this DP solution, submission link

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

        I guess your initializations are wrong. For pos dp, each element should be initialized to number less than min negative product possible (-1e15 since each element could be up to -1e3). A similar analogy for neg dp.

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

Nice round! Thanks~

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

Plag Checker is dead !

[Proof] 92607281 92620817

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

Generalisation of problem B has already been asked quite recently on atcoder
Here's the link: atcoder ABC 173 E

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

In Problem B, I am getting wrong answer on test 2, more specifically on 143rd input — answer is not matching . Can anyone please point me out where I am going wrong? Link to submission — https://codeforces.com/contest/1406/submission/92680690

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

    I am also getting wrong answer on the same input. Still not able to figure it out.

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

      As kennethyonghw has told, We are making the same mistake. When your product in all cases turns out to be negative, then we need to minimize it, on contrary following line maximizes it: prod=pos[i-1]*neg[4-i];

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

    Consider the test case: -6 -5 -4 -3 -2 -1. Your code gives -720 but the answer should be -120.

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

      Thanks kennethyonghw for pointing out that bug, I made a few changes and it got accepted. Thanks a lot.

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

In task C , is it necessary for x to be y's father to cut a leaf from y and attach it to x?I am not able to understand this .

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

My solution for C :

If there are two centroids, I pick one of the centroids and disconnect one of its non-centroid subtree and connect that subtree to the other centroid. Will this always work?

My submission : 92632074

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

Isn't B's editorial wrong?

Consider input as : 1 1 1 1 -1

All numbers are not less than 0 yet maximum product is negative.

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

Does anyone knows any good tutorial/blog for finding the centroid of a tree?

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

    The answer you seek is one google search away

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

      I am only finding about centroid decompostion(other than 1 CF blog). Is it the same ?

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

        This blog is quite nice. Very short and has interesting problems. Try to solve all. You will learn much quicker via solving problems than just reading theory.

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

Hi, in 1406B — Maximum Product, after sorting in descending order, i think it is feasible to check only 3 values that are 5 entries from top and none from bottom, 3 from top and 2 from bottom, 1 from top and 4 from bottom and then simply find their max :)

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

Am I the only one who tried solving D using range updates and range maximum queries? I feel stupid.

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

For problem D, how to prove that this arrangement will be optimal and gives us the least possible max(c1,bn) ? For example say d = a(i) — a(i-1), when d > 0, b(i) = b(i-1) + y(aribitary y), c(i) = c(i-1) + d — y(arbitary y), how to prove that in the optimal solution y = 0 ?

isaf27 gyh20 csani

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

    For every i>1, you just want to minimize b(i) and maximize c(i), when y=0, this is the optimal.

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

      Thanks, but in the editorial, shouldn't it be a(r+1)-a(r) instead of a(r) — a(r-1) ? both a(r) and a(r-1) change by x

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

        will fix that soon,thanks.

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

In a tree, the center of the diameter and the centroid are different points, right? Please give me an example, I am unable to come up with one... Thanks in advance

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    N = 7
    
    Edges:
    1 2
    2 3
    3 4
    4 5
    4 6
    4 7
    
    Center of diameter: 3
    Centroid: 4
    
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it always that tree can have atmost two centroids? If so, then why not more than 2? Please help, just heard about centriod in this contest and am confused even after reading other blogs.. can someone explain centroid in simple terms. :(

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

please someone explain this line written in editorial of problem C, Proof: It's easy to see that the size of y's subtree must be exactly n/2

why it's n/2 always??

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

problem b is interesting because it has many solutions, there is a very easy way to understand that is to break down 6 cases :

- - - - -
- - - - +
- - - + +
- - + + +
- + + + +
+ + + + +
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, For 1406B — Maximum Product : I believe we can answer the question by checking 3 values after sorting. The first is the product of the 5 largest numbers, the second the product of the 2 least and 3 largest numbers and finally the third will be the product of the 4 least and the 1 largest number.

The solution will be the maximum of these 3 values. The solution tries to keep the answer +ve and that can be only done by selecting an even number of -ve numbers(least numbers). If there are no -ve numbers or all are -ve then the solution will simply contain the product of the largest 5 numbers[first value] which will be the max possible product.

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

For question 3

can anyone give me an example tree with more than 2 centroids? my assert(n<=2) statement is failing.

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

Video editorial for Problem E : Deleting Numbers for anyone interested : https://www.youtube.com/watch?v=49GhzA5eWyE . Note : This video is a discussion and not take this as a tutorial .

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

Can someone please tell me where my solution is failing for problem C?

Link to my submission : https://codeforces.com/contest/1406/submission/92731735

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

Can this solution be used for any k (which is 5) in the problem B? 92677568 , why not?

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

for problem C, how a tree can contain no more than 2 centroids?

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

I solved [problem:1460E] in another way: "B i" for every prime in (n/2, n], then "A 1", check is your cnt equal to this: if not: "A i" == 1 for every prime in (n/2, n] -> ans *= i; else take (n/4, n/2] ...

And in the end check primes from (1, n / ans)

I mention that primes in (1, n/2] > (n/2, n], that's why you won't have more than enough queries

But the author's solution with sqrt-decomposition is better and easier — Sorry for the waste of time ))) Wanted to let you know about other solution :)

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

I think the total number of operations for E is around $$$M + \sqrt{M} \cdot log(M) + log(M)$$$

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

Can problem D find legal arrays of $$$b$$$ and $$$c$$$? upd:Oh, yes, it can be done.

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

In Problem C in the case of 2 centroids, instead of finding a leaf in a centroid and attaching to the other centroid I found an edge from a centroid other than the one joining the two centroids and attached it to the other centroid. My solution passed system tests. Is it right or is there any test case for which my solution fails?

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

For Problem D, i am not able to see why x should be (a1+K)/2.Can someone please explain?

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

PROBLEM B

method not working

def partition(arr, low, high): i = (low-1)
pivot = abs(arr[high])
for j in range(low, high):

if abs(arr[j]) <= pivot:


        i = i+1
        arr[i], arr[j] = arr[j], arr[i]

arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)

def quickSort(arr, low, high): if len(arr) == 1: return arr if low < high:

pi = partition(arr, low, high)

    quickSort(arr, low, pi-1)
    quickSort(arr, pi+1, high)

if name == "__main__": for i in range(int(input())): l2 = [] n = int(input()) l1 = list(map(int,input().split())) quickSort(l1,0,n-1) #print(l1) sm = 1 for i in range(len(l1)-5,len(l1)): l2.append(l1[i]) sm *= l1[i]

if sm >= 0:
        print(sm)
    else:
        smm = sm
        for i in range(0,5):
            for j in range(n-6,-1,-1):
                sm = 1
                for x in range(0,i):
                    sm *= l2[x]
                sm *= l1[j]
                for z in range(i+1,5):
                    sm *= l2[z]
                if sm >= 0:
                    smm  = max(sm,smm)

        print(smm)

https://codeforces.com/contest/1406/submission/92847774 test 2 fails ,It will be great if someone help me understand what have i done wrong here or what am i missing.Thank you in advance.

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

problem B's tutotial: while the maxinum component size of x is still $$$\frac{n}{2}$$$.

I think it should be: while the maxinum component size of x is $$$\frac{n}{2}$$$ or $$$\frac{n}{2}-1$$$.

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

    Since x is parent of y, won't maximum component size of x become n/2 -1 always? How will it be n/2?

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

      If you link the leaf with x, that's n/2 — 1. but if you cut a leaf from the subtree of y that does not contain x and don’t link the leaf with x,the maximum component size of x will it be n/2

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

I am not sure I completely understand problem D. I have been trying for past 3 days but the queries part is not clear to me and the solutions I refer to also are not understandable Can someone please explain the queries part, how are we updating the elements in the range l..r or if not, then why not? I understood why we need only the two adjacent differences in every query but what about updating the elements? Please help me.I would appreciate it.

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

Can someone please explain how the updates are being made in editorial's solution? I looked at many codes but I am unable to understand anything from them? Please help me!!! I understood the rest of the solution.

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

can anyone explain the editorial of problem A. and why i got runtime error herehttps://codeforces.com/contest/1406/submission/93185539

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

;

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

Is problem A wrong? Why not split the set (0 2 1 5 0 1) into (0 0 2 5) and (1 1) to have mex of 1 and 0 respectively?

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

Anyone can explain the algorithm to calculate the centroids of problem C.I don't get that. Thanks in advance.