MAXPR - Editorial

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

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

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. CodeChef: Practical coding for everyone
  2. CodeChef: Practical coding for everyone

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

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!

2 Likes

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 :-- CodeChef: Practical coding for everyone

Thnx in advance…

DP always cripples my mind…

4 Likes

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

Can somebody please into my solution.Used the exact same algorithm. Pairs to store the difference and the index. CodeChef: Practical coding for everyone. Thanks in advance

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.

[CodeChef: Practical coding for everyone][1]
[1]: CodeChef: Practical coding for everyone

In the editorial,dp[i] 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??

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[i];
vvl dp(111,vl(222,0));
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
int curr = was[i];
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[i][j+99] << " ";
}
cout << “\n”;
}
*/
for (int i = 0; i <= 100; i++) {
for (int j = -99; j <= 99; j++) {
res = (res + dp[i][j+99]) % MOD;
}
}

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

}

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 ?

1 Like

Can someone please give more test cases …

Can someone please give more test cases …

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

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

My solutions seems to work for the inputs I give, but I’m getting WA as the result when I submit. Can someone please help? Here’s a link to my solution:
CodeChef: Practical coding for everyone

I am getting WA in the following code. I tried most of the possible test cases and it is giving the correct answers but getting WA still. Can someone help me, what I am missing ?

Thanks in advance :slight_smile:

link to code : CodeChef: Practical coding for everyone