gop2024's blog

By gop2024, history, 5 years ago, translation, In English

(Idea of the problem Div2A — ScreaMood)

(Developer of the problem Div2A — gop2024)

Tutorial is loading...

Code

(Idea of the problem Div2B — kirillbogatiy)

(Developer of the problem Div2B — gop2024)

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 — gop2024)

(Developer of the problem Div1B — PeregudovSergey)

Tutorial is loading...

Code

(Idea of the problem Div1C — ----------)

(Developer of the problem Div1C — ----------)

Tutorial is loading...

Code

(Idea of the problem Div1D — gop2024)

(Developers of the problem Div1D — ---------- и gop2024)

Tutorial is loading...

Code

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

(Idea of the problem Div1E — gop2024)

(Developer of the problem Div1E — TheWayISteppedOutTheCar)

Tutorial is loading...

Code

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

| Write comment?
»
5 years 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

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

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

    I support the question.

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

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

    Correct answer is 1019. Your code outputs 1018.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    I am struggling to even see the correctness. Can you please give me some details?

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

gop2024 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.

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

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

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

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

        Use segment tree to count the maximum suffix sum.

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

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      5 years 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.

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

»
5 years 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;

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

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

What is CHT?

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

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

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

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

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

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

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

»
5 years 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://mirror.codeforces.com/contest/1180/submission/55891316

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

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

Nice editorial.

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

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

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

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

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

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

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

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

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

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

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

»
5 years 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://mirror.codeforces.com/contest/1180/submission/56012176 AC submission: https://mirror.codeforces.com/contest/1180/submission/56012511

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

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

»
5 years 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://mirror.codeforces.com/contest/1179/submission/56058316

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

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

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

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

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

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

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

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

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

In div1D, what is the meaning of the sum A, B and C? Thanks in advance

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

in div2C i was getting MLE bcz i was using deque but same logic using vector works fine enough can anyone plz explain why this is so

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

Well i spent almost 2 hours on problem B(Nick and Array). Nice and tricky problem anyway!!!