### 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  845, Comments (109)
 » Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
 » Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
 » Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
 » The time complexity allowed for problem C is too high
•  » » 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{A}$ not pass, but $n * \sqrt{A}$ pass.
•  » » » how to achieve O(n*A^(1/3))?
•  » » » » The maximum factors of a number $A$ are bounded by $\sqrt{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.
•  » » » » » thanks!
•  » » » 2 weeks ago, # ^ | ← Rev. 3 →   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!!
•  » » » » The statement clearly say that:It is guaranteed that the sum of n over all test cases does not exceed 10^5.
•  » » » I passed with time complexity $O(n\log n \sqrt A)$.
•  » » » » I used Segment Tree and passed with time complexity $O(128 n \log m)$.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 3 →   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.
•  » » » You are right, n*sqrt(A) should pass. :)
 » When systesting?
 » The TL on F is stupidly high, a simple $O(n^2)$ passed: 190000292
•  » » Hacked
•  » » » 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.
•  » » » » what does that "tune=native" do ?
 » Auto comment: topic has been updated by ShivanshJ (previous revision, new revision, compare).
 » idk why i was stuck on B. I knew the final product needed for the answer, but it was failing pretest 3
•  » » same i dont know why
•  » » » 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.
•  » » » » 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.
•  » » 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
•  » » 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.
•  » » overflow
 » The editorial of #845 is earlier than #844Or there will be no editorial of #844
•  » » There was an unofficial for 844
•  » » 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
•  » » » lol, don't assume we have friends.
 » Actually that was the best idea. Hats off boss.
 » 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._
 » My solve for C barely passed, 1996 ms. Thought I had to binary search for length.
•  » » Lucky! Can you share your idea?
•  » » » 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 →   Any advice on How to master number theory..I Struck in "C" today.(How to think in the mathematical sense for the problem).
 » OMG！Lunar New Year's Eve Round(Div.2)
 » can anyone tell me what i did wrong in C?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   Bro,You have to minimize the answer.Which you have notdone.
•  » » » 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?
 » I managed to hack my own code after the contest, feels bad to get accepted after this...
 » A good Spring Festival gift, but a stupid me. ):
 » It's such a pity that I watched the Spring Festival Gala and failed to solve E in time.
 » 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.
•  » » 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 ?
•  » » » 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.
•  » » » » Aha it's clear now. Thanks !
 » 2 weeks ago, # | ← Rev. 2 →   I found B fun, thanks for the round guys
 » There is a right bracket missing in the solution of Problem D. The location is just as the picture shows.
 » 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?
•  » » This algorithm could be improved by finding the interval that a_i is the leftest largest element in any subarray.
•  » » 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.
•  » » 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 →   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.
 » I don't know why preset 3 was failing on my B's solution and my solution was correct :(
•  » » 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
 » Super fast editorials (: And very interesting problems.
 » 2 weeks ago, # | ← Rev. 2 →   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.
 » 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 ?
•  » » 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 :/
•  » » » 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 :)
•  » » » » 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.
 » video editorial for Chinese:BiliBili
 » Editorial of B is just awesome.
 » 2 weeks ago, # | ← Rev. 2 →   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
•  » » 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.
 » Can someone please tell me what is the mistake in my code of problem C https://codeforces.com/contest/1777/submission/190077492
 » 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.
•  » » 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 →   F can be solved with the standard D&C in less than 1s. why is the TL 8s?
 » 2 weeks ago, # | ← Rev. 2 →   I don't know why I was stuck on E. It was TLE on test 3. But my time complexity was right.
 » I didn't understand the explanation for D.
•  » » 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.
 » 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?
 » I didn't understand how we calculate expected value of k boolean nodes in problem D, can someone explain in simpler)
•  » » 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.
•  » » » thanks!
 » 2 weeks ago, # | ← Rev. 2 →   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.
 » emordnilap is palindrome backwards.
 » 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.
•  » » 3rd line of code: #define int long long 
 » 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?
 » 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
•  » » 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.
 » For Problem F, the editorial solution gives Memory Limit Exceeded on test 84. https://codeforces.com/contest/1777/submission/190232289
•  » » Can someone please tell me where have I got it wrong?
•  » » 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.
•  » » » Thanks.
 » 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.
•  » » Or they could just do the standard D&C which divides in half :)
•  » » » How to solve it with standard D&C?
•  » » » » 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
•  » » » » » 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.
•  » » » » » » 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?
•  » » » » » » » 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 →   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!
 » Can problem C be solved using binary search(Optimization problem) as we have to minimise the maximum difference here?
 » problem B was just super good.Idea of solving it is just amazing.
 » 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.
•  » » No, you need to do topological sort on the condensed graph.
•  » » » 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 →   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.
 » Hey I find this Round has become unrated.Does anyone know why?
•  » » I was about to write the same; did you get any answers ???
 » What E(F(A)) means?