### BledDest's blog

By BledDest, 3 years ago,

1633A - Div. 7

Idea: BledDest, preparation: BledDest

Tutorial
Solution (BledDest)

1633B - Minority

Idea: BledDest, preparation: awoo and Neon

Tutorial
Solution (awoo)

1633C - Kill the Monster

Idea: BledDest, preparation: Neon

Tutorial
Solution (awoo)

1633D - Make Them Equal

Idea: BledDest, preparation: Neon

Tutorial
Solution (Neon)

1633E - Spanning Tree Queries

Idea: BledDest, preparation: awoo

Tutorial
Solution (awoo)

1633F - Perfect Matching

Idea: BledDest, preparation: BledDest

Tutorial
Solution (BledDest)
• +107

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +2 video Editorial for Problem D : VIDEO LINK video Editorial for problem C : VIDEO LINK
 » 3 years ago, # |   +41 The blend of BFS with Knapsack makes problem D very beautiful if we see it from the perspective of of DSA based interview. An ideal problem to test your graph and Dp skills and reduce the problem to a known simpler problem.
•  » » 3 years ago, # ^ |   0 can u please elaborate how to use bfs to calculate the no of steps
•  » » » 3 years ago, # ^ | ← Rev. 5 →   +9 since the constraints are not so big of bi, we do a brute force kind of thing to create the adjacency list.for each, i in the range[1,1000] I can calculate where I can go from i for example, suppose i=5 soI can go to 10 as 5+(5/1) here x is 1 I can go to 7 as 5+(5/2) here x is 2I can go to 6 as 5+(5/3) here x is 3and so on..Here is a small observation if we choose x>5 then we will not reach anywhere and unnecessarily we will waste one operation so we will choose x
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I tried calculating number of steps with DFS instead of BFS, but I am getting wrong answer.Can you please tell that why DFS will not work here?My Submission for your reference — Click Here
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 I may not give you give a concrete answer to your question because whenever there is a question of finding the shortest path or minimum distance in an unweighted graph the only algorithm that pops in my mind is bfs I have never applied dfs or rather never thought of it but I think you can apply dfs it depends on how you have applied the dfs you have to do a little tweak in itthe difference between dfs and bfs is the order in which you visit your neighbour In bfs you first visit your neighbouring nodes which are closest to your source node In dfs you visit the neighbour in the order you have stored in adjacency list or adjacency matrixLet's take an example not related to the actual problem lets take the below graph1 <-> 2 <-> 31 <-> 3if do the conventional dfs and start from 1 the distance from 3 will be 2 but if you follow the 2nd path it will be 1 if you follow the first path and 2nd path will never be visited because 3 is already visited so the tweak you can do is that as you are returning after processing all the nodes you mark it unvisited like you started from 1 you visited 2 calculated its distance which is 1 then you visited 3 calculated its distance which is 2 now as you are returning from 3 mark it unvisited because next time when you take the 2nd path 3 will remain unvisited and you can relax its distance from 2 to 1. So as you can see this tweak is a little cumbersome and bfs is more intuitive that is why go for bfs but you can apply dfs but you have to tweak it
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks for this wonderful explanation. As you said, to make the nodes unvisited after processing so as to relax the distances, I am doing the same thing in the dfs function of my Solution.Following is the snippet in the DFS function which I am referring to: if(steps[n]!=0) //if visited then enter to relax { steps[n]=min(steps[n],cnt); //relaxation return 0; } (Basically, through DFS, Number of steps for some n, are incorrectly calculated. But through BFS, number of steps are correctly calculated, and, I am not able to figure out this reason.)
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 yeah, I noticed. I am also not able to understand why this is not working sorry :(
•  » » » » » » » 3 years ago, # ^ |   +5 When cnt < steps[n], you should not only update the vertex n, you should update all vertex that are reachable from the vertex n. So that is the reason, why dfs never(I mean only in trees) used to calculate the shortest paths. You can actually try "fixing" your dfs by returning 0 if and only if cnt >= steps[n], but with this implementation dfs works in (n! * n) as far as I remember. This dfs can be useful if n < 15, and you need to work with all possible paths. So, in this problem bfs is essential
•  » » » » » 3 weeks ago, # ^ |   0 DFS is not guaranteed to find the shortest path.
 » 3 years ago, # |   +34 In problem E there are only 2*m different spanning trees. For each edge there is only one interval, when it is useful.
•  » » 3 years ago, # ^ |   +3 Can you please elaborate a bit more about how to find these 2*m breaking points?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +34 No test (including hacks) has more than $m$ good MSTs, I'm inclined to think that is the true limit since I can't find a counter case.I used this to solve E in a way that works in $O(X m \log(m)\log(10^8) + k(n + \log(m))$, where $X$ is the number of MSTs which are optimal for some $X$.So if we have calculated $x_1, x_2, \ldots, x_{i - 1}$, we know that the next range with the same MST must go from $x_{i - 1}$ to some $x_i$. So we can just binary search for this value $x_i$. In each step of the binary search we will have to check if the MST is the same. We can trivially do this in $O(m logm)$, so we get a total of $O(m^2 \log(m)\log(10^8))$. Now for a query we can just binary search to find the correct MST, and compute the absolute value in $O(n + \log(m))$ time. You can store prefix sums in advance to be able to do this in $O(\log(n) + \log(m))$ but it isn't necessary to get AC.So the total complexity is $O(X m \log(m)\log(10^8) + k(n + \log(m))$ or $O(X m \log(m)\log(10^8) + k(\log(n) + \log(m))$ depending on implementation.Code — 144725137
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks! One small point, should the first term be $O(m^2\log m \log M)$, where $M = 10^8$?Here is my python code with complexity $O(m^2\log m \log M + k \log m)$ https://codeforces.com/contest/1633/submission/144881605
•  » » » » 3 years ago, # ^ |   0 Yup, it should be, fixed it now.
•  » » 3 years ago, # ^ |   +5 Here is my proof why for each edge there is only one interval.Let's prove that for q > w of the edge, its selected in some range [l, r] (q > l, q > r). Now, key insight. You can find out whether edge is selected in MST in other way: join everything (literally everything) up to edge w with weight less than it, and calculate number of components (it's not a tree anymore). Edge will be selected in MST if and only if number of components decrease with this additional edge.Now, consider what we have to join for some q. We have to join everything from w to q + (q — w). Because only those weights satisfy |weight — q| < w, where w is our edge for which we prove this fact. And when we increase q then left 'side' of subrange is fixed and only right side of 'subrange' is increasing. So we only add new edges into our 'join everything' graph. So edge with weight w will be selected while it decrease number of components. In other words, it will not be selected when vertices it connects ends up within same component. Case when q < w is completely symmetrical.Looks legit.From now on: for q > w edge is used for single range, and for q < w edge is used for single range. But it's easy to see that for q = w we use edge with weight w. Possible loophole: what if several edges has same weight and same endpoints, you can't use all of them, you'll use only one of them. But I think it can be proven if done more carefully.
 » 3 years ago, # |   +27 it was very good contest but weak testcases in C was bad point in it
 » 3 years ago, # |   +43 Out of curiosity, what was the purpose of having both explicit and compressed queries in problem E? Is there some kind of solution that this was meant to cut off? Right now, it seems to me like the problem would be the same with only the compressed queries.
•  » » 3 years ago, # ^ |   +27 It could be to: decrease the time-consuming in input and output reduce the size of the input file include more queries for thorough checking
 » 3 years ago, # | ← Rev. 2 →   +25 Problem C can be solved in O(1) time as follows:Let's assume that Monocarp spends $x$ coins on upgrading their armor and $y$ coins on upgrading their attacking power. The total number of turns required to defeat the monster would be $\frac{h_M}{d_C + wy}$ and the maximum number of turns monocarp can survive is $\frac{h_C + ax}{d_M}$. Thus, we have: $\frac{h_C + ax}{d_M} + 1 > \frac{h_M}{d_C + wy}$Note the +1 there, since Monocarp is the one who attacks first. Obviously, we also have: $x + y = k$Because if Monocarp can defeat the monster by using only some of their coins, they will be able to do the same while using all of their coins. Substituting the second equation into the first, we get a quadratic equation, which can be solved to get two roots (the roots may be equal). Let's call the two roots $m$ and $n$. If there exists a positive integer in the range $(m, n)$ then Monocarp can defeat the monster and the answer is YES, otherwise the answer is NO.
•  » » 3 years ago, # ^ |   0 when you substitute suppose x= k-y and solve 1st equation. There will be terms such as hc*dc and many more, which will cause overflow.
 » 3 years ago, # |   +3 For editorial in problem E, I don't quite understand for the last 4 paragraphs and here are my questions Why knowing the weight of the MST from the start of the range isn't enough? You mentioned that (from the last 3 paragraphs) we want to add more ranges. What does it mean by this? Thanks. Cool problem btw
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 The MST doesn't change but the weight of edges increases or decreases unpredictably. You add more ranges so in the same range weight of an edge either increases or decreases.
•  » » » 3 years ago, # ^ |   0 Hmm I see. But how does it translate to (base[y] + (n - 1 - 2 * cnt[y]) * 1ll * (2 * x - ev[y])) / 2; At the implementation part?
•  » » » » 3 years ago, # ^ |   0 Sorry I shouldn't say that the cost doesn't change. It should be the number of edges whose weight is greater than w doesn't change.
•  » » » » » 3 years ago, # ^ |   0 I see. Thanks for your explanation. I think ExplodingFreeze solution is more intuitive for me (than the editorial one). The binary-search-ing the MST idea is insightful for me and it's very cool somehow :)
 » 3 years ago, # |   0 in problem D, do we really need dp for calculating the minimum operation to get the number i from 1, can we take always x=1? and in end take x according to the remaining value. Will it be not optimal??
•  » » 3 years ago, # ^ | ← Rev. 4 →   +4 It is not necessarily possible you can choose the remaining value. Consider $a_i = 12$. Lets list the values of $\lfloor\frac{a_i}{j}\rfloor$ for all $1 \leq j \leq n$ — $[12, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1]$.Note that we can generate all values from $1$ to $\sqrt{a_i}$, but for values larger than that we have $a_i - \sqrt{a_i}$ values remaining but only $\sqrt{a_i}$ possible divisors, so the majority are unreachable.
•  » » » 3 years ago, # ^ |   0 Got it , Thanks !
 » 3 years ago, # |   0 Problem D :How to calculate the minimum number of operations to get number i from 1 using BFS or Dp?
•  » » 3 years ago, # ^ |   0 you can use both of them by bfs you can make loop from 1 to the number x and make edge from x to x + x/i
 » 3 years ago, # |   +17 Task B is easier than task A :)
•  » » 2 years ago, # ^ |   +3 true , i spent more time in A than B and C combined
 » 3 years ago, # |   0 In Problem D, why are the maximum operations to convert 1 into b is 12, why not 10, if we fix x as 1 and keep iterating we would reach 1024 in 10 operations which exceed the maximum value of b. how can you make sure that there is no case where operations would exceed 12.
•  » » 3 years ago, # ^ |   0 No,we need at max 12 operation to reach(try on number which is not power of 2). Just write bfs or dp code for calculating operation and then take max you will get 12.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 OmPrakashIIT Can we calculate it mathematically?
 » 3 years ago, # |   +13 In case someone is interested, I have made video solution for Problem A-D in Chinese (video BV1pq4y1h72x)
 » 3 years ago, # | ← Rev. 2 →   0 It is hard for me to understand E's paragraph 4.why m^2 swaps can lead to m^2 's different arrangements. Could someone share his idea with me?
 » 3 years ago, # |   0 Can anyone please help why I am getting in run time error in Problem E https://codeforces.com/contest/1633/submission/144915859
•  » » 3 years ago, # ^ |   +3
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks a lot for your help. But after fixing these test case still, I am getting runtime error 144946651.
 » 3 years ago, # | ← Rev. 4 →   +16 Maybe there's another solution for problen E（sorry for awful English）: First I sort all the edges and queries(it takes O(q log q) time but fast enough... )I use "wqs binary search" to solve a famous problem:"If every edge has a color (B/W),find a MST that has exactly x white edges) (m+1)*n times. And then I get a O(nm^2 log w + q log q + nq) solution : https://codeforces.com/contest/1633/submission/144789682Moreover I note that we can use some geometry trick to make it faster( Or just use Lichao Segment Tree to make O(nq)->O(q log n) but n is only 50....)Finally I got a O(nm^2 log w + n^2m + q log q) solution : https://codeforces.com/contest/1633/submission/144802434 , that w is the maximum edge's weights (10^8 in this problem ). It runs fast enough and I think we can let m = 1225( 50*49/2 ) and this solution will be more excellent than the standard solution (that m^3 log m) ,Maybe ？
 » 3 years ago, # |   +29 Problem F's datas are too weak and the time limit is too large,so that many solutions with higher complexity can even pass.BTW,once I built a wrong Heavy-Light Decomposition on it and got Accepted...
 » 3 years ago, # |   0 I really don't understand solution of problem F. Maybe because i'm specialist. Can someone elaborate it?
•  » » 2 years ago, # ^ |   +6 You need to learn Heavy Light Decomposition or Link Cut Tree,but I guess you haven't learned that,problem F is not an easy thing for beginners.
 » 3 years ago, # |   0 Very good editorial and problems as usual. Ths
 » 3 years ago, # |   +5 In Problem E, while following the tutorial, ensure that while sorting edges based on their $|w_i-x|$ value, in case of a tie between two edges, you always pick the larger edge first. The reason is this: We calculate the MST at the start of each range $[a, b)$. For any $x \ge a, x \lt b$, we use the MST cost at $a$, and decrease it by (number of edges whose weight $> a$) $(x - a)$ times. This decrease (or 'number of edges') is maximized when we pick the largest possible edges to form our MST.
 » 2 years ago, # |   0 Can anyone explain why in problem D, the max weight is limited to 12*n? I changed the max weight in my knapsack from k to 12*n and got accepted, but I am not sure why.
•  » » 2 years ago, # ^ |   +5 Because the maximum number of steps required to convert 1 to any of the b[i] = 12. So, the upper bound is 12 * n
•  » » » 2 years ago, # ^ |   0 Oh thanks, i actually forgot about the constrains, thank you. I couldve used some other bigger multiple as well, 12 is just a tight bound. Got it! Thanks!
•  » » » » 2 years ago, # ^ |   0 You don't actually need to know the upper bound. You could've guessed wrong. You can just compute the maximum possible cost (the cost of upgrading every single array element, which is the sum of all costs). If it's smaller than $k$, then no need for knapsack
 » 2 years ago, # |   0 Can anyone share their solution to F using Link/Cut tree ? Thanks in advance
 » 2 years ago, # | ← Rev. 3 →   0 I have a doubt in the Make Them Equal Problem Test case — 4 4 1 7 5 2 2 6 5 2 Output — 9Here 7 can be made in 3 moves — 1+floor(1/1)+floor(2/1)+floor(3/1) and for the 2 we use another 1 move This strategy gives us the maximum knapsack value as 10 i.e. it allows us to choose 2,6,2 as the weights in 4 allowed moves. Then why the output is 9 ???
•  » » 2 years ago, # ^ |   +35 You Noob
•  » » 2 years ago, # ^ |   +21 You got some misunderstanding on this problem. The correct process is that 1+floor(1/1)=2 2+floor(2/2)=3 3+floor(3/1)=6 6+floor(6/6)=7 Then 7 can be made in 4 moves.
 » 2 years ago, # |   0 Can anyone tell me how to count the prefix and optimize the algorithm with time complexity O(k (log (m)) in the second half of the e problem? I see that in the problem solution, each number is simply divided into increasing or decreasing, but what if a number happens to be in this interval (that is, the number happens to decrease first and then increase in this interval)? Another question is why this complexity is not O (K (log (m ^ 2))? After all, there are m^2 such intervals. (I'm very sorry, my English level is not high)
•  » » 2 years ago, # ^ |   0 From these intervals if you check their mst edges you will see that most of them are the same. In reality there are at most m different MST (I don't have a proof for that but couldn't find any counterexamples). So I did a binary search to find them Then I added the edges to solve the problem you comment. Having 2m points of change
•  » » » 2 years ago, # ^ |   0 Thank you! But,emm...I am sorry to say that I can't understand what you said.But I know the answer of my problem in the end.I didn't see that it add a interval boundary on each w_i in the standard code,if do that,every point in every intervals are just increase or decrease.There is a huge different between my mother tongue and English.I don't know if you can understand my point.
•  » » » » 2 years ago, # ^ |   0 Sorry, English isn't also my mother tongue and yesterday I was trying to be short because I was writing from my phone. What we try to do here is: - 1 find all spots/intervals where the MST (minimum spanning tree) changes - 2 add also all weights to this intervals (as you commented) to be sure that for a given interval any edge always increases or decreases its weight. For 1 you could go for (w_i + w_j) / 2 for all pair of weights (the spots where two different edges changes its order) but this will generate O(m^2) and most of these spots don't change the MST. So imagine that after you calculated all (w_i + w_j) / 2 you have a list like this intervals=[0, 6, 10, 16... , 120, 200]. You could calculate mst[interval[0]], mst[interval[end]]. - If those 2 mst are the same then all the other intervals could be eliminated, and also mst[end] (We are sure that the MST don't change in this range). - If they are different you calculate mid=mst[interval[(ini-end)/2]] and recursive apply the same to [0,mid], [mid,end] In the end you should have something like O(m) intervals, so you did this binary search m times giving you a complexity of O(mlogm). Then you should add (2) all the edges. I hope this was a little more clearer than my previous explanation. You could see my implementation in #145770276 I used the "cuts" variable to calculate all possible intervals and the "edgeCuts" the real ones. Sorry my code is a little messy because I did a lot of changes through various days. I hope this helps :)
•  » » » » » 2 years ago, # ^ |   0 First,I want to thank you for spending so much time answering me.In fact,this was much more clearer than your previous explanation.I have already understood what you said and learned a lot from your reply. Although I can not use Java,I still tried to read a lot your code.And I have to say that you are wise.Your code's time complexity is better than the standard code.But I am not so clever to prove there are n real MST.And I also can't to give a counterexample.But there is a truth that your code is better.Thanks!