### ShivanshJ's blog

By ShivanshJ, history, 2 weeks ago,

We hope you enjoyed the contest!. Thank you for your participation! Do vote under the Feedback section, and feel free to give your review of the problems in the comments.

Idea: ShivanshJ
Preparation: ShivanshJ
Editorialist: ShivanshJ

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

Idea: TimeWarp101 quantau
Preparation: TimeWarp101
Editorialist: TimeWarp101

Hints
Solution
Implementation (C++)
Implementation (Python)
Feedback

Idea: quantau
Preparation: TimeWarp101 quantau
Editorialist: TimeWarp101

Hints
Solution
Implementation (C++)
Feedback

Idea: AwakeAnay
Preparation: mayankfrost ShivanshJ
Editorialist: AwakeAnay

Hints
Solution
Implementation (C++)
Feedback

Idea: Crocuta
Preparation: mayankfrost
Editorialist: mayankfrost

Hints
Solution
Implementation (C++)
Feedback

Idea: Crocuta
Preparation: TimeWarp101
Editorialist: Crocuta

Hints
Solution
Implementation (C++)
Feedback

• +93

 » 2 weeks ago, # |   +1 Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
 » 2 weeks ago, # |   0 Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
 » 2 weeks ago, # |   0 Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
 » 2 weeks ago, # |   -45 lol didn't read
 » 2 weeks ago, # |   +13 The time complexity allowed for problem C is too high
•  » » 2 weeks ago, # ^ |   0 We had initially thought of keeping it tighter but after some discussions we decided that it wont be be a good idea to let $n * \sqrt[2]{A}$ not pass, but $n * \sqrt[3]{A}$ pass.
•  » » » 2 weeks ago, # ^ |   +15 how to achieve O(n*A^(1/3))?
•  » » » » 2 weeks ago, # ^ |   +5 The maximum factors of a number $A$ are bounded by $\sqrt[3]{A}$. Discussion for the same.Using some precalculation methods you can store factors for all possible smartness values as $n$ was capped at $10^5$. Refer the implementation for the same.
•  » » » » » 2 weeks ago, # ^ |   0 thanks!
•  » » » 2 weeks ago, # ^ | ← Rev. 3 →   -17 Why should n*sqrt(A) pass as n up to 1e5 and max A up to 1e5.It overall become something (1e4 * 1e5 *1e2.5)=1e11.5. My submission just pass 190040942. Of oder n*sqrt(A). Due this Iam not able to do even after have some idea.Edit: My reading mistake!!
•  » » » » 2 weeks ago, # ^ |   +12 The statement clearly say that:It is guaranteed that the sum of n over all test cases does not exceed 10^5.
•  » » » 2 weeks ago, # ^ |   +9 I passed with time complexity $O(n\log n \sqrt A)$.
•  » » » » 2 weeks ago, # ^ |   +8 I used Segment Tree and passed with time complexity $O(128 n \log m)$.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 3 →   0 Same, shouldn't have passed, code breaks an test1100000 10000083160 100000 timesThey just didn't include that test, which allowed many wrong submissions to pass, not only segtrees, but also some people used maps, which results in same complexity.It is posible to fit this code in TL, the person's above code runs in 2550ms, mine in 2170 ms (without I/O), so with small bit optimizations on segtree I got 2022ms (also without I/O), if improved more, this should pass.
•  » » » 2 weeks ago, # ^ |   0 You are right, n*sqrt(A) should pass. :)
 » 2 weeks ago, # |   +8 When systesting?
 » 2 weeks ago, # |   +26 The TL on F is stupidly high, a simple $O(n^2)$ passed: 190000292
•  » » 2 weeks ago, # ^ |   +24 Hacked
•  » » » 2 weeks ago, # ^ |   +29 Optimized it, I wanna know if you could hack this one: 190039238Also I think it's kind of wrong that people started downvoting my comment, me being hacked doesn't change the fact that TL is absurdly big when only $O(nlognlogA)$ was intended in the first place.
•  » » » » 2 weeks ago, # ^ |   0 what does that "tune=native" do ?
 » 2 weeks ago, # |   0 Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
 » 2 weeks ago, # |   0 idk why i was stuck on B. I knew the final product needed for the answer, but it was failing pretest 3
