sid55's blog

By sid55, history, 5 years ago, In English

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!!!

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

How to solve Magic Warehouse (IEMCO6B)?

»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Looks like constrains for "Perfect Pair" were wrong (n > 104 actually), awesome contest, innovative tasks, really enjoyed it!!!!!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Which all questions did you feel innovative?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      maybe he is about nontrivial segment tree applications O_o

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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.