Lain's blog

By Lain, history, 6 days ago, In English

The round is starting in around half an hour. Let's discuss the approaches here after it's done.

Good luck!

Read more »

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

By Lain, history, 3 months ago, In English

The above image is a problem from a recent hiring test by CodeNation. Any clues on how to solve it?

P.S. This test is over, it's been a couple days now

Read more »

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

By Lain, history, 4 months ago, In English

The Problem

I am trying to solve problem 1136E, where I need to find the lowest $$$pos$$$ such that $$$b_{pos} \geq b_i + x$$$. I generally use the lazy segment tree from the AtCoder Library, which is iterative. In a recursive segment tree, I could just move down the tree choosing the left or right node. How do I do this in an iterative segment tree?

My attempt

  int find_pos(int val)
  {
    int root = 1;
    while (root < size)
    {
      push(root);
      int l = 2*root;
      int r = 2*root+1;
      if (t[l].mx >= val)
        root = l;
      else
        root = r;
    }
    return root-size;
  }

Reference submission

This gives the wrong lower bound on some cases. I think it's because in the iterative case, it is not a clear tree, but rather a set of binary trees. Usually we move bottom up when calculating in an iterative segtree, so either it is not possible in an iterative segtree (without magic) or I have misunderstood something. Please let me know.

Read more »

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

By Lain, history, 6 months ago, In English

I was reading the editorial for 1136D, and solution 2 talks about a graph-based solution. I didn't completely understand it. I understood the graph they built(I think), and the answer is the number of unreachable vertices, but what is this "standard algorithm" called DFS by complement graph? I've never heard of it, and I just see a bunch of papers on Googling, which leads me to believe it isn't as standard as the editorialist claims it is. Also, if this is the standard definition of a complement graph, why is the graph described in the problem the complement of the provided graph? Is it assuming I remove all the edges where $$$v$$$ is behind $$$u$$$?

I've posted this blog since comments about the same on the editorial went ignored, so I hope this will reach more people. Thanks in advance.

Read more »

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it