•  » » 2 weeks ago, # ^ |   0 same i dont know why
•  » » » 2 weeks ago, # ^ |   0 If you change n and m to long long it works, i guess because you are combining long long and int you should go for all long long but I´m not completely sure.
•  » » » » 2 weeks ago, # ^ |   0 it worked thanks,I read 10^5 as 10^4 in the range of n and tested 10^4 and thought declaring m long long shouldn't be a problem fm.
•  » » 2 weeks ago, # ^ |   0 while taking the modulo for the final product of n, n-1 and the modded factorial, you must have taken % after multiplying all three values in the same line. This may result in overflow. Ideally, multiply first two, take modulo, then multiply this result with the third term and take modulo. This will work
•  » » 2 weeks ago, # ^ |   +5 I had the same problem as you. When n = 10^5, n*(n-1) overflows an integer. So n also has to be a long long.
•  » » 2 weeks ago, # ^ |   0 overflow
 » 2 weeks ago, # |   +3 The editorial of #845 is earlier than #844Or there will be no editorial of #844
•  » » 2 weeks ago, # ^ |   0 There was an unofficial for 844
•  » » 2 weeks ago, # ^ |   0 Oh please stop spamming everywhere, You have commented in most of the blogs in recrnt months, Instead of spamming go and find some friends to talk with them
•  » » » 2 weeks ago, # ^ |   +13 lol, don't assume we have friends.
 » 2 weeks ago, # |   0 Actually that was the best idea. Hats off boss.
 » 2 weeks ago, # |   +4 In problem A,you could just simply check consecutive elements whether they were even or odd.The count of consecutive even or odd pairs or both would be the result._
•  » » 2 weeks ago, # ^ |   0 Who asked? There is already the solution above.
 » 2 weeks ago, # |   +1 My solve for C barely passed, 1996 ms. Thought I had to binary search for length.
•  » » 2 weeks ago, # ^ |   0 Lucky! Can you share your idea?
•  » » » 2 weeks ago, # ^ |   +1 Similar to the solve in the tutorial, I kept a frequency of how many factors appeared and I binary searched to what length to keep it. If the length is greater than the series, it fails.
 » 2 weeks ago, # | ← Rev. 3 →   0 Any advice on How to master number theory..I Struck in "C" today.(How to think in the mathematical sense for the problem).
 » 2 weeks ago, # |   0 OMG！Lunar New Year's Eve Round(Div.2)
 » 2 weeks ago, # |   0 can anyone tell me what i did wrong in C?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Bro,You have to minimize the answer.Which you have notdone.
•  » » » 2 weeks ago, # ^ |   0 I have sorted the smartness array in reverse, so the answer is the maximum value possible for each number,how can i further minimize it?
 » 2 weeks ago, # |   0 I managed to hack my own code after the contest, feels bad to get accepted after this...
 » 2 weeks ago, # |   +9 A good Spring Festival gift, but a stupid me. ):
 » 2 weeks ago, # |   +5 It's such a pity that I watched the Spring Festival Gala and failed to solve E in time.
 » 2 weeks ago, # |   +10 In E instead of topological sort, you can just check the in degree of each scc. If there are more than one scc with in degree == 0 then graph is not reachable.
•  » » 2 weeks ago, # ^ |   0 I'm not sure if I got your point right, but I guess you're saying that if there's more than one node with indegree equal to zero in the scc graph, then there is no answer, if so consider the following test:3 2 1 2 13 2 2you can make node one reach every node by reversing the second edge (3 2 2) could you clarify a bit more ?
•  » » » 2 weeks ago, # ^ |   0 No I was talking about the routine inside binary search. You make all edges with weights less than or equal to mid double sided. Then you make SCC and if there are more than one nodes with in degree 0 then not possible for that value of mid.
•  » » » » 2 weeks ago, # ^ |   0 Aha it's clear now. Thanks !
 » 2 weeks ago, # | ← Rev. 2 →   0 I found B fun, thanks for the round guys
 » 2 weeks ago, # |   +6 There is a right bracket missing in the solution of Problem D. The location is just as the picture shows.
 » 2 weeks ago, # |   +14 In the contest I wrote such an algorithm below for F: for every index I,find the interval that a_i can be the largest element in any subarray of it,which can be solved simply in O(n) complexity. Then just calculate the answer for every I using 01trie.The total complexity is O($\sum len(interval)$log n). If the value of a_i are distinct,the complexity is O(nlogn),which is acceptable.However,if there are same elements---for example a_i are same for every I,the complexity would be O(n^2) or higher.However,the algorithm passed both the pretest and the system test.Isn't the data too weak?
