Editorial for New Year's '18 P6 - Old Christmas Lights II


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

For 10\% of points, one can run a DFS for each query, and then obtain the c_i values for each node on the path. Comparing each pairwise answer would then yield the answer to the query. Alternatively, one can precompute the answer for each possible pair u_i, v_i in \mathcal O(N^3) and use a lookup table.

Time Complexity: \mathcal O(QN^2) or \mathcal O(N^3 + Q)

For an additional 10\% of points, we can optimize the algorithm for finding the minimum difference by sorting the array; the minimum difference will be between two adjacent elements.

Time Complexity: \mathcal O(QN \log N) or \mathcal O(N^2 \log N + Q)

For the final 80\% of points, we can use Mo's Algorithm on a tree. Firstly, flatten the tree into its Euler Tour. Then each query can be expressed as a query over a contiguous subarray, with all nodes that appear twice not being counted. See this Codeforces blog post for more details on Mo's on a tree. Following this, we can use a balanced binary search tree or segment tree to keep track of which brightness values have appeared, and find the minimum difference. Updating this data structure takes \mathcal O(\log N), which is then multiplied by the standard time complexity of Mo's algorithm: \mathcal O((N+Q) \sqrt N). Note that it may be necessary to constant optimize the solution to pass.

Time Complexity: \mathcal O((N+Q) \sqrt N \log N)


Comments


  • 1
    xyz2606  commented on Jan. 17, 2018, 5:05 p.m.

    Why do you set the time limit to 10s when Author's solution using already 9s?


    • 2
      Kirito  commented on Jan. 17, 2018, 8:01 p.m.

      Originally time limit was going to be a bit higher, but when testing, Eliden was able to solve the problem in <5s per test case, so we kept it at 10.


  • 0
    magieNoire  commented on Jan. 4, 2018, 12:04 p.m.

    I have problems getting the last batch run under the given time limit. I have used segment tree and still fails on large test cases. What kind of optimizations can I do ?

    Also how can we use multiset instead of segment tree?


    • 2
      triple1  commented on Jan. 4, 2018, 12:24 p.m.

      I used 2 multisets. Multiset 1 stores the values of nodes. Multiset 2 stores difference of adjacent values in multiset 1. Whenever an element has to be added, at most 2 new differences emerge. These differences are added in multiset 2. We handle similarly when an element is removed. For each query, the answer is the first element of multiset 2.

      Try changing block size. I initially kept in sqrt(N), and it didn't pass. When I had set it to 500, it got passed.


  • 0
    triple1  commented on Jan. 3, 2018, 4:23 p.m. edited

    I have solved this problem. I wanted to have a look at the test cases of the last subtask. Can I access the test cases, if it doesn't violate any rules?


    • 2
      Kirito  commented on Jan. 3, 2018, 4:39 p.m. edited

      You are welcome to contact us on Discord, since the cases are not public. My handle on Discord is kirito.feng#3920.


  • 0
    ivan100sic  commented on Jan. 3, 2018, 2:12 p.m.

    I used a segment tree and still got TLE! Are you kidding me?


    • 1
      r3mark  commented on Jan. 3, 2018, 5:35 p.m.

      :( A larger block size (~800) ACs your most recent submission.


  • 0
    SamZhangQingChuan  commented on Jan. 3, 2018, 3:37 a.m.

    Could you plz elaborate on how to do constant optimization? I had exactly the same algo and complexity but got TLEd...


    • 0
      r3mark  commented on Jan. 3, 2018, 4:34 a.m.

      It seems you've realized this already but anyways: using a multiset is likely to TLE as the constant factor is fairly high (though some people still passed using multiset and somehow the fastest submission uses multiset???). A segment tree approach should pass without any optimizing.


      • 2
        ivan100sic  commented on Jan. 3, 2018, 8:21 p.m.

        That is seriously so disappointing.


        • 2
          pmnox  commented on Jan. 4, 2018, 1:20 a.m.

          I updated my solution based on xyz111 idea. I also used segment tree. This allows me to get 0.4s/10s on the worst case. In the end my solution is 4x faster than the one used by xyz111.