MAXPR - Editorial

combinatorics
dynamic-programming
easy
editorial
june14
maxpr

#1

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* denote the number of AP’s ending at i and having difference equal to d.
So if our current number is equal to A*, we need to
find all the positions j < i such that A[j] = A* - 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 = 1 + sum_(j = 1 to i - 1) dp[j] such that A[j] = A* - 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*'s such that A* = x.

After this, our dp will be.

Hence dp* = sum[A* - 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* - diff >= 1 and A* - diff <= 100):
			// fetch the content from the sum array.
			dp* = sum[A* - diff] + 1
		// update the sum array.
		sum[A*] += dp*.
		cur += dp*
	
	// 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


#2

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.


#3

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?


#4

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?


#5

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


#6

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.


#7

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.


#8

For large common differences d, I do things a bit differently.

Let MAX be the maximum and MIN be the minimum. If |d| > (MAX-MIN)/2, then the length of the arithmetic subsequence is at most 2—any more than that and you’ll get a number larger than MAX or smaller than MIN. Therefore, the number of arithmetic subsequences with absolute common difference d is equal to ∑ C(x)C(x+d) for MIN ≤ x ≤ MAX-d, and C(x) is the number of indices in the array with value x.

The values C(x) can be precalculated in the beginning of a test case in O(N), and for a particular d with |d| > (MAX-MIN)/2, the sum can be calculated in MAX-MIN ≤ 100 operations.

If |d| ≤ (MAX-MIN)/2, we do the same DP approach as in the editorial. But now we’ve cut the runtime in half!


#9

Can you tell me why code is getting WA…
I used the same algorithm as you have told in ur editorial but still WA…
Soln link :-- http://www.codechef.com/viewsolution/4107416

Thnx in advance…


#10

DP always cripples my mind…


#11

I am getting WA again n again. Can someone please point out why my solution is wrong ?
http://www.codechef.com/viewsolution/4108001
Thanks


#12

Can somebody please into my solution.Used the exact same algorithm. Pairs to store the difference and the index. http://www.codechef.com/viewsolution/4101901. Thanks in advance


#13

Even after implementing the above idea and keeping the number of mod equations and variables of type LongLongInt at minimum, still getting TLE.
Please suggest corrections.

[http://www.codechef.com/viewsolution/4109359][1]
[1]: http://www.codechef.com/viewsolution/4109359


#14

In the editorial,dp* means all those AP which are ending at ith digit,suppose we consider the sequence 1 2 3
than
dp[1]=1,
dp[2]=1+dp[1]=2,
dp[3]=1+dp[2]+dp[1]=4,
so total numbers of AP which are ending at the i the digit are 4 but we are having {1},{2},{3},{1,2},{2,3},{1,3},{1,2,3} =7 AP’s.Can anybody explain it??


#15

can anyone see why am i getting WA

int t,n;
cin >> t;
while (t–) {
cin >> n;
vi was(n);
vi occ(111,0);
for (int i = 0; i < n; i ++) cin >> was*;
vvl dp(111,vl(222,0));
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
int curr = was*;
for (int j = -99; j <= 99; j++) {
int prev = curr - j;
if (1 <= prev && prev <= 100) {
//addmod(dp[curr][j+99],dp[prev][j+99]);
dp[curr][j+99] = (dp[curr][j+99] + dp[prev][j+99]) % MOD;
if (curr != prev) {
//addmod(dp[curr][j+99],occ[prev]);
dp[curr][j+99] = (dp[curr][j+99] + occ[prev]) % MOD;
}
}
}
occ[curr]++;
//addmod(dp[curr][0+99],1);
dp[curr][0+99] = (dp[curr][0+99] + 1) % MOD;
}
ll res = 0;
/for (int i = 1; i <= 2; i++) {
for (int j = -1; j <= 1; j++) {
cout << dp
[j+99] << " ";
}
cout << "
";
}
/
for (int i = 0; i <= 100; i++) {
for (int j = -99; j <= 99; j++) {
res = (res + dp
[j+99]) % MOD;
}
}

ll pos_seq = power(2,n);
res = (pos_seq - res) % MOD;
cout << res << "

";
}


#16

why the difference is varying from -100 to 100… i can see the maximum difference should be +99 and minimum should be -99… can anyone explain ?


#17

Can someone please give more test cases …


#18

Can someone please give more test cases …


#19

hi.i tried a different algo which gives the same answer as one of the correct submission gave.but codechef gives a WA wrong answer to my code.someone please help me…
this is my code…i can explain the algo…iknow only 1 or 2 test cases are going wrong
http://www.codechef.com/viewsolution/4120150


#20

i really didnt get the optimization… if some one can explain it using kinda small dp table that will be really very very grateful… till now i understood that dp[n]= summation_d=-100 to 100 (dp[n-1][d]); cant understand the optimization