•  » » 2 weeks ago, # ^ |   0 This algorithm could be improved by finding the interval that a_i is the leftest largest element in any subarray.
•  » » 10 days ago, # ^ |   0 I don't understand. Won't that be O(n^2) even when the elements are distinct. Like, consider when the given array is in sorted order.
•  » » 10 days ago, # ^ |   0 190017681 is $O(n^2)$ (and not $O(n*logn)$ even if even if all elements are distinct. Simple testcase$a_i = i$$l_i = 0$ and $r_i = i+1$, $len_i = i$, $\sum len_i = O(n^2)$. It's easy to make all elements distinct, just change $a_i$ integer to $(a_i,i)$ tuple, although it won't help in this case.
 » 2 weeks ago, # | ← Rev. 4 →   +32 To my attitude , it's too standard. If you understand Chinese (or use translation softwares), you can see that the last two problems are just constructed with some standard algorithms(E: https://www.luogu.com.cn/problem/P3387 and F: https://www.luogu.com.cn/problem/P4735) . The fact that they weren't as hard as usual caused the ranking to seem a little strange. And I think if you replace E or F with harder or more interesting problems, then this round will be much better.
 » 2 weeks ago, # |   0 I don't know why preset 3 was failing on my B's solution and my solution was correct :(
•  » » 2 weeks ago, # ^ |   0 the answer should've been n*(n-1)*n!, however in your code, you iterate i(1 — n) and add i*(i-1) to answer, which is wrong
 » 2 weeks ago, # |   +1 Super fast editorials (: And very interesting problems.
 » 2 weeks ago, # | ← Rev. 2 →   0 Am I correct in saying the complexity of my solution for C is $O(a \ln m \cdot \ln(a \ln m) + m)$? It TLEs in 190006029 when I just use $a = 10^5$ but passes in 190008245 when I use compute up to the max $a_i$ from the input.
 » 2 weeks ago, # |   0 I thought about a harder version of problem D during the contest — At any integer time t>0 , the value of a node becomes the bitwise XOR of the values of all children (all nodes below it) at time t−1.How to solve this ?
•  » » 2 weeks ago, # ^ |   +5 I'm guessing that the solution would be the exact same. That the node would have a value of 1 approximately half the time. Not sure though :/
•  » » » 2 weeks ago, # ^ |   +13 well you could look at it this way that, let say the grandchildren becomes zero, it means they don't affect the children and we go back to the same case as was mentioned in the original question. Now another case is that the value of grandchildren matters , but you can see that the great grand children will become zero 1 step before, leaving children's value to be dependant on the grandchildren only and not the nodes below that. This way we can conclude that the answer would not change and probability of 0 or 1 will still remain (1/2). Correct me if I am wrong :)
•  » » » » 2 weeks ago, # ^ |   0 I mean, I'm not sure it's EXACTLY the same. You mentioned that after the leaves become 0, the parents of the leaves won't be affected. But if you look at the root of the tree for example, it will still have to deal with the XORs of a lot more values than in the original problem. However I'm pretty sure that the answer would still stay the same, b/c I doubt that the #of descendants that affect the current node matters.
 » 2 weeks ago, # |   +19 video editorial for Chinese:BiliBili
 » 2 weeks ago, # |   0 Editorial of B is just awesome.
 » 2 weeks ago, # | ← Rev. 2 →   +24 In problem E we don't even need to check for toposort in SCC, we just need to check the count of indegree, there should be only one element whose indegree should be zero in the SCCif there are no elements (you graph is not DAG)and if there are more than one, than you can't reach from one of the elements to other
•  » » 2 weeks ago, # ^ |   +8 Yes. You are right. The editorial is a little off. What we meant was you don't need to do the complete SCC algorithm. You can just do a toposort on the graph (which is the first part of SCC algo). If you think about it,the first node in this sorted list will be the one belonging to a 0-degree SCC. So, you can just check the reachability of all other nodes from the first node.
 » 2 weeks ago, # |   0 Can someone please tell me what is the mistake in my code of problem C https://codeforces.com/contest/1777/submission/190077492
 » 2 weeks ago, # |   0 how can one can generalize this statement "We will focus on computing the expected value of F(A) rather than the sum, as the sum is just 2n×E(F(A))" from editorial of question d.
•  » » 2 weeks ago, # ^ |   0 Each initial situation has chance of p(A)=1/2^n to appear, so E(F(A))=sum(F(A)*p(A))=sum(F(A)/2^n)=(1/2^n)*sum(F(A)).
 » 2 weeks ago, # | ← Rev. 2 →   +8 F can be solved with the standard D&C in less than 1s. why is the TL 8s?
 » 2 weeks ago, # | ← Rev. 2 →   0 I don't know why I was stuck on E. It was TLE on test 3. But my time complexity was right.
 » 2 weeks ago, # |   0 I didn't understand the explanation for D.
