FelixMP's blog

CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) Editorial
By FelixMP, history, 3 years ago, In English

1656A - Good Pairs

Author: FelixMP Preparator: FelixMP

Solution
Code

1656B - Subtract Operation

Author: FelixMP Preparator: xpov1LL

Solution
Code

1656C - Make Equal With Mod

Author: FelixMP Preparator: FelixMP

Solution
Code

1656D - K-good

Author: FelixMP Preparator: FelixMP

Solution
Code

1656E - Equal Tree Sums

Author: FelixMP Preparator: FelixMP

Solution
Code

1656F - Parametric MST

Author: FelixMP Preparator: FelixMP

Solution
Code

1656G - Cycle Palindrome

Author: FelixMP Preparator: FelixMP

Solution
Code

1656H - Equal LCM Subsets

Author: FelixMP Preparator: FelixMP

Solution
Code

1656I - Neighbour Ordering

Author: FelixMP Preparator: FelixMP

Solution
Code
  • Vote: I like it
  • +82
  • Vote: I do not like it

Comments Comments (98)
| Write comment?
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Congratulations to winners!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

What a contest! (☉_☉)

→ Reply
»
3 years ago, # |
  Vote: I like it +171 Vote: I do not like it

MathForces

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

used unordered_set for B, got TLE.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    unordered_set works $$$O(n^2)$$$ in STL. Use set

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

      What I see from the docs is that they mention linear time in the worst case and constant time on average. They also mention that it is faster than set as the elements are not stored in sorted manner.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it -80 Vote: I do not like it

        The thing with unordered_set is that it relativly slowly adds new elements. Yes, it is guaranteed that it will run in constant time, but no one said that this constant will be less than logarithm =)

        Here is your submission with set instead of unordered_set : https://codeforces.net/contest/1656/submission/150817878

        UPD: It doesn't work! (However, if you still want use unordered_set you can rehash (resize) it before using. This is similar to what vector::reserve() does, (but impacts more). __ Here is your sumbission with us.rehash(n) after creation of us: https://codeforces.net/contest/1656/submission/150818489 It runs in just 78ms __ Conclusion: be careful with std::unordered_set and use rehash())

        Conclusion: don't use std::unordered_set

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it +79 Vote: I do not like it

          That is completely incorrect! The hashing used by std::unordered_set and std::unordered_map is fundamentally broken, and you can easily create O(n^2) blow-ups, see this blog. Trying to use .rehash, .max_load_factor or .reserve etc... will not fix this. To fix it, you need to create your own custom hash.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +15 Vote: I do not like it

            Wow, that's mindblowing! I've always used std::unordered_map with rehashing, it's never been a problem, and I've never even thought about these types of blow-ups. Thanks a lot for pointing this out!

            → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for the fast editorial.

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Proof for E?

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

    For each edge assign a positive end to one node and a negative end to the other. The positive node has values equal to +degree(node) and the negative node has a value equal to -degree(node). Now u delete one node. If the node was positive then all the disconnected regions are unaffected except by 1 edge. We know the sum of values of nodes that are contributed by the edges which are not deleted is 0. So whatever sum the disconnected regions have it will be either -1 if the deleted node was positive or +1 if deleted node is negative.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

I've also added a new feature to view all the hacks and small testcases for any CF problem. However, for this contest, only problem D has hack testcases of length less than 255.

View hacks for D: K-Good

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

→ Reply
»
3 years ago, # |
  Vote: I like it +136 Vote: I do not like it

The editorial to E reads to me like some kind of magic, where you must hope a higher power whispers the right construction into your ears. There's a straightforward way to reach this solution without guessing some construction.

Root the tree at node 1. Let $$$S_u$$$ be the subtree sum for vertex $$$u$$$ and $$$p_u$$$ be the parent of $$$u$$$. Consider an arbitrary vertex $$$u \neq 1$$$ and it's children, $$$c_1, c_2, \cdots c_k$$$. Then, if you remove vertex $$$u$$$, it is clear that:

$$$ S_{c_1} = S_{c_2} = \cdots = S_{c_k} = S_1 - S_u $$$

