## Editorial for 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 of points, one can run a DFS for each query, and then obtain the 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 in and use a lookup table.

Time Complexity: , or

For an additional 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: or

For the final 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 , which is then multiplied by the standard time complexity of Mo's algorithm: . Note that it may be necessary to constant optimize the solution to pass.

Time Complexity:

• commented on Jan. 17, 2018, 12:05 p.m.

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

• commented on Jan. 17, 2018, 3: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.

• commented on Jan. 4, 2018, 7:04 a.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?

• commented on Jan. 4, 2018, 7:24 a.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.

• commented on Jan. 4, 2018, 8:01 a.m.

Good idea thanks.

UPD: I got it accepted after several optimizations. r3mark Can we have a look at a jury solution?

• commented on Jan. 4, 2018, 10:11 a.m.
• commented on Jan. 4, 2018, 2:01 p.m.

Thank you!

• commented on Jan. 3, 2018, 11:23 a.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?

• commented on Jan. 3, 2018, 11:39 a.m.

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

• commented on Jan. 3, 2018, 9:12 a.m.

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

• commented on Jan. 3, 2018, 12:35 p.m.

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

• commented on Jan. 2, 2018, 10:37 p.m.

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

• commented on Jan. 2, 2018, 11:34 p.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.

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

That is seriously so disappointing.

• commented on Jan. 3, 2018, 8:20 p.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.