### FelixMP's blog

By FelixMP, history, 5 months ago,

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

• +82

 » 5 months ago, # |   +12 Congratulations to winners!
•  » » 5 months ago, # ^ | ← Rev. 2 →   -23 Congratulations to winners!
 » 5 months ago, # | ← Rev. 2 →   +5 What a contest! (☉_☉)
 » 5 months ago, # |   +171 MathForces
•  » » 5 months ago, # ^ |   +141 and ConstructiveForces
 » 5 months ago, # |   +13 used unordered_set for B, got TLE.
•  » » 5 months ago, # ^ |   +55 unordered_set works $O(n^2)$ in STL. Use set
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   -80 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.com/contest/1656/submission/150817878UPD: 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.com/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
•  » » » » » 5 months ago, # ^ |   -18 Thanks for the explanation. Cheers.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +79 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.
•  » » » » » » 5 months ago, # ^ |   +15 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!
•  » » » 5 months ago, # ^ |   0 can you explain in detail??thanks in advance.
 » 5 months ago, # |   +5 Thanks for the fast editorial.
 » 5 months ago, # |   +7 Proof for E?
•  » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # | ← Rev. 2 →   +26 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-GoodIf 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.
•  » » 5 months ago, # ^ |   0 How to know the contest id of a contest ?
•  » » » 5 months ago, # ^ |   0 For this contest, I've already hyperlinked all the pages.For a general problem, click on it, and take a look at the URL. The URL resembles https://codeforces.com/problemset/problem/1656/A. Here 1656 is the contest_id.An alternate way is to open the contest, for example, CodeTON Round and inspect the URL, which is like: https://codeforces.com/contest/1656. Here 1656 is the contest_id.
 » 5 months ago, # |   +136 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.
•  » » 5 months ago, # ^ |   +35 A straightforward solution of E for those who are bad in finding explicit constructions: Let the weight in the root be $W$ and sum in each of the root’s subtrees be $S$ Weight of every node can be written as $aW+bS$ 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 Now we can effectively compute weight of each node for fixed $W$ and $S$ 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$
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   +1 this is how the idea of bicoloring becomes clearCould you elaborate a bit more on why should we use bicoloring here ? and assign weights according to degree and color for each node
»
5 months ago, # |
Rev. 4   -46
Spoiler
•  » » 5 months ago, # ^ |   +4 Why don't you put code in spoiler, and why are you using float
•  » » » 5 months ago, # ^ |   0 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?.
•  » » » » 5 months ago, # ^ |   0 You should edit your comment and add code to a spoiler. It hinders scrolling down for others.
•  » » » » 5 months ago, # ^ |   0 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.
•  » » » » » 5 months ago, # ^ |   0 Thanks man!!!
 » 5 months ago, # |   +1 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$?
•  » » 5 months ago, # ^ |   +9 positive integers
•  » » » 5 months ago, # ^ |   0 ah, indeed
•  » » » 5 months ago, # ^ |   0 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 ?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 $0 + ... + k - 1 \equiv 1 + ... + k$, if that's what you're saying. I don't really understand your comment to be honest.
•  » » » » » 5 months ago, # ^ |   0 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.
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 5 months ago, # ^ |   +3 Can you explain me the rest of the problem D. I am not getting it.
•  » » » » » » » » 5 months ago, # ^ |   +1 Here it is
 » 5 months ago, # |   +1 How do you make checker for D?
•  » » 5 months ago, # ^ |   +11 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).
•  » » » 5 months ago, # ^ |   0 Oh, you're right. I misunderstood the editorial. My bad.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +18 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.
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 Just check: $\frac{k*(k-1)}{2}$ $\%$ $k$ = $n$$\%$$k$ $\frac{k*(k+1)}{2}$ $\le$ $n$
 » 5 months ago, # |   0 why this failed for B https://codeforces.com/contest/1656/submission/150765827
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 two pointer approach only works for positive Integers array. run this test case.3 2-1 3 5
•  » » 5 months ago, # ^ |   0 two pointer codesort(all(v)); int i = 0; int j = 0; while (i < N && j < N) { if (v[i] == v[j] + K) { cout<<"YES"<
 » 5 months ago, # |   0 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??
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 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
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ |   0 I came up with the same line of thought after the contest and I tried it out (150837085) applying AP formula and trying out for even numbers. Using AP was not exactly on the right track but close enough. I started looking for solns and this video here really helped me out to get it.
 » 5 months ago, # | ← Rev. 2 →   +81 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.
 » 5 months ago, # |   +61 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:int n, arr[200005]; int calc(int t) { int ans = 0; int mx = arr[0], mi = arr[0]; int lpt = 1, rpt = n - 1; for(int i = 1; i < n; i++) { int connl = min(arr[lpt] * (mi + t) + mi * t, arr[lpt] * (mx + t) + mx * t); int connr = min(arr[rpt] * (mi + t) + mi * t, arr[rpt] * (mx + t) + mx * t); if(connl < connr) { ans += connl; mx = max(mx, arr[lpt]); lpt++; } else { ans += connr; mx = max(mx, arr[rpt]); rpt--; } } return ans; } void solve(int TC) { cin >> n; for(int i = 0; i < n; i++) { cin >> arr[i]; } sort(arr, arr + n); int l = -1e7, r = 1e7; while(l < r) { int d = r - l; int m = l + d / 2; if(calc(m) < calc(m + 1)) l = m + 1; else r = m; } if(abs(l) == 1e7 && calc(l) != calc(l + 1)) { cout << "INF\n"; } else cout << calc(l) << '\n'; } 
 » 5 months ago, # |   0 Problem B "since the previous substractions are cancelled", what does this sentence mean ?
