cppAcademy
FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP B2017 · MediumSubsequence dynamic programming

Counting Arithmetic Subsequences

National Olympiad — Regional round (2017 season)

Submission name: progres.cpp

Solve in Editor →

Problem summary

Count position-distinct subsequences of length at least two forming a strictly increasing arithmetic progression, modulo 123456789012345.

Input

N and N positive integers.

Output

Number of arithmetic subsequences modulo the given modulus.

Constraints

1 < N < 1000; 1 ≤ value ≤ 1000.

Worked example

An independently prepared example for this explanation.

Input

3
1 2 3

Output

4

Solution analysis

  1. Let dp[i][d] count arithmetic subsequences of length at least two that end at position i with positive common difference d. Differences can only be 1…999.
  2. For each earlier j with a[j]<a[i], set d=a[i]−a[j]. Append a[i] to every subsequence counted by dp[j][d], and also count the new two-element subsequence (j,i). Add dp[j][d]+1 to dp[i][d] and to the answer.
  3. For 1,2,3, the pairs (1,2),(2,3),(1,3) contribute three sequences, and extending (1,2) produces (1,2,3), giving four. Equal-valued positions are separate choices but never form a positive-difference pair.

Why it works

Every counted progression has a unique penultimate position j and positive difference d. Removing its last element leaves either a one-element prefix, counted by the added one, or a progression counted by dp[j][d]. These cases are disjoint, so the recurrence counts each legal position sequence once.

Complexity: O(N²) time and O(1000N) space.

Watch out. Subsequences need not be contiguous. Equal value sequences at different positions count separately. Exclude d=0 and reduce every addition modulo the specified 15-digit modulus.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
// Algorithm: Let dp[i][d] count arithmetic subsequences of length at least two that end at
// position i with positive common difference d.
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int&value:a){
        cin>>value;
    }
    const long long mod=123456789012345LL;
    vector<vector<long long>>dp(n,vector<long long>(1000,0));
    long long answer=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<i;++j){
            int difference=a[i]-a[j];
            if(difference<=0){
                continue;
            }
            long long added=(dp[j][difference]+1)%mod;
            dp[i][difference]=(dp[i][difference]+added)%mod;
            answer=(answer+added)%mod;
        }
    }
    cout<<answer<<'\n';
}

Source: Arena Olimpiici ↗