The right most term is the sum of the rest of the tree, not counting $$$u$$$ and it's children. From this, we find that for any $$$u$$$, $$$S_u + S_{p_u} = S_1$$$. This is how the idea of bicoloring becomes clear — the sum of $$$u$$$ and $$$p_{p_u}$$$ must be the same by this identity. Now what should be the sum for each colour?. Neither can be 0 since then the leaves might have value 0. So try $$$S_1 = 0$$$, and the sums of each colour being 1 and -1. Through this, you reach the same conclusion as the editorial.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    A straightforward solution of E for those who are bad in finding explicit constructions:

    1. Let the weight in the root be $$$W$$$ and sum in each of the root’s subtrees be $$$S$$$

    2. Weight of every node can be written as $$$aW+bS$$$

    3. We can find $$$a$$$ and $$$b$$$ for every node by running a dfs, just keep track of (1) sum in the current subtree and (2) sum in the nodes outside of it

    4. Now we can effectively compute weight of each node for fixed $$$W$$$ and $$$S$$$

    5. At this point, just brute-force different combinations of $$$W$$$ and $$$S$$$ before you find the one for which all the weights are non-zero and smaller than $$$10^5$$$

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

    Thanks a lot. After reading the tutorial, i thought that it's impossible for me to transform the problem into the conclusion, too abstract for me. Your comment is very helpful for me to fully understand this problem.

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

    this is how the idea of bicoloring becomes clear

    Could you elaborate a bit more on why should we use bicoloring here ? and assign weights according to degree and color for each node

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it -46 Vote: I do not like it
Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Why don't you put code in spoiler, and why are you using float

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

      Sorry I didn't know about that. I will keep this in mind next time. Actually I just use the boiler plate of earlier question I was doing using float variable. So that's why.

      Thanks for your suggestion I just changed float to int. It worked just confused ewhy it give wrong result in float?.

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

        You should edit your comment and add code to a spoiler. It hinders scrolling down for others.

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

        Float and int are the same number of bytes, but a float only uses 23 bits to store the precise value of the number (and the other 8 bits to store the exponent/magnitude + 1 bit for the sign), so for large numbers, a float can't store the exact value. For this problem, the values of $$$k$$$ are large enough to need 30 bits to be stored. So tl;dr, float causes precision issues here.

        → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I don't get why in D we consider sum of remainders as $$$ 1 + 2 + ... + k$$$, shouldn't it be $$$0 + 1 + 2 + ... + k - 1$$$?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    positive integers

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

      ah, indeed

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

      Still 0, 1, ... ,k-1 are k distinct remainders where k is a positive number (k > 0 ) so why shouldn't the remainders be 0, 1, ..., k-1 ?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        $$$0 + ... + k - 1 \equiv 1 + ... + k$$$, if that's what you're saying. I don't really understand your comment to be honest.

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

          No I am not saying this. n will be sum of k positive integers.

          Say n = 6 then 6 = 1 + 2 + 3 then remainders are (0, 1, 2) hence three distinct remainders are 0, 1, 2...so sum of remainders is (0 + 1 + k — 1), in this case k = 3.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            To eliminate the condition for positive integers, instead of 0 they are assuming the remainder is k. In your case instead of 0, put 3 there, as any way you are going to add some positive multiple of 3 to 0.

            → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How do you make checker for D?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Unless I’m misunderstanding the question, it seems like writing the checker should be pretty straightforward: the authors specify conditions for n to be k-good on the first few lines of the editorial, so you can just check if these conditions are satisfied (or, if the program prints -1, check if N was a power of two).

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

      Oh, you're right. I misunderstood the editorial. My bad.

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +18 Vote: I do not like it

    I think checking the following conditions would be fine-

    • $$$ (2 \cdot n) \% k = 0 $$$

    • $$$ \dfrac{2 \cdot n}{k} + 1 - k $$$ is positive and even.

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

    Just check:

    • $$$\frac{k*(k-1)}{2}$$$ $$$\%$$$ $$$k$$$ = $$$n$$$$$$\%$$$$$$k$$$
    • $$$\frac{k*(k+1)}{2}$$$ $$$\le$$$ $$$n$$$
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why this failed for B https://codeforces.net/contest/1656/submission/150765827

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for question C, editorial says that if 1 is not present in the array then the answer will always be YES, but what if array contains only two elements 7,8 then what should be the answer??

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

    The author says that if we have elements with difference 1 along with 1 in the array, such as 1,7,8(eg) we have answer no. But in the case said by you, we get answer yes, as we have no 1 in array as well as no 0. This has been said in the first line of editorial, if there is no 1 in array answer is always yes.

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

    yes because: the first operation will be: 8 mod 8 = 0 7 mod 8 = 7 the second operation will be: 0 mod 7 = 0 7 mod 7 = 0

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me in a simpler language the solution to problem D? I was able to figure out, that for odd n, a valid answer is always 2, and if n is a power of 2, answer is -1. But I was not able to figure out for even n which are not powers of 2. Can someone help?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +81 Vote: I do not like it

