How to solve pretty boxes (PBOXES) from november long challenge
1 Like
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: Find smallest range containing elements from k lists - GeeksforGeeks
1 Like
All the numbers present in the answer for K pairs will also be present in K + 1 pairs. Try to solve using this fact.
1 Like
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)
4 Likes
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
2 Likes
Walsh Hadamard transform for XOR3 - FFT.
3 Likes
Well, of course! 
1 Like
Thanks! A bit of a surprise, that - I was expecting about 2150 or so(!)
1 Like
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 
3 Likes
Well, you certain don’t have far to go Looking forward to seeing a 6* next to your name this time next month
1 Like
I want to join the club of 2 stars 
2 Likes
I must say that you try hard to maintain your 1 star 
1 Like
Yes - your commitment to your gimmick is impressive - I salute you
2 Likes
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😉
5 Likes
He can lie about the university .
1 Like
what is significance of this??can you please explain…
1 Like
Can you explain in a more clear way, more explanatory way? I still couldn’t understand.