•  » » 2 weeks ago, # ^ |   +2 Jumping off someone else's comment, the idea is that if we let V(node, time) be the sum of all the possible values of this node over all initial positions, then V(node, time) is equal to 2^n-1 for all nodes and times(except when we hit a time such that the value of the node is guaranteed to become 0). This is b/c we can expect each node to have a value of 1 approximately half the time. This is kind of intuitive to see, but you might need to do some examples to prove this to yourself. So in order to calculate the sum of all ideal V's, we need another observation. At time 1, the problem states that the leaves of the tree will become 0. This effect will actually cascade upwards. So if a node i has a height of k_i (the distance from the node to the farthest leaf that's a descendant), then that means that it will have a 50% chance to be a 1 for exactly k_i times, before becoming a 0 for the rest of eternity. So the solution is to sum up all the values of k_i and multiply that sum with 2^n-1.
 » 2 weeks ago, # |   0 In problem D, the way $V_u(A,t)$ is defined (that is, value of node u is bitwise xor of all nodes at distance t from u) is not at all true for t=1, or many instances of time, for ex: Did I do something wrong or there is something wrong in the editorial?
 » 2 weeks ago, # |   0 I didn't understand how we calculate expected value of k boolean nodes in problem D, can someone explain in simpler)
•  » » 2 weeks ago, # ^ |   0 Expected value = C(k, odd) / (C(k, odd) + C(k, even)). It's a well known fact that C(k, odd) = C(k, even) with k > 0.
•  » » » 2 weeks ago, # ^ |   0 thanks!
 » 2 weeks ago, # | ← Rev. 2 →   0 I approached Problem C: Quiz Master in the following way:Let $pos_x$ store all numbers $num$ (present in given sequence $A$) such that $num$ is divisible by $x$. Also make $pos_i$ is sorted for each $1 \leq i \leq m$. If $pos_i$ is empty for any $i$ then our answer is $-1$ else it is just a variation of this problem Smallest range in K lists. Smallest range in K listsWe need to take one element from all $pos_i$. Let us take the smallest element from each $pos_i$. Since the range (difference in smartness) depends only on maximum and minimum value of numbers in list, so we try to increase the minimum number in our list (as we cannot decrease the maximum number). We continue this until we run out of option i.e., we can no longer increase the minimum number. The answer is the minimum range found in all cases.Here is my submission.
 » 2 weeks ago, # |   +11 emordnilap is palindrome backwards.
 » 2 weeks ago, # |   0 For B. Emordnilap, wouldn't you have to set ans to a long long (c++ solution)? N goes up to 10^5 and n * (n-1) would most definitely be past the ranges of an int. an int goes to about 2 billion (2^9 or to be exact 2147483647), and multiplying would be out of the range. Please tell me if I'm wrong.
•  » » 2 weeks ago, # ^ |   0 3rd line of code: #define int long long
 » 2 weeks ago, # |   0 If the optimal team has students with maximum smartness M and minimum smartness m, would having students with smartness X such that m≤X≤M the answer will not change. Is it me or the hint should rather read like this:If the optimal team has students with maximum smartness M and minimum smartness m, would having students with smartness X such that m≤X≤M change the answer?
 » 2 weeks ago, # |   0 In problem C what does this mean in the 2nd nested for loop while (curr_count == m) { ll curr_ans = vec[i].ff - vec[j].ff; if (curr_ans < global_ans) { global_ans = curr_ans; } for (auto x : factors[vec[j].ff]) { if (x > m) break; if (--frequency[x] == 0) { curr_count--; } } j++; } It would be a big help if someone explains me this
•  » » 2 weeks ago, # ^ |   0 2nd loop has tow parts.1st part: if (x > m) break;. This would be because we only care about divisors upto m. The divisors > m don't affect our question or answer.2nd part: if (--frequency[x] == 0) curr_count--;. When removing a particular factor, if decreasing it by 1 makes it total count as 0, then that means in current range we have no other numbers, that has that number as a factor, hence total found number of factors i.e curr_count is decreased by 1.
 » 2 weeks ago, # |   0 For Problem F, the editorial solution gives Memory Limit Exceeded on test 84. https://codeforces.com/contest/1777/submission/190232289