I: It is easy to see that the graph doesn't satisfy the condition if it contains $$$K_4$$$ or $$$K_{2,3}$$$ as a minor, and graphs that don't contain those minor graphs are called outerplanar. It is also clear that outerplanar graphs have correct neighbor ordering, so the whole problem is almost equivalent to checking if the graph is outerplanar.

→ Reply
»
3 years ago, # |
  Vote: I like it +61 Vote: I do not like it

I used another solution to pass problem F, the idea is as follows:

First, prove (or write brute force to check) that $$$f(t)$$$ is a convex function.

Then we devise the following $$$\mathcal O(n)$$$ algorithm to calculate $$$f(t)$$$ given $$$t$$$:

Using Prim's algorithm, in each step, we want to find the unconnected node that is the cheapest to connect to, which we can see is either the one with the largest or the smallest value of $$$a_i$$$ in the unconnected nodes. We also see that the edge will come out from the connected set from either the one with the largest or the smallest value of $$$a_i$$$ among them. Therefore, we only have 4 possible cases to handle for each step and so we can construct the MST and its weight in $$$\mathcal O(n)$$$.

Now we can directly do a binary search for the optimal value of $$$t$$$, and do some special handling for the INF cases.

Time complexity: $$$\mathcal O(n \lg n + n \lg a_i)$$$

Implementation:
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B "since the previous substractions are cancelled", what does this sentence mean ?

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

    Let's take four numbers a,b,c,d
    {a, b, c, d} -> {a-b, c-b, d-b} -> {a-b-c+b, d-b-c+b} = {a-c, d-c}

    You can see -b which was there in all the terms gets cancelled.
    I have solved a similar observation based problem few days back: https://atcoder.jp/contests/arc135/tasks/arc135_c

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Another way to think is that if there exists a pair that has a difference k, then it's always possible to do subtractions in some order because the relative difference between them is not going to change.

      → Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain D in simple terms?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was my solution right? It looks not right at all but it has been passed during the system test. link：https://codeforces.net/contest/1656/submission/150790452

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +58 Vote: I do not like it

Problem I can be analyzed somewhat simply using SPQR trees. (Some motivation: at a glance, the idea of ordering the edges incident to each vertex and looking at cycles is very reminiscent of picking a planar embedding of the graph. Alternatively, we can notice that 3 parallel nontrivial vertex-disjoint paths can get us into trouble because they form 3 cycles oriented different ways, so we are motivated to look at triconnectivity.)

Note that, similar to planar embeddings, if there exists a good neighbor ordering of the whole graph, there exists a good neighbor ordering of any graph minor (a subgraph formed by deleting vertices, deleting edges, or contracting paths into edges). This is straightforward to construct, we can make path contractions preserve the ordering by inserting the new edge into the orderings by the locations of its starting and ending edge.

Let's consider a single biconnected component at a time. An SPQR tree consists of the triconnected components of a graph, where each SPQR tree edge represents a 2-vertex cut of the graph, and each SPQR node represents a triconnected component with each adjacent triconnected component compressed into a virtual edge.

Consider a particular SPQR node. Note that each virtual edge is "spanned" by at least one real path in the adjacent component, so the triconnected component is a graph minor. Thus, we can restrict any global good neighbor ordering to a good neighbor ordering of this triconnected component.

Additionally, if the adjacent component is nontrivial (more than a single real edge), then there is a spanning path of length at least 2, which induces a "directionality" to the virtual edge: when going from top to bottom, we are forced to have either $$$v_1 <_{v_2} v_3$$$ or vice versa. This suggests that we should actually replace each nontrivial virtual edge with a path of length 2. Indeed, if we find a good neighbor ordering for each triconnected component with virtual edges replaced by paths of length 2, then we can uniquely glue the triconnected components back together into a good neighbor ordering of the whole graph, using the neighbor ordering of each virtual edge's midpoint to decide whether to reverse each component's ordering or not.

Hence, there is a global good neighbor ordering if and only if there is a good neighbor ordering of each triconnected component, with virtual edges replaced by paths of length 2.

Now, all that remains is to analyze each type of triconnected component (S, P, and R).

S nodes (cycles) are straightforward to order: we can either direction of the cycle, and order each node's predecessor before its successor.