•  » » 5 months ago, # ^ |   +4 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
•  » » » 5 months ago, # ^ |   +7 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.
•  » » » » 5 months ago, # ^ |   0 the relative difference between them is not going to change this sentence did it for me, thanks
 » 5 months ago, # |   +4 Can someone explain D in simple terms?
 » 5 months ago, # |   0 Was my solution right? It looks not right at all but it has been passed during the system test. link：https://codeforces.com/contest/1656/submission/150790452
 » 5 months ago, # | ← Rev. 2 →   +58 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.
 » 5 months ago, # |   0 I got TLE in B (fail system test) because I use unordered_set in my program /(ㄒoㄒ)/~~. I couldn't believe it!
•  » » 5 months ago, # ^ |   -10 And I solve the problem by changing unordered_set into set. This used unordered_set 150731295. This used set 150837224.
 » 5 months ago, # |   +88 ShaBi! TaMenDouShi ShaBi A!
•  » » 5 months ago, # ^ |   +60 goodjob
•  » » 5 months ago, # ^ |   +1 Excuse me, what happened? I'm a little curious.
 » 5 months ago, # |   +13 TheoryForces.
 » 5 months ago, # |   0 Proof for B? I'm so lame..
•  » » 5 months ago, # ^ |   0 a b c d (b-a) (c-a) (d-a) subtract 'a' from every element ((c-a)-(b-a)) ((d-a)-(b-a)) subtract 'b-a' from every element = (c-b) (d-b) ((d-b)-(c-b)) subtract (c-b) from every element = (d-c) So by this you can always end up in any two pair of element . So for every element 'a' you have to find another element 'b' such that a-b = k or if a-k is present in the array.
•  » » » 5 months ago, # ^ |   0 okeyyy thx!! :)
 » 5 months ago, # |   +14 WeakPretestForces
 » 5 months ago, # | ← Rev. 2 →   0 Can someone explain this approach 150742723
•  » » 5 months ago, # ^ | ← Rev. 3 →   +1 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
•  » » » 5 months ago, # ^ | ← Rev. 4 →   +1 Why do we need min(even,odd)
•  » » » » 5 months ago, # ^ |   0 because k=min(k,k+2*C+1) remeber C>=0.
•  » » » » » 5 months ago, # ^ |   0 Got it thanks very much
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ |   +4 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
 » 5 months ago, # |   0 How to proof the E？
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   0 thx
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 see this -LINK
•  » » » 5 months ago, # ^ |   0 thx
 » 5 months ago, # |   +1 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 ?
•  » » 5 months ago, # ^ |   +8 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 simplifyingn%k= ((k/2)%k*1)%kn%k=(k/2)%k.
•  » » » 5 months ago, # ^ |   +1 Ok got it. Thanks !
 » 5 months ago, # |   0 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.
 » 5 months ago, # |   +3 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.
•  » » 5 months ago, # ^ |   +11 That's my issue with most editorials, they show the solution but not the "path" or thought process that can lead to that solution
 » 5 months ago, # | ← Rev. 2 →   0 In editorial of D, What is this architecture-specific function? I could not find it on goolge
•  » » 5 months ago, # ^ |   0 In c++ you have __builtin_ctz(x) which counts how many times 2 divides x.
 » 5 months ago, # |   +3 Love problems like C
•  » » 5 months ago, # ^ |   0 why this code is failing for problem C 150995742
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 checked your code: if(v[i] == 1) check_one = true; should be put in for(int i=0;i
 » 5 months ago, # |   0 In editorial of D: "all odd candidates of k must be odd divisors of n ". Explain this please
 » 5 months ago, # |   0 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?
 » 5 months ago, # |   0 nice contest
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   0 Failing Testcase: Ticket 2641
•  » » 5 months ago, # ^ |   0 i think that the problem is that you start the loop with 1 and therefore you don't check ifthe element v[0] contains 1 or not. so for a fix after the end of the loop check if v[0] has 1 or no
 » 5 months ago, # |   0 hello, in problem D why 15 is not 2-good ( 14 + 1 = 15)
•  » » 5 months ago, # ^ |   0 it is 2-good, eg- 8+7
•  » » » 5 months ago, # ^ |   0 That's true i forget that the answer could be any K and not the first k. that's why i was confused when i read it in the example. thank you.
 » 5 months ago, # |   0 can someone explain how we came to this conclusion in problem D LineThe smallest of such k is k1=2^ν2(n)+1, i.e. the smallest power of 2 that does not divide n.
 » 5 months ago, # |   +20 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.
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   +10 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}$ :)
•  » » » » 13 days ago, # ^ | ← Rev. 4 →   0 Why would doubling $U$ prevent this solution?
•  » » » » » 11 days ago, # ^ |   +8 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.
•  » » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 :O i seealthough yeah 1e18 can be factored quickly enough to pass
 » 5 months ago, # |   0 why problom I has rating only 1800?
 » 4 months ago, # |   0 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.
•  » » 4 months ago, # ^ |   +26 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).
•  » » » 4 months ago, # ^ |   0 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.