Pretty boxes (PBOXES) from november long challenge?

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: https://www.geeksforgeeks.org/find-smallest-range-containing-elements-from-k-lists/

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 :slight_smile:

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

2 Likes

Walsh Hadamard transform for XOR3 - FFT.

3 Likes

Well, of course! :wink:

1 Like

Congrats @ssjgz for 6 star !:slightly_smiling_face:

2 Likes

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 :wink:… I was too busy with other things this month, hope to join 6* club in December :joy:

3 Likes

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

1 Like

I want to join the club of 2 stars :frowning:

2 Likes

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

1 Like

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

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

must be some red/orange code in this list-https://codeforces.com/ratings/organization/2393

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.