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!
Congrats @ssjgz for 6 star !
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😉
must be some red/orange code in this list-https://codeforces.com/ratings/organization/2393
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.