Editorial for Nightmare-a-thon


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

This problem was quite challenging for the junior level (thank Timothy Li), but the solution is super cool! Because of the high bounds on N, we needed \mathcal{O}(1) or \mathcal{O}(\log N) time complexity queries to pass. The easiest solution is in \mathcal{O}(1) time. Let's break this problem down into the two parts of its queries. The first part asks for the highest rated episode not within the range a - b. This is very difficult because it is hard to do anything from the middle or an array. How do we change this problem to make it easier for us? Well, the query is basically asking us the highest rated episode from episode 1 to episode a-1, or from episode b+1 to episode N, right? Now, to find the highest from episode 1 to episode a-1, make a maximum array, sweep through the episodes left to right, keeping track of the highest rated episode we've found so far in your max array. Similarly, for episodes b+1 to N, keep a second maximum array, sweep through the episodes right to left, keeping track of the highest ep. we've found so far. An example of this:

Episodes:  1 3 2 4 3 5 2
Maxleft:   1 3 3 4 4 5 5
Maxright:  5 5 5 5 5 5 2

Now, to find the highest rating not within episodes a and b, simply take the max between maxleft[a-1] and maxright[b+1].

The second part of the query can be solved in conjunction to the first. Create 2 more occurrence/frequency arrays. Whenever you update your maximum array to a higher rating, the occurrences of high should be set to 1 (since this new high is the only one you've found!). Whenever you find an episode that has equal rating to your previous high, the occurrence at that index should equal the occurrence at the previous index + 1. Otherwise, the occurrence at the current index should equal the occurrence at the previous index. An example iterating from the left side:

Episodes:  1 3 2 4 4 5 2
Maxleft:   1 3 3 4 4 5 5
Freqleft:  1 1 1 1 2 1 1

Now, to answer the second part of the query, we need to consider a few cases. If the left side max is greater than the right side max, we need to take the occurrences of the left side max (aka Freqleft [a-1]). Similarly if right side max > left side max, we take Freqright[b+1]. However, if left side max == right side max, we need to find the combined occurrences of this number in both left side and right side, thus we take FreqReft[a-1] + FreqRight[b+1]. The official solution in Python 2 is below.

import sys
raw_input = sys.stdin.readline

n,q = map(int,raw_input().split())
ep = map(int,raw_input().split())
dpl = [0 for i in xrange(n)]
freql = [0 for i in xrange(n)]
dpr = [0 for i in xrange(n)]

freqr = [0 for i in xrange(n)]
dpl[0] = ep[0]
dpr[-1] = ep[-1]
freql[0] = freqr[-1] = 1
for i in xrange(1,n):
    if ep[i] > dpl[i-1]:
        dpl[i] = ep[i]
        freql[i] = 1
    elif ep[i] == dpl[i-1]:
        dpl[i] = dpl[i-1]
        freql[i] = freql[i-1] + 1
    else:
        dpl[i] = dpl[i-1]
        freql[i] = freql[i-1]
for i in xrange(n-2,-1,-1):
    if ep[i] > dpr[i+1]:
        dpr[i] = ep[i]
        freqr[i] = 1
    elif ep[i] == dpl[i+1]:
        dpr[i] = dpr[i+1]
        freqr[i] = freqr[i+1] + 1
    else:
        dpr[i] = dpr[i+1]
        freqr[i] = freqr[i+1]

dpl = [0] + dpl + [0]; freql = [0] + freql + [0] ## pad with zeroes
dpr = [0] + dpr + [0]; freqr = [0] + freqr + [0] ## to make life easier

for i in range(q):
    a,b = map(int,raw_input().split())
    maxi = max(dpl[a-1],dpr[b+1])
    if dpl[a-1] == dpr[b+1]:
        cnt = freql[a-1] + freqr[b+1]
    elif dpl[a-1] > dpr[b+1]:
        cnt = freql[a-1]
    else:
        cnt = freqr[b+1]
    print maxi,cnt

Comments

There are no comments at the moment.