int count(int N, int K){
dp[0][0] = 1;
for(int i = 0; i < N; i++){
for(int j = 0; j <= K; j++){
for( int a = 0; a <= i; a++){
print(N,K);
if(j+a*(i-a) > K || dp[i][j] == 0){ continue;}
dp[i+1][j+a*(i-a)] += dp[i][j];
dp[i+1][j+a*(i-a)] %= MOD;
}
}
}
return dp[N][K];
}
Help me with dis dp code, I can't undestand. https://community.topcoder.com/stat?c=problem_statement&pm=14304
Let DPij denote the number of permutations using first i numbers with exactly j lo-hi-lo triples. Then for the ith number, we can try to put it anywhere in one of the i positions.
If we put it in the starting position or ending position we won't get any lo-hi-lo triple as contribution to the answer.
If we put it in some other place, say after p elements, then we get a contribution of p * (i - 1 - p) to our answer. And you will update DP[i][j] + = DP[i - 1][j - p·(i - 1 - p)].
The first part I understand, but when you said, "we can try to put it anywhere in one of the i positions.", it is a lo-hi-lo triples?, second, "If we put it in the starting position or ending position we won't get any lo-hi-lo triple as contribution to the answer", in this case is possible to contribute for the answer, example {1,2,3} => {2,3,1}. Scuse me, if I don't undestand.
Suppose we already know the answer for for i - 1, and now we need to know the answer for ith index. We can put the ith element anywhere in one of the i positions in a permutation of i - 1 elements, to get a permutation of i elements.
For eg if we have a permutation of 3 elements A, B, C. We can put the 4th element in 4 positions and the new permutations are — (D, A, B, C), (A, D, B, C), (A, B, D, C), (A, B, C, D).
Now notice that when we put them in first or last position we do not get any additional lo-hi-lo triples because D is greater than all elements and it is at starting or ending position.
When we put it after p elements, we get p * (i - 1 - p) more lo-hi-lo triples.