vkditya0997's blog

AtCoder Grand Contest 002 Problem D
By vkditya0997, history, 8 years ago, In English

Hello codeforces,

I am not able to understand the editorial for this question.

Can someone please explain the approach to this problem more clearly?

Editorial link : http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

Problem link : http://agc002.contest.atcoder.jp/tasks/agc002_d

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Updated the editorial. Now I hope it's easier to understand.

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

(I'm assuming that the part you didn't understand is the fifth paragraph, the one in which the author improves the complexity from O(Q * M * log(M)) to O((M + Q) * log(M)).

First off, when we binary search the answer for a query (x, y, z), we are essentially doing the following: let f(x, y, z, r) = (can we visit at least z nodes from x and y using edges with indexes not greater than r). Then, let a0, ..., am be a sequence such that (ai = f(x, y, z, i)). Then, obviously, a0 = false, ... a(sol-1) = false, a(sol) = true, ..., am = true. We are essentially finding the point where (a) stops being false. To do this, we sequentially calculate log(m) different values for f(x, y, z, _).

Now, let's see how we can do this in parallel for q queries (xi, yi, zi). For each query, we have to sequentially calculate log(m) different values for f(xi, yi, zi, _). But, we can calculate the j'th value of f(xi, yi, zi, _), for all i's, at the same time !

To do this, we simply associate each value calculation with it's specific edge, then pass through the edges in their index order. We first unite the ends of the edges in our union-find data structure. When we reach an edge associated with a value calculation, we then see if f(xi, yi, zi, _) is true or false, by querying the size of the components to which xi and yi belong in our union-find data structure. Based on this, we decide which is the following value calculation for that specific query.

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

    First 2 paras were perfectly clear. In last para, what do u mean by assosciating each value calculation with it's specific edge? Also when we reach an edge assosciated with a value calculation, we see if f(xi, yi, zi, _) is true or false. What does _ holds when we are querying?

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

      First, in order to do one value calculation f(xi, yi, zi, ri), we iterate over edges by their indexes, adding them to our union-find data structure, until we reach edge (zi). Then, we check if the sum of sizes of the components of xi, yi, (or, if they're in the same component, the size of that component) is larger or equal to ri. When we do several at once, we go through all the edges, and once we reach edge zi, we do the same check. What I mean by associating the value calculation with it's edge is that, for each edge, we keep a list of calculations f(xi, yi, zi, ri) where zi = the edge. Associating them simply means adding a pointer to the place where we want to result of f(xi, yi, zi, ri), together with (xi, yi, zi) to the list of edge (zi). The _ holds the number of nodes we want to be able to visit.

      → Reply