How to solve pretty boxes (PBOXES) from november long challenge

The question can be translated to -

Given a list of one dimensional arrays, what is the smallest range such that

there there is at least one element in each array that belongs to this list.

Check explanation here: https://www.geeksforgeeks.org/find-smallest-range-containing-elements-from-k-lists/

All the numbers present in the answer for K pairs will also be present in K + 1 pairs. Try to solve using this fact.

Based from what mnaveenkumar has said, you can easily derive a O(N ^ 2) greedy solution: Treat opening boxes as ‘(’ and ‘)’, and each time add another pair of ‘(’ and ‘)’ at positions i and j.

What is the conditon for this to be valid? If i < j it’s sure to be valid. Else, the minimum prefix sum between these positions have to be 1.

So now, solve the task for these 2 independently.

1st task: Find max of Aj - Ai with j > i in array, with updates removing numbers. This is an easy segment tree problem, so I’ll jump to the second one.

2nd task: Given an array initially consisting of 0s. Queries are:

- Add 1 to a range
- Delete 1 from a range
- For each consecutive range, find max(Ai) - min(Ai), and find max of this value over all ranges.
- Remove some element.

Simply build another segment tree with each node managing:

- Min of segment
- Answer to segment if every element is erased by the min.
- Longest prefix and suffix without a 0 if every element is erased by the min.

These 2 segment trees are enough to answer these questions, and the complexity is O(N * logN * logN)

Really nice Problem, this one; I felt like I had enough background knowledge to solve it, if only I was just that little bit smarter

No idea what techniques are needed for > 50pts on MDSWIN, though - presumably some kind of JIIT-style generating function shenanigans, or somesuch

Walsh Hadamard transform for XOR3 - FFT.

Well, of course!

Thanks! A bit of a surprise, that - I was expecting about 2150 or so(!)

You got a rank of under 40, it was obvious … I was too busy with other things this month, hope to join 6* club in December

Well, you certain don’t have far to go Looking forward to seeing a 6* next to your name this time next month

I want to join the club of 2 stars

I must say that you try hard to maintain your 1 star

Yes - your commitment to your gimmick is impressive - I salute you

you solved the last 3 problems of div1 in nov challenge(the toughest ones).just solve the easy ones ones for few challenges and become red(untrue to your handle)

He’s already a red coder, playing with us😉

He can lie about the university .

what is significance of this??can you please explain…

Can you explain in a more clear way, more explanatory way? I still couldn’t understand.