P nodes (parallel edges) require a little analysis. We can check that a P node with at least 3 virtual edges is necessarily bad (2 vertices with 3 nontrivial vertex-disjoint paths), since the "middle" path cannot satisfy both the cycle with the earlier one or the later one. In a P node with 2 virtual edges and 1 real edge, the real edge must be the middle one to prevent this issue.

R nodes each contain a $$$K_4$$$ as a graph minor. It is simple to verify that there is no good neighbor ordering of a $$$K_4$$$, so R nodes do not have good neighbor orderings.

To summarize, the SPQR tree of the graph must contain only S nodes and P nodes with 2 virtual edges and 1 real edge. Such graphs look like several cycles glued together on edges, forming a tree of cycles (kind of like a cactus, but glued at edges not vertices). If we walk along the exterior, we can find the Hamiltonian path as described in the editorial.

Here is a solution implementing this idea, using a (work-in-progress) linear time SPQR tree template. 150839781 We could also write a simpler implementation by just using the SPQR template to identify the Hamiltonian cycles, and then sorting the edges like the editorial.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got TLE in B (fail system test) because I use unordered_set in my program /(ㄒoㄒ)/~~. I couldn't believe it!

→ Reply
»
3 years ago, # |
  Vote: I like it +88 Vote: I do not like it

ShaBi! TaMenDouShi ShaBi A!

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

TheoryForces.

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

WeakPretestForces

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain this approach 150742723

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

    see acc to question we need to write

    n=(a0*k)+(a1*k+1)+....+(a(k-1)+(k-1)),where a0>=1 while ai>=0 for all i>=1.

    Now if write a0 as 1+a00 then n=(k+a00k)+(a1*k+1)+....+(a(k-1)+(k-1)),

    which reudces to n=k*(1+a00+a1+a2+...a(k-1))+k*(k-1)/2

    whch can be rewritten as n=k*C+k*(k+1)/2 where C=a00+a1+..a(k-1)

    now again simplifying n=k*(k+2*c+1)/2

    i.e. n has to expressed as odd*even/2 or even*odd/2 [if first term is even the second term is odd or vice versa]

    k=min(even,odd).

    Thats why in the code he first take out all the powers of 2 and then the left out part is odd and then print the min of them if the min is 1 answer will be -1 and he mulitply extra 2 in final answer becuase n=even*odd/2 or 2*n=even*odd.

    link to my code (in case u need it):-150843839

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

      Why do we need min(even,odd)

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

      But in Odd part, why are we taking the maximum ODD factor of n, say n=3*5*7*(2^p) , then odd could have been 3 also right, instead of 3*5*7. Can someone clarify.

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

        yes u can but their is no need to do so ,because u r checking odd only if u fail in 2^(x+1) and the reason why u fail in 2^(x+1) is that 2^(x+1)>sqrt(n) which means odd<sqrt(n) and hence this odd will be small enough to be considered.The problem in considering more smaller odds is that u need to do prime factorisation which will give TLE as n<=1e18.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to proof the E？

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

    If you have read the editorial of E, You would see this :

    Consider removing one vertex u. In each subtree, for each edge not incident with u, +1 will be added for one of the endpoints and −1 for the other endpoint, so the total contribution is 0. For the one edge in each subtree incident with u, the contribution will be +1 or −1 depending on the color of u. So the sums of the subtrees will all be equal to +1 or −1.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    see this -LINK

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem D I can't understand this words "Note that, if k is even, the second condition is n≡k2(modk),". Can anybody tell me why is it so, please ?

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

    originally it was n%k = (k*(k+1)/2)%k now we can rewrite this as

    n%k= ((k/2)%k*(k+1)%k)%k future simplifying

    n%k= ((k/2)%k*1)%k

    n%k=(k/2)%k.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be great for beginners like me if someone who solved E during contest (or even after it but without the help of ediotrial) can share their thought process.I got the solution after reading the editorial but i m still confused how to think and reach to this solution on your own.If anyone has some other solution please share.

