MAXPR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

Easy

PREREQUISITES:

dynamic programming, simple combinatorics.

PROBLEM:

Given an array A. You have to find number of sub-sequences of A which are not arithmetic progressions(AP).

EXPLANATION

As total number of sub-sequences in the array A will be 2 n (including the empty sequence),
Excluding the empty sequence, we will have 2 n - 1 sub-sequences.

So instead of finding number of sequences which are not arithmetic progressions, we will find number of sequences which are
arithmetic progressions and subtract it from 2 n - 1.

Terminology

AP is defined as a series of a, a + d, a + 2 * d, etc.
By difference of AP we mean d.

Number of APs in an array A

Notice the following the observation.

  • Elements of the array lie between 1 to 100 inclusive.
  • Due to previous condition, maximum difference of AP can be at most 100.
  • Similarly, minimum difference of AP can be at most -100.

So the values of elements of the array are small. We will make use of this observation.
Let us say we iterate over the difference of the AP and try to count number of APs in the array having the given difference.

Number of APs having difference d in an array A

We will solve this problem by dynamic programming. Let dp[i] denote the number of AP’s ending at i and having difference equal to d.
So if our current number is equal to A[i], we need to
find all the positions j < i such that A[j] = A[i] - diff and we will take sum of dp[j] for those j’s. It is equivalent to extending the
APs ending at position j with the element at position i.

Hence dp[i] = 1 + sum_(j = 1 to i - 1) dp[j] such that A[j] = A[i] - diff

We are adding 1 for the case when our current number is the only number in the AP. (1 element is also an AP according to problem statement.)

Naively computing the above recurrence will take time equal to O(N 2 ) which is not going to pass in the given time. We need to optimize this.

Note that we can optimize this by maintaining a sum array where sum[x] will record sum of all the dp’s where the value of array elements was x.
Mathematically speaking, sum[x] = sum of all dp[i]'s such that A[i] = x.

After this, our dp will be.

Hence dp[i] = sum[A[i] - diff] + 1.

Now with this optimization, our dp computation will take O(N) time.

Note that we are doing slight over-counting in the APs of just one element. Each iteration of diff will count A element APs, Hence it will
amount to over-counting. For that we can simply remove n single elements APs in the iteration over diff variable. In the end, we can simply
add the n 1 element APs.


// I have not included mod operations in pseudo code, don’t forget to include them.
pseudo code:

ans = 0

for diff = -100 to 100:
	make an array sum of size 100.
	cur = 0
	for i = 1 to N:
		if (A[i] - diff >= 1 and A[i] - diff <= 100):
			// fetch the content from the sum array.
			dp[i] = sum[A[i] - diff] + 1
		// update the sum array.
		sum[A[i]] += dp[i].
		cur += dp[i]
	
	// Now we need to remove 1 element APs, 
	// because each iteration of diff will count 1 elements AP, hence it will lead to over counting.
	ans += cur
	ans -= n

// Now add the 1 elements AP
ans += n

// For finding non APs, subtract from 2^n - 1
ans = 2^n - 1 - ans.

Complexity

Overall complexity is O(200 * N).
As 200 is the maximum possible value of difference of arithmetic progression because each number lies in the range [1, 100].
For each difference value of AP, we are just doing a single pass over the array A, Hence O(N) time.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

14 Likes

slight error: make it 2^n-1 instead of n^n -1.

8 Likes

Please update the links to Author’s and Tester’s solution.

it should be 2^n instead of n^n.
There are only two ways a number in the array can go: it can either be in any subsequence or not. this is the case with all the numbers. multiplying 2 upto n gives us all the possible subsequences.

6 Likes

that’s not a “slight error” !!!

1 Like

Well in mathematical terms, no, but i merely meant it in terms of the number of characters he got wrong.

I used the same logic,but it was giving TLE. So i had to use fast IO in order to get AC. Also my solution after using fast IO gave TLE when when submitted in C++ 4.3.2 while gave AC in C++ 4.8.1 . What could the
reasons for this?

5 Likes

The complexity given is for a single test case .

My O(200*N) solution using the same principles as mentioned in the editorial got TLE. I don’t understand why solutions only slightly better in terms of the constant factors deserved to get accepted and others don’t. Does the author have a purpose on having such a strict time limits or is it just another badly designed question?

1 Like

there is also O(100*N) solution. This can be done in a much faster way.
You can make it even more faster by fast exponentiation.
So, the time limit is not strict at all

if you change the looping order, you can have a O(100*N) solution.

4 Likes

I too have used the same logic (O(n)*100), but it was getting TLE during the contest. It will be really disappointing to know that apart from this logic, this question required the use of Fast IO.

Many solutions including my solution gave TLE even after we followed the method described above.
This is mainly because of 2 reasons.

  1. Some of us haven’t used fast i/o.
  2. We have used mod a lot of times.

Did the second point confuse you?
Then just look at my solutions.

  1. http://www.codechef.com/viewsolution/4032512
  2. http://www.codechef.com/viewsolution/4106416

The first one is without using if condition while using mod and it gave TLE while the second solution has OPTIMIZED the usage of MOD and hence it got accepted.

I was literally frustrated when I realized that even a MOD could result in TLE.

I sincerely request codechef to go through all the TLE solutions again and increase the time limit of the question if possible, so that such solutions are accepted.

3 Likes

@dpraveen what was the benefit of choosing limit of N as 2*10^5 instead of 10^5?

It is due to the way compiler works…

i also asked for the same here:

http://discuss.codechef.com/questions/44751/c11-just-a-pretty-face

@sansid There were many more optimisation that remove tle
like summing up the ans after all operation would be 100*200 which is 10 times faster than doing it after each modification.
Also you can use int here instead of long long. Using int my time was reduced by half.

long long int was giving me tle…changing to int gives AC

2 Likes

The time complexity should not depend upon the usage of int/long long int. Ideally the questions should focus on algorithmic or logical details rather than other things.

4 Likes

@dpraveen i am not able to understand why “sum” array is not set to 0 for each diff in the psuedo-code. Someone please explain this because even in editorial it is not mentioned that sum should be set to 0 for each diff, but sum[x] is supposed to contain sum of dp[i]'s such that A[i]=x for a particular value of diff.

the recursive dp was giving me TLE. changing it to a bottom up implementation got me AC

//