Блог пользователя shsh

Автор shsh, история, 19 месяцев назад, По-английски

In every virtual tree implementation I can find (https://en.oi-wiki.org/graph/virtual-tree/, https://codeforces.me/blog/entry/140066 , for instance), there seems to be an unnecessarily complex method to construct edges involving some kind of stack. The stack method used here is thankfully much simpler than both of these, but can't we simplify it even further to not use a stack at all?

That is, instead of:

for (int i = 1; i < (int)res.size(); i++) {
	while (tin[res[i]] > tout[stk.back()]) { stk.pop_back(); }

	vadj[stk.back()].push_back(res[i]);
	stk.push_back(res[i]);
}

(From the USACO Guide implementation)

We could just write:

for (int i = 1; i < (int)res.size(); i++) {
	vadj[lca(res[i - 1], res[i])].push_back(res[i]);
}

Is there any case in which this approach is wrong? I made this modification and still got accepted on the relevant AtCoder problem.

Edit: the usaco.guide module has since been updated, but I'm still not sure what advantage the second implementation on OI Wiki here has over the first one (which matches more closely with what I've described here), since both implementations seems to have O(n log n) runtime.

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

shsh orz

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

If you have the following complete binary tree with 7 nodes, indexed from top to bottom, left to right with 1..7, then if you want to build the virtual tree of the leaves, i.e. 4..7, you should get the entire tree, but with the bottom implementation, when you do lca(5, 6) = 1, you will add an edge from 1 to 6 which does not make it a tree anymore I think.

  • »
    »
    19 месяцев назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    However res is computed like so:

    vector<int> res = key;
    sort(res.begin(), res.end(), sort_tin);
    
    for (int i = 1; i < (int)key.size(); i++) {
    	res.push_back(lca(key[i - 1], key[i]));
    }
    
    sort(res.begin(), res.end(), sort_tin);
    res.erase(unique(res.begin(), res.end()), res.end());
    

    So in the case you mentioned, res = {1, 2, 4, 5, 3, 6, 7} and my implementation still works right?

»
19 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Consider a tree

1 2
2 3
2 4

And you try to build virtual tree on [1, 3, 4]. I think your algorithm will generate edges

1 3
2 4

However, we will expect

1 2
2 3
2 4
  • »
    »
    19 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Check my comment above; in this case res already contains all 4 nodes.

    • »
      »
      »
      19 месяцев назад, скрыть # ^ |
      ← Rev. 3  
      Проголосовать: нравится +10 Проголосовать: не нравится

      I think this means that your code differs a lot from normal implementation. Can you show the full implementation? It helps the discussion.

      • »
        »
        »
        »
        19 месяцев назад, скрыть # ^ |
        ← Rev. 2  
        Проголосовать: нравится 0 Проголосовать: не нравится

        In case you don't want to provide the full implementation. I think the one described in the Chinese OI-Wiki may be related.

      • »
        »
        »
        »
        19 месяцев назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Sorry, I should’ve specified better, but the code that I’m basing my implementation off of is the last USACO Guide link.

        • »
          »
          »
          »
          »
          19 месяцев назад, скрыть # ^ |
          ← Rev. 4  
          Проголосовать: нравится 0 Проголосовать: не нравится

          Ah I see. Sorry I miss that link.

          I think then it's unnecessary to maintain a stack there. You can check the first implementation in the Chinese OI-Wiki (not the en one) as I shared above.

          The code looks like

          int dfn[MAXN];
          int h[MAXN], m, a[MAXN], len;  // store key nodes
          
          bool cmp(int x, int y) {
            return dfn[x] < dfn[y];  // sort by the dfs order
          }
          
          void build_virtual_tree() {
            sort(h + 1, h + m + 1, cmp);  // sort key nodes by the dfs order
            for (int i = 1; i < m; ++i) {
              a[++len] = h[i];
              a[++len] = lca(h[i], h[i + 1]);  // insert lca
            }
            a[++len] = h[m];
            sort(a + 1, a + len + 1, cmp);  // sort every nodes on the virtual tree by the dfs order
            len = unique(a + 1, a + len + 1) - a - 1;  // remove duplicated
            for (int i = 1, lc; i < len; ++i) {
              lc = lca(a[i], a[i + 1]);
              conn(lc, a[i + 1]);  // connect the edge
            }
          }
          
          • »
            »
            »
            »
            »
            »
            19 месяцев назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            Oh, I didn't even notice there were two implementations on OI Wiki! Is there any advantage of the second implementation over the first one then? It seems strictly more complicated with no noticeable advantage.

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

If you are lazy to write O(1) LCA, maybe adding the extra constant factor factor to building virtual tree may not be good, idk. (Personally, I don't use O(1) lca often, it's not that much needed in every case.) Also, if the problem forces you to use O(N) memory, you need to use segment tree min queries for LCA, which will also give you log, thus by using the stack implementation you may save some constant factor. But obviosuly this is not very relevant...

»
19 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

This approach is correct, and OI-Wiki also introduces it as a naive approach before introducing the monostack approach.

The key is that you have to introduce either a much more complex algorithm like Four Russian to achieve a $$$O(n)\sim O(1)$$$ LCA, or an extra $$$\log$$$. By using a monostack you can build the virtual tree in $$$\Theta(n)$$$ without much coding.

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится -19 Проголосовать: не нравится

As the author of the USACO.guide article and a big fan of shsh, I'm honored that he optimized my code, and everyone can blame my stupidity for the inefficiency and confusion caused here.

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).