Thanks in advance.

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

    You can think about it like this. Root the tree at $$$1$$$, and then consider any node $$$u$$$. When we take away $$$u$$$, we are left with $$$u$$$'s children's subtrees, and the rest of the tree above $$$u$$$. Let's call the sum of the whole tree $$$T$$$, the sum of any of $$$u$$$'s children's subtrees $$$m$$$ (note that $$$m$$$ is the same for all of $$$u$$$'s subtrees), $$$u$$$'s value $$$L$$$, and the count of $$$u$$$'s children $$$c$$$.

    Because the component above $$$u$$$ must have the same sum as $$$m$$$, it must be the case that $$$T - (c \cdot m + L) = m$$$. Solving for $$$L$$$, we find that $$$L = T - (c + 1) \cdot m$$$. Notice that $$$c + 1$$$ is the degree of $$$u$$$. If we try to let $$$T = 0$$$ and set $$$m$$$ = 1 for the bottom-most leaves, we find that the weights of any $$$u$$$ where $$$u \ge 2$$$ alternates between $$$c + 1$$$ and $$$-c - 1$$$. The root is the only exception, since setting it equal to either of those will make the $$$|T| > 0$$$. The root's value $$$R$$$ must satisfy $$$R + \sum_{u \ge 2} u = 0$$$, which is $$$-\sum_{u \ge 2} u$$$.

    It is true that none of these nodes' values ever reach $$$0$$$ if we set $$$T = 0$$$ and $$$|m| = 1$$$. For any non-leaf $$$u \ge 2$$$, $$$|\pm (c + 1) \cdot m| > 0$$$ (for any leaf it is $$$\pm 1$$$). Since the root has at least $$$1$$$ subtree, its sum, being the negative of the sum of all of its subtrees, is not $$$0$$$.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I dont like that explanation for E because it doesnt show ideas that leads to the solution. For me this idea the best to explain what is happening:

See on graph and assume that V vertex will be removed. Obviously for every edge we would +1 and -1 incident vertex, but there is a problem: we would remove incident to V edge and sum cannot be 0. We would swap +1 and -1 on some edges. That idea leads to applying graph coloring.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    That's my issue with most editorials, they show the solution but not the "path" or thought process that can lead to that solution

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In editorial of D, What is this architecture-specific function? I could not find it on goolge

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

    In c++ you have __builtin_ctz(x) which counts how many times 2 divides x.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Love problems like C

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

    why this code is failing for problem C 150995742

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

      checked your code:

      if(v[i] == 1)
    	        check_one = true;

      should be put in 

      for(int i=0;i<n;i++)

      rather than

      for(int i=1;i<n;i++)

      which is in yours

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In editorial of D: "all odd candidates of k must be odd divisors of n ". Explain this please

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain F a little bit more? I don't get where $$$-t^2$$$ went? 

if(a[n-1]*(n-2) + tsum < 0 || a[0]*(n-2) + tsum > 0)

Why does this condition checks if it goes to infinity?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this code is failing 150995742 for problem C. I've used same approach as in tutorial, but not able to figure out mistake inside for loop.

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

What was the motivation behind the $$$4 \cdot 10^{36}$$$ constraint for H?

I guess people could use some highly-optimized prime factorization to factorize everything in $$$O(nU^3)$$$ or something rather than use the gcd trick to get "prime" factors in $$$O(n^2U)$$$, where by "prime" I mean, for example, 6 is not prime, but if everything in the input which is divisible by either 2 or 3 is also divisible by 6, then 6 can be treated as prime for the purpose of the problem.

