BledDest's blog

Educational Codeforces Round 122 — Editorial
By BledDest, 3 years ago, In English

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)
  • Vote: I like it
  • +107
  • Vote: I do not like it

Comments Comments (67)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

video Editorial for Problem D : VIDEO LINK
video Editorial for problem C : VIDEO LINK

→ Reply
»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u please elaborate how to use bfs to calculate the no of steps

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 5   Vote: I like it +9 Vote: I do not like it

      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 so

      I can go to 10 as 5+(5/1) here x is 1

      I can go to 7 as 5+(5/2) here x is 2

      I can go to 6 as 5+(5/3) here x is 3

      and 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<i after that it is simple we create an adjacency list and a distance array and simply do a bfs from 1 calculating the distance Here is my solution look at the code below fast ip/op and above the while loop in the main

      In my code what I did is that I create an adjacency list where adj[i] is a set that contains all the destinations I can reach from i. I have used the set because there are many destinations that are repeated. In the creation of the adjacency list, I used two for loops the outer loop fixes the i and the inner loop creates all the x. After the creation of the adjacency list, I did a bfs with the source node as 1 and I calculated all the distance of each node from the source node that is 1.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          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 it

          the 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 matrix

          Let's take an example not related to the actual problem lets take the below graph

          1 <-> 2 <-> 3

          1 <-> 3

          if 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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              ← Rev. 2   Vote: I like it +5 Vote: I do not like it

              yeah, I noticed. I am also not able to understand why this is not working sorry :(

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              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

              → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          DFS is not guaranteed to find the shortest path.

          → Reply
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

In problem E there are only 2*m different spanning trees. For each edge there is only one interval, when it is useful.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you please elaborate a bit more about how to find these 2*m breaking points?

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +34 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

it was very good contest but weak testcases in C was bad point in it

→ Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    It could be to:

    1. decrease the time-consuming in input and output

    2. reduce the size of the input file

    3. include more queries for thorough checking

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For editorial in problem E, I don't quite understand for the last 4 paragraphs and here are my questions

  1. Why knowing the weight of the MST from the start of the range isn't enough?

  2. You mentioned that (from the last 3 paragraphs) we want to add more ranges. What does it mean by this?

Thanks. Cool problem btw

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it
    1. The MST doesn't change but the weight of edges increases or decreases unpredictably.
    2. You add more ranges so in the same range weight of an edge either increases or decreases.
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :)

          → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it

    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.

    <Ignore what was written here in previous revisions if you saw it. I somehow forgot we need the costs lol>

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D :How to calculate the minimum number of operations to get number i from 1 using BFS or Dp?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Task B is easier than task A :)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    true , i spent more time in A than B and C combined

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

In case someone is interested, I have made video solution for Problem A-D in Chinese (video BV1pq4y1h72x)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help why I am getting in run time error in Problem E https://mirror.codeforces.com/contest/1633/submission/144915859

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

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://mirror.codeforces.com/contest/1633/submission/144789682

Moreover 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://mirror.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 ？

→ Reply
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really don't understand solution of problem F. Maybe because i'm specialist. Can someone elaborate it?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very good editorial and problems as usual. Ths

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Because the maximum number of steps required to convert 1 to any of the b[i] = 12. So, the upper bound is 12 * n

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share their solution to F using Link/Cut tree ? Thanks in advance

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I have a doubt in the Make Them Equal Problem

Test case — 

4 4
1 7 5 2
2 6 5 2

Output — 9

Here 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 ???

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    You Noob

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 :)

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh,on more thing.I saw a discuss about this question just now,just at the top of this page.I'll read more about it.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              OK, now I know why there are just n "real" MST. Thanks a lot!

              → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E can't be solved by Prim's Algorithm or can it?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D how exactly we can get a safe upper bound for maximum possible weights? Do we first usually code for upper-bound and then find the solution? As we can't code dp solution for the second half if we don't know that upper bound is small.

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem F's datas are not enough to test time limit . Test cases should be more accurate .However problem was good

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

won't it exceed time limit if we go for n*k --> 10^9*t=10^11 time complexity for d problem?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D it is also possible to precalculate a map with 1000 entries with the minimum operations needed to reach the number from 1 and just paste it into the program :D . Then, since it's precalculated at the member's computer, can use a slow O(N^3) algorithm instead of the O(N^2) dp or the BFS approach.

→ Reply