Lets share our approaches for the problems here while editorials for problems come out (at this moment none n̶o̶t̶ ̶a̶l̶l̶ of them are out)? Got any interesting approach which you cant wait to share? The wait is over
So, which was your favourite problem? I struggled with Power Tree.
ANDSQR was a pretty simple problem. We can see for a specific L, there are at most 30 different ranges that will produce different values. Only store ranges that produce a square.
Now our task is answering for a [L…R]. Simple, sort all queries by their right border. Keep moving and update
all the Ls on the way. For a L there are at most 2 cases:
R doesn’t lie in any range of it. In this case we can simply add all the found ranges of the L in our answer
R lies in a range. Then we see the answer is R - range_L + 1. This can be found by storing 2 other values in the segment tree: Total of range_L and the number of Rs we need (Number of opening ranges). Then obtain the answer is simply sum_prev_range + cntR * (R + 1) - sum_L.
Complexity: Updating for a new R takes O(logA), and answering a query takes O(logN). So the total complexity is O(NlogA + QlogN), which will pass easily.
I solved both BSHUFFLE and TABGAME after observing patterns in the test cases. I did not get an intuitive explanation for either (maybe for TABGAME). Interested to see the editorial.
I don’t understand why good problems do not get editorials. Waiting for the editorial of SAFEPAR(AUG18) till now and again for this contest too :(. I think many people dislike this part about the challenge.