But still, surprising to see such a large constraint. I think it is the first time I have seen a problem where int128 is required just to read the input.

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

    If constraints were only up to $$$10^{18}$$$, all numbers could be factorized using the following strategy: first, take out all small ($$$\leq 10^6$$$) prime factors, and then each number can have at most $$$2$$$ big prime factors, which if they appear separate then they can be found by calculating gcd with al other numbers, and if they appear together then product of the two factors can be considered as a prime as you said.

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

      Wait, so using the gcd method to split apart the two big prime factors was not intended? In my solution (151180177), I used it to factor all of the numbers in $$$O(n^2U\log n)$$$. Maybe the constraints should have been $$$8 \cdot 10^{72}$$$ :)

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

        Why would doubling $$$U$$$ prevent this solution?

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

          It wouldn't, I'm just joking that they made unconventional constraints requiring int128 to read the input, just to prevent a specific kind of unintended solution, but actually they didn't prevent the solution.

          Also on looking at my solution a second time, I think it's also $$$O(n^2U)$$$, I don't remember where the $$$\log n$$$ came from.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            :O i see

            although yeah 1e18 can be factored quickly enough to pass, so 1e36 was necessary

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why problom I has rating only 1800?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How does one develop intuition for a problem like D ? I was able to solve the problem till the part where we had to check for $$$k_1$$$, but I got stuck after that. How did you guys figure out that we're supposed to consider a number $$$k_2 = \frac{2n}{k_1}$$$ and that it would give the correct answer? Some insight as to how to get these ideas naturally would be really helpful.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    We did not magically construct that number, we were, in fact, looking for it.

    We know that $$$n$$$ is $$$k$$$-good iff

    • $$$n \geq \frac{k(k + 1)}{2}$$$
    • $$$n \equiv \frac{k(k + 1)}{2}$$$

    (The editorial skips this segment). Suppose $$$k$$$ is odd. We have

    $$$n \equiv k*\frac{(k + 1)}{2} \Rightarrow n \equiv 0 $$$

    Hence, any odd divisor of n satisfies the second condition. What is the best candidate to satisfy the first condition? Answer: The smallest odd divisor of $n$.

    However, finding the smallest odd divisor of $$$n$$$ is not a trivial task (in fact, prime detection would follow as a consequence of it, since the smallest odd divisor of a prime is the number itself). Of course, for this problem, when we talk about divisors, we mean numbers greater than 1.

    So now, we have a correct but inefficient algorithm to find the answer when $$$n$$$ has at least one odd divisor. Since we are unable to progress further, let's move on to the second segment, i.e, $$$k$$$ is even.

    For even $$$k$$$, the editorial does a good job of explaining that all valid candidates would be a divisor of $$$2n$$$, but not a divisor of $$$n$$$.

    What does it look like visually? Write $$$n = 2^x * pod$$$ where $$$pod$$$ is the product of odd divisors of $$$n$$$.

    The smallest candidate is naturally $$$k = 2*2^x$$$. (Note that the first 2 came from the left half of $$$(2)n$$$, and $$$2^x$$$ came from $$$n$$$. If this candidate satisfies condition 1, we are done. Otherwise, no other candidate can satisfy that condition for an even $$$k$$$. At this point, the analysis for even $$$k$$$ ends, but since the editorial mentions $$$k_2 = \frac{2n}{k_1}$$$, it looks like this analysis is still ongoing (which is not true).

    Now, we have a correct but slow algorithm for the original problem. The answer is an odd divisor of $$$n$$$ if it exists. If it does not, try $$$k = 2*2^x$$$ where $$$x$$$ is the exponent of 2 in the prime factorization of $$$n$$$. If this $$$k$$$ is not valid, the answer is $$$-1$$$.

    To optimize the time complexity, notice that the first condition states that $$$n \geq k*(k + 1)/2$$$. Making some slight approximations, we can say that $$$n \geq k*k$$$ or $$$k \leq \sqrt{n}$$$. Hence, if we can somehow find ANY odd divisor of $$$n$$$ which is $$$\leq \sqrt{n}$$$, we are done.

    Recall an obvious fact, for every divisor $$$div > \sqrt{n}$$$, the complement divisor $$$div ^\complement = \frac{n}{div}$$$ is $$$\leq \sqrt{n}$$$.

    Let's circle back to the $$$k$$$ even case, recall that $$$k_1 = 2*2^x$$$ was a possible candidate. If this candidate did not satisfy condition 1, it means that $$$k_1 > sqrt(n)$$$, or roughly $$$2^x > sqrt(n)$$$. Hence, the complement divisor of $$$2^x$$$ should be $$$\leq \sqrt{n}$$$. And voila, what's the complement divisor of $$$2^x$$$? It's $$$pod$$$ (product of odd divisor, that we had defined earlier). Now we have an odd divisor that satisfies condition 1, hence we have also solved for odd $$$k$$$ efficiently. Also notice that this is the largest odd divisor, because the largest even divisor was $$$> \sqrt{n}$$$.

    And by the way, did you notice that the fancy $$$k_2 = \frac{2n}{k_1}$$$ is nothing but $$$pod$$$ in our definition, i.e, $$$k_2$$$ is the number remaining when you remove all exponents of $$$2$$$ in the prime factorization of $$$n$$$.

    In retrospect, it worked because of the property of complement divisor. If we couldn't find an answer for even $$$k$$$ case, we were destined to find the answer for odd $$$k$$$ by taking the complement divisor (or prove that the answer does not exist). Since you asked for intuition, I made some rough approximations here and there, (leaving out a factor of 2 while comparing with $$$\sqrt{n}$$$ but you can refer to the editorial for the actual proof).

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

      Thanks you for such a detailed reply. I also tried the smallest odd factor idea but soon realized that it would be difficult to compute in the appropriate time complexity. I think the main link that I was missing was the complement divisor idea, which you did a great job explaining, thanks a lot.

      → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give proper explanation of D

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

(O(1)with some architecture-specific functions)

it's 2 * lowbit i thonk

→ Reply