•  » » 2 weeks ago, # ^ |   0 Can someone please tell me where have I got it wrong?
•  » » 2 weeks ago, # ^ |   +5 That's because you submitted it in a 64 bit compiler. Pointers are 8 bytes in 64 bit compilers and 4 bytes in 32 bit compilers. The solution will pass if you submit it in a 32 bit compiler (like GNU G++17). But it takes double the memory in 64 bit compilers and therefore MLEs.
•  » » » 2 weeks ago, # ^ |   0 Thanks.
 » 2 weeks ago, # |   +1 Suggestion for people having TLE on F even though they implemented the optimal solution: Make sure you use a structure like a segment tree or sparse table to find the maximum in the interval you are solving. Or alternatively, pass it when returning recursion. Do not iterate through the entire interval as I did as that can take up to $O(N^2)$ time, because d&c does not divide in half each time.
•  » » 2 weeks ago, # ^ |   +11 Or they could just do the standard D&C which divides in half :)
•  » » » 2 weeks ago, # ^ |   0 How to solve it with standard D&C?
•  » » » » 13 days ago, # ^ |   +13 For a segment $[l;r]$ let $m={(l+r)\over 2}$.The optimal answer is either in the left, right or both parts. For the left and right parts solve recursively.Now, if the answer lies in the both parts. Assume that a segment $[L;R]$ such that $L \le m \lt R$ is the optimal answer.$max(a_L,...,a_R)$ lies either in the $[L;m]$ (left part) or $[m+1;R]$ (right part).Let's assume that it's in the right part. We will use two pointers. Initially, $L=m$ and $R=m+1$Assume that the right end of the answer is $R$. We already know the maximum element $mxR$ and xor $xrR$ of the right part. We have the right part of the answer, but we are missing the left one. How do we find it fast such that it would be the optimal one?We assumed that the maximum element in the optimal answer lies in the right part. It means that each segment $[L;m]$ such that $max(a_L,...,a_m) \le mxR$ combined with the right part could be the optimal answer. Create a trie for xor.While $max(a_L,...,a_m) \le mxR$, add $xor(a_L,...,a_m)$ to the trie, and decrease $L$. When you can't move $L$ anymore, get the best number $xrL$ from the trie to maximize $mxR ⊕ xrR ⊕ xrL$ and update the answer.When you are done, repeat the process for the left part(as if the max would be in there).submission
•  » » » » » 13 days ago, # ^ |   +5 I think that I understand your solution. It seems like O(N^2), but it actually has O(N log A) armortized complexity per division. Thank you for sharing.
•  » » » » » » 13 days ago, # ^ |   +13 The complexity is $O(nlogn * logn)$.Btw, why does it look like an $O(n^2)$ algo? It is absolutely the same as the standard D&C with an additional log from the trie?
•  » » » » » » » 13 days ago, # ^ |   +5 I mean the solution which first comes to mind seems like you would need to do $O(N^2)$, because of keeping maximum and stuff. (Like, going through all possible right and left borders) But actually, it's enough to move one border and move the other one only when necessary by fixing on which side maximum is.
 » 2 weeks ago, # | ← Rev. 2 →   0 Can't we just say that problem B is an Ad Hoc problem? Because if we draw permutations for the first 5 N's, we can see that every time, the number of inversions for all permutations are same, and if we think a little bit, we can represent the number of inversions with n * (n — 1), and that is it!
 » 2 weeks ago, # |   0 Can problem C be solved using binary search(Optimization problem) as we have to minimise the maximum difference here?
 » 2 weeks ago, # |   +3 problem B was just super good.Idea of solving it is just amazing.
 » 13 days ago, # |   0 It's a bit too much talking about SCCs and kosaraju for E when in the end it just comes down to topologically sorting the uncondensed graph to find an appropriate candidate. But knowing how to think it terms of SSCs does help in this kind of problem.
•  » » 12 days ago, # ^ |   0 No, you need to do topological sort on the condensed graph.
•  » » » 12 days ago, # ^ |   +5 If what you call the condensed graph is the one with nodes being SCCs, then you definitely don't. you can check my submission for example. I use binary search. To verify a given cost $c$, I consider the graph with reverse edges only if $c \leq w$. I only topo sort then do a dfs on the untransformed graph starting from the top/root node i get. This is because topo sort guarantees that if the "root" node can't reach another node, then this node can't reach the root node either.Of course it's true for whatever node $n_i$ that appears before node $n_j$ in the topological sorting.
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   +1 That’s an interesting solution. I didn’t think that you can do that. However, I believe that the SCC solution is actually straightforward for most people.
 » 12 days ago, # |   0 Hey I find this Round has become unrated.Does anyone know why?
•  » » 12 days ago, # ^ |   0 I was about to write the same; did you get any answers ???
 » 11 days ago, # |   0 What E(F(A)) means?