### apoorv_kulsh's blog

By apoorv_kulsh, 4 years ago,

Set by : vntshh

Setter's solution

Set by : AakashHanda

Setter's solution

Set by : 7dan

Setter's solution

Set by : Vicennial

Setter's solution

Set by : rohitranjan017

Setter's solution

Set by : kr_abhinav

Setter's solution

Set by : apoorv_kulsh

Setter's solution

Set by : arnabsamanta

Setter's solution

Do give your feedback here : https://goo.gl/forms/xbsdMxnkA3XsG4092. Would love to hear your feedback, since that would help us get better!

• +63

 » 4 years ago, # |   0 Auto comment: topic has been updated by apoorv_kulsh (previous revision, new revision, compare).
 » 4 years ago, # |   0 Auto comment: topic has been updated by apoorv_kulsh (previous revision, new revision, compare).
 » 4 years ago, # |   +9 Really good problem set.
•  » » 4 years ago, # ^ |   +1 and solves nothing hahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahaha
•  » » 4 years ago, # ^ |   0 Nice comment to gain positive upvotes.
•  » » » 4 years ago, # ^ |   0 Do you think after looking at my comments (including this one) that I care about the upvotes.
 » 4 years ago, # | ← Rev. 2 →   -9 Solution for C is suboptimal, you can greedily choose the greatest K such that 2^K-1 <= X.
•  » » 4 years ago, # ^ |   -10 The array should have exactly X subsequences.
•  » » » 4 years ago, # ^ |   +3 Yes, and?
•  » » 4 years ago, # ^ |   +5 You don't need to output an array with minimum number of elements. You just need to find any array with size ≤ 104. There may be a different solution than described here, which is able to produce an array with lesser number of elements and satisfying the constraints.
 » 4 years ago, # |   0 For problem F, I created another graph with edges as vertices and then ran DFS on it. My solution is exceeding memory limit and I couldn't optimize it furthur. Please help. http://codeforces.com/contest/960/submission/37094773
•  » » 4 years ago, # ^ | ← Rev. 3 →   +3 At the bottom of your submission there is the part of the test your solution got MLE. As you will notice, the test contains 1e5 self loops. The problem is that for such a graph, by turning edges to nodes, you make new graph with |E|2 edges, thus your algo total complexity is |E|2 which is too much and the memory you take then is |E|2 too, which caused MLE before TLE :<. edit: notice that the problem still exists in usual graphs without self-loops. That's why switching vertices with edges is possible only if every vertex has small degree, cause every vertex causes his adjacent edges to form a clique, when you transform the graph
 » 4 years ago, # |   +4 Can someone explain to me how to write Dynamic Segment Tree in O(n*log n)? Is it possible to do it iteratively? Thank you in advance!
•  » » 4 years ago, # ^ |   +1 I usually do segment tree recursively. The way you use this structure is the same, but, instead of creating all nodes, you just create nodes that you actually need (you do not need a build function, only update).Suppose that you will insert/update something on index 5 and left node keep values in [0, 5], there is no need to worry about right node.It's kinda of more complex, but you can do this with lazy propagation too.My submission on F: 37069514
•  » » » 4 years ago, # ^ |   +3 Thank you :)
•  » » » 4 years ago, # ^ |   +1 sorry if I am asking for too much but can this also be implemented simply using STL's map ?If yes , can you show a sample code?
•  » » » » 4 years ago, # ^ |   0 That is what i have done before asking my question. However using STL`s map you will get O(n*logn^2). Due to this (probably) i got TLE on test 12. Here is my code. 37099586
•  » » » » » 4 years ago, # ^ |   0 Check out setter's solution tab for maps + O(nlogn) solution :)Also check out submission 37130983 based on dynamic segment tree approach
•  » » » 4 years ago, # ^ |   0 For F my O(n) soln is giving TLE http://codeforces.com/contest/960/submission/37123425 can anyone help please
 » 4 years ago, # |   0 can anyone explain me solution of problem f approach 1?
 » 4 years ago, # |   +6
 » 4 years ago, # |   +22 Amazing problemset. Although in my opinion, problem F is much easier to write than problem E :)
•  » » 4 years ago, # ^ |   +14 We apologise for the scoring issue. We underestimated/overestimated a few problems. Glad to hear you like the problem set :)
 » 4 years ago, # |   0 For F my O(n) soln is giving TLE http://codeforces.com/contest/960/submission/37123425 can anyone help please
•  » » 4 years ago, # ^ |   0 In F your solution is quadratic in the worst case, when all the edges are between the same two nodes. Check the case you got tle on
•  » » » 4 years ago, # ^ |   0 got it,thanks
 » 4 years ago, # |   0 Can someone please tell me why I got tle in question F Link to my code http://codeforces.com/contest/960/submission/37079088
•  » » 4 years ago, # ^ |   0 maybe you are making same mistake as i did..read reply on my comment above
 » 4 years ago, # |   0 Why dynamic segment tree is required in problem F? Can't it be solved with static segment tree? Can anyone help me where I am going wrong?
•  » » 4 years ago, # ^ | ← Rev. 4 →   +6 Sorry for my poor English: It is possible solve it with static segment tree: For every edge that goes from node u to node v add this in a list of edges that leave the node u, then in every node the edges are ordered, because you add this in the same order of the input and in every node have a segment tree of max, that store the max length of a path that end in this edge, it is easy to see that the sum of all edges for every node is M, because every edge is added to only one node, then initially the length of all the path for every edge is 1, in other list that contains all the edges sorted by minimum weight process the edges now, what happen when a edge (u, v, w) comes, it is possible to traverse along this, then update in node v all the edges that comes after the current edge in the input with x=value of this+1 we obtain this value doing a query to the segment tree in node u for the position of the current edge, the position (p) of the first edge that comes after the current edge is possible search it by a binary search in the list of edges of node v, then update the range (p, end) with x, every time that you process one edge update the answer, only left one problem: what happen when a edge of weight w update other after(in the input) with the same value w, this is violating that the weights of the path is strictly increasing, to solve this, store the value of all the next edges to process of the same weight w, used this value to update, so not matter that you update "invalid" edges weight lower or equal to the current because this values never will by used when you process the edges sort by weight Finally let you a link to my solution: 37110519 It is possible solve with a unique segment tree you only assign for every edge in the same node a continuous position on it.
 » 4 years ago, # |   +5 Nice editorial especially problem D
 » 4 years ago, # |   0 Where is the editorial for the divide-by-zero problem? 2018/0 = ? Did anyone solve it?
 » 4 years ago, # |   0 How to solve problem E using Dp?
 » 4 years ago, # |   +5
 » 4 years ago, # |   0 In problem G, how did you do FFT by modulo? Can you explain it more detailed? I know that it is because MOD-1 is divisible by 2^23, but what it gives to us? And where did you get numbers root and root_1?
•  » » 4 years ago, # ^ |   +13 This is in fact [number theoretic transform](https://en.m.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform).Root is a 223-th primitive root, and root_1 is perhaps its inverse. How to find it? We don't really know. Luckily, if r is a primitive root modulo n, and gcd(e, n - 1) = 1, then re is also a primitive root. So you can just find it using brute force.
 » 4 years ago, # | ← Rev. 2 →   +5 For problem G, is there some intuitive way to realize that number of permutations with |LIS| = k k elements visible from front is in fact just Stirling numbers of first kind? (It is evident from the recurrence, but not able to create a mapping between the two)
•  » » 4 years ago, # ^ |   0 We can solve the problem as follows:For each i from 0 to n, find the number of ways we can permute i elements to have exactly a - 1 records lets call it f(i, a - 1). In the end , we can select f(i, a - 1), f(n - 1 - i, b - 1), and we place n between them to make it exactly equal to (a, b) records. We can find that using basic combinatorical interpretations. Now, also . So, f(i, a - 1) = S(i, a - 1).Now, to find final answer you can use the formula mentioned in the editorial, and here
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Thanks, but that's not what I asked. I already know that their recursion formulas (and polynomial form) are identical. What I'm looking for is an intuitive explanation which tells why is the number of permutations with exactly k cycles (i.e Stirling numbers of first kind) equal to the number of permutations with |LIS| = k elements visible from front. Is there some explanation which is able to map number of cycles to number of elements visible from front?
•  » » » 4 years ago, # ^ |   0 On an unrelated note, can you elaborate on "using basic combinatorical interpretations." please? How do you come up with that formula?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +5 We can build each permutation of n elements having k records as follows :Express n as sum of k positive integers, x1, x2, ...xk. Now, repeat k times : Create a new block of size xi, place the largest available element to the leftmost position of this block, and select and permute the rest available xi - 1 elements arbitrarily. Append this block to the left of the previous block.The number of ways to select elements for the ith block corresponds to the ith binomial coefficient in the product, and the factorials for internal permutations. We iterate over all ways to express n as a sum like this.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Nice!This explanation also helps realize the equivalence between number of cycles and size of LIS number of elements visible from front. x1, x2, .. xk can correspond to the size of the K cycles. The largest element of each cycle corresponds to an LIS element.
 » 4 years ago, # |   0 Maybe i think we can maintain the "sigema { hk[x]^2 }" directly. we can use tree subdivision and dymanic segment tree to deal with the problem.For more specific , we maintian "size^2 size num"in the datastruct . And it's obvious that when we change the flavour we can maintian such information easyly.
 » 23 months ago, # | ← Rev. 3 →   0 Nvm, got it
 » 14 months ago, # |   0 We don't need to consider any even odd thing in Problem-E Alternating tree, just two dfs directly is sufficient, one for setting answer consider any node as root and second for applying rerooting-DP to calculate the answer for every children node of the previously considered root and adding to the final answer side by side. Complexity-> O(n) link to my solution: alternating_tree_submission