Hello Fellow Coders!

Whether it is coding or solving problems in real life, we Coders know it well and Institute of Engineering and Management believes in these skills and want to be the part of this movement to bring more and more people under the umbrella of competitive programming. So again on 11-11 Institute of Engineering and Management,SaltLake, India is organising IEMCO for **6th** time, with prizes worth **50,000** INR up for grab.

Contest Details: Time: 11th November, 2018, 8 PM to 11 PM. Contest **Link**: IEMCO6

Registration: Create a team of upto 3 members on codechef and Register yourself. **Prizes:Prizes worth 50,000 INR up for grab.**

All the Best!!! See you in the contest. Keep Coding, Keep Solving!!!

How to solve Magic Warehouse (IEMCO6B)?

Looks like constrains for "Perfect Pair" were wrong (

n> 10^{4}actually), awesome contest, innovative tasks, really enjoyed it!!!!!Which all questions did you feel innovative?

maybe he is about nontrivial segment tree applications O_o

Do you feel application of seg tree in perfect pairs is non trivial?

It's a sarcasm, Sheldon!!!

Here is my mini editorial for this contest. (Note A D E F B C)

A. Write K's first, then write non-K non-M's, then write M's.

D. We want the maximum sum subarray of 1s and -1s. Using prefix sums, we need to maximize P[j] — P[i] for j > i. For each i in decreasing order, we can remember the largest P[j] we've seen.

E. Straightforward using a Trie.

F. Use a DFS to create the tour. Now you want to make RMQ queries in the standard way.

B. DP on (i, prev), where prev is the value of the box to the left of the ith box. Either we swap or we don't.

C. Create the perfect number array. Since the largest square is at most 2 * max(A), there are only 1200 of those, so it is at most O(1200) to check. Once we have the array P[i] = x, we essentially have intervals (i, x) [or (i, INF) if x is -1]. Now for a query (qL, qR), we want to know how many intervals B are contained completely in interval [qL, qR]: the answer then would be qR-qL+1-B. We can use a merge sort tree.