MOU2H - Editorial

editorial
, , , ,
1

PROBLEM LINK:

[Practice][111]
[Contest][222]

Author: Vitalij Kozhukhivskij
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

You have a sequence of N elements H1,H2…HN. A climb is defined by the nonempty sequence (p1, p1+1), (p2, p2+1), …, (ps, ps+1), where pk+1 ≤ pk+1 for k = 1, 2, …, s − 1.
Two climbs, say (p1, p1+1), (p2, p2+1), …, (ps, ps+1) and (q1, q1+1), (q2, q2+1), …, (qt, qt+1) are different if and only if

  • s ≠ t or
  • There exists at least one k such that 1 ≤ k < min(s, t) and Hpk+1 – Hpk ≠ Hqk+1 – Hqk.

If you read the problem carefully and is thought over for sometime you’ll realise the basically what is asked for is number of different/distinct subsequences of the sequence H2-H1,H3-H2…HN-HN-1.

EXPLANATION:

So, our problem is reduced to: Given a sequence A1,A2…AN, find the number of distinct subsequences. Subsequence is a sequence that can be derived from sequence A by deleting some elements without changing the order of the remaining elements. Two subsequences are distinct if there length are different or some of the corresponding element is different.

dp[i] = Number of distinct subsequences ending with A[i].
sum[i] = dp[1] + dp[2] + … + dp[i]. So sum[n] will be our answer.
last[i] = last position of occurence of A[i] in the array A.

A null string has one subsequence, so dp[0] = 1.

for i=1 to N:
    dp[i]= sum[i-1] - sum[last[a[i]]-1]
    sum[i]=sum[i-1] + dp[i]
    last[a[i]]=i
print sum[n]

Initially, we assume we can append A[i] to all subsequences ending on previous characters, but this might violate the condition that the counted subsequences need to be distinct. Remember that last[A[i]] gives us the last position A[i] appeared on until now. The only subsequences we overcount are those that the previous A[i] was appended to, so we subtract those.

Using map in C++ to store last would have timed out. It was intentional. Also, take care of modulo operations.

ALTERNATIVE SOLUTION

If all elements in A are distinct, our answer will be 2N. Let’s say dp[i] stores the answer for array A_1 to A_i. Now, if there is some i<j such that A[i]==A[j], we should consider only last occurence of A[j] ie. at the index i. So we have to subtract the number of subsequences due to it’s previous occurrence.

This pseudo code will make it more clear:

dp[0]=1 // for length 0 the subsequences are 1
for i=1 to N:
    dp[i]=dp[i-1]*2
    if A[i] has occured last time at index j:
	dp[i]=dp[i]-dp[j-1]
print dp[n]

AUTHOR’S AND TESTER’S SOLUTIONS:

[Author’s solution][131]
[Tester’s solution][132]

Note: Editorial inspired from a post on stackoverflow.
[111]: http://www.codechef.com/problems/MOU2H
[222]: http://www.codechef.com/AUG14/problems/MOU2H
[131]: http://www.codechef.com/download/Solutions/2014/August/Setter/MOU2H.cpp
[132]: http://www.codechef.com/download/Solutions/2014/August/Tester/MOU2H.cpp

2 Likes
2

I used the same algorithm in Python.

http://www.codechef.com/viewsolution/4533860
http://www.codechef.com/viewsolution/4542578

and several other variations, all of them gave a TLE. Any suggestions as to what I can do to reduce the runtime so that it passes?

I can’t find a single Python AC out of all the submissions for this problem.

3

Nah, getting Python to do a serious O(N) algorithm with N=10^6 in less than several seconds is quite hard (at least in my experience). Moral lesson: when getting TLE in Python, ditch it and write the same in C++.

2 Likes
4

I did try C++ but I never really use it for competitive programming and kept getting segmentation error, I really need to practice with that.

Anyways, shouldn’t they raise the Python time limit so as to allow the submissions with acceptable time complexity? :\

5

In the tester’s solution, would you please explain a little bit more the thing done by this line?

int mem[8100000], *used = mem + 4001000;

I mean this kind of code is kinda new to me.

6

thank’s for the post .The solution is interesting

7

@incognito_103 >> in the above line, mem is declared as an int array of size 8100000 & used is a pointer to an int & it points to 4001000th location in mem array.Purpose of doing this is we can access used array using negative indices and it still remains as a pointer to a valid location in mem array.(in the above problem difference between two adjacent heights can be a minimum of -4*10^6 and maximum of 4*10^6, so we need an array of size at least 8*10^6 to access negative index of -4*10^6 and positive index of 4*10^6).

Illustrative Example(with smaller sized array):

say we declare an array named mem with size 3, and an int pointer to position 1 of mem(i.e. int* ptr = mem[1])

mem array:

0   1   2
----------
|  |  |  |
----------
    ^
    |
    ptr

So, this implies ptr[0] points to location 1 of mem array, ptr[-1] points to location 0 of mem array, ptr[1] points to location 2 of mem array.

accessing ptr[i] , i<-1

and ptr[i] , i>1 leads to array index out of bound runtime error.

8

@incognito_103 >> see below for answer (i wasn’t able to fit the answer in comment field).

9

In C++, using std::map may cause TLE, but using std::unordered_map will not. That is what you should be using anyways, since there is no need to maintain the elements in a sorted order.