Count the number of arithmetic progressions within a sequence

Question

I have some problems with code for my classes. Even though it works correctly, I run out of time for half of the examples. Here's the task (I really did my best trying to translate it):

You have a permutation of numbers 1,2,...,n for some n. All consecutive numbers of permutations together create sequence a₁, a₂, a₊. Your task is to count how many arithmetic substrings of length 3 are present.

Input: In first line there is a number n (1 <= n <= 200 000). In the second line there is n numbers a₁, a₂, a₊ representing our permutation.

Output: The program needs to print out amount of arithmetic substrings of length 3 for permutations from entry. You can assume that the result won't be bigger than 1 000 000.

NOTE: arithmetic substrings most likely stand for arithmetic progression or something like that

#include <iostream>
using namespace std;

int main() 
{
    int input_length;
    cin >> input_length;
    int correct_sequences = 0;
    
    bool* whether_itroduced = new bool[input_length + 1]{0}; // true - if number was already introduced and false otherwise.
    
    
    for (int i = 0; i < input_length; i++)
    {
        int a;
        cin >> a;
        whether_itroduced[a] = true;
        int range = min(input_length - a, a - 1); // max or min number that may be in the subsequence e.g. if introduced number a = 3, and all numbers are six, max range is 2 (3 - 2 = 1 and 3 + 2 = 5, so the longest possible subsequence is 1, 3, 5)
        
        for (int r = range * -1; r <= range; r++) // r - there is a formula used to count arithmetic sequences -> an-1 = a1-r, an = a1, an+1 = a1+r, I have no idea how to explain it
        {
            if (r == 0) continue; // r cannot be 0
            
            if (whether_itroduced[a - r] && !whether_itroduced[a + r])
            correct_sequences++;
            
        }
    }
    cout << correct_sequences;
}

example input: 5 1 5 4 2 3

correct output: 2 // {1,2,3} and {5,4,3}

example input: 5 1 2 3 4 5

correct output: 4 // {1,2,3} {2,3,4} {3,4,5} {1,3,5}

example input: 10 1 5 9 7 4 3 6 10 2 8

correct output: 4 // {4,3,2} {1,5,9} {5,4,3} {4,6,8}

I need to somehow come up with another algorithm that is less than quadratic in time. I can't really see all of the inputs and correct outputs, but I know that the biggest 'n' number is about 32000, so it's most likely that I run out of time because of the algorithm. Do you have any ideas about how can I improve it and make it work faster? Thanks for help!

EDIT: I found a guide explaining how to make the algorithm work quicker. Unluckily, I still have no idea how to write the code as the guide seems very unclear for me. Here's the guide:

Let’s say that x_1 is the smallest positive number, such that l_(ai-x1)≠l_(ai+x1) and l_(ai-y)=l_(ai+y) for 1 <= y < x_1. Then, the word created by l_(ai-x1+1), l_(ai-x1+2), ... , l_(ai+x1-1) is a palindrome, so a word l_(ai-x1+1), ... , l_ai is the same as word l_(ai+x1-1), ... , l_ai. Let’s say that x_2 is the smallest positive number, such that l_(ai-x2)≠l_(ai+x2) and l_(ai-y)=l_(ai+y) for x_1<y<x_2. Then, the word created by l_(ai-x2+1), l_(ai-x2+2), ... , l_(ai-x1-1), l_(ai+x1+1), ... , l_(ai+x2-1) is a palindrome. Also, you can define x_3, x_4, ... , x_k for some non-negative k (we assume, that x_(k+1) doesn’t exist). Considering the above definitions of sequence x_1, ... , x_k, we can assume, that the only arithmetic substrings of length 3 and a_i as a middle element, are a_i-x_j,a_i,a_i+x_j for 1 <= j <= k. If we could quickly compare two coherent subwords of words or subwords after reversal (it doesn’t make any sense in my language too), words l_1, l_2, ..., l_n, then using binary search, we would have been able to search for numbers x_1, ..., x_k. The structure allowing us to both compare coherent subwords of words and to update letters of word, is interval tree, in which we will store hashes (you can identify letters from words with positive numbers). In the apex, corresponding to some consistent subword l_a, l_(a+1), ..., l_b, there will be a hash of this subword h_([a,b])=l_a*p^0+l_(a+1)*p^1 + ... + l_(a+x)p^x+ ... + l_bp^(b-a). Changing the letter in a word and updating the tree is simple. We begin by changing the value in the leaf and for vertex values, which are not leaves and do have sons (?) responsible for compartment [a, a+x-1] and [a + x, a + 2x – 1] the new hash will be equal to h_([a,a+x-1])+h_([a+x,a+2x-1])*p^x. The update works in O(log n) time, assuming that we will remember all previous powers of p. To count the hash of a subword starting at a-th position and ending at b-th position, first break the interval [a,b] into base intervals. Let our base intervals be [a,c₁], [c₁+1,c₂], . . . . , [cₖ+1,b]. The hash of our word is: h[a,c₁]+h[c₁+1,c₂]*p^(c₁-a)+. . . +h[cᵢ+1,cᵢ+1]*p^(cᵢ-a)+. . . +h[cₖ+1,b]*p^(cₖ-a). Thus, one can count the hash of any consistent subword in O(log n) complexity. // base intervals - when we want to answer a query about the maximum on the interval [a,b], we need to find some set of partial intervals represented by the nodes of the interval tree. Such smaller intervals are called base intervals. Once we have the base intervals, we can reach into the tree and take the maximum from the values stored in the nodes corresponding to the base intervals, thus obtaining the result of the entire query// To use the presented structure in our task, we need two copies of it. We will keep the normal word in one binary tree and the reversed word in the other binary tree. This will allow us to arbitrarily compare both normal and inverted subwords. The entire algorithm has a computational (time) complexity of O(n log² n + m log² n) (or O(n log n + m log² n) if we apply a small optimization - we check if a word is not a palindrome before we start looking for all words xᵢ) and computational memory (space) complexity O(n).

Note: of course, indexes I have written in Word didn't survive, so here's screen from Word: https://i.sstatic.net/laT2N.jpg Guess that it's not worth your time to fix all those indexes.

Answer 1

There's some straightforward and common C++ problems immediately obvious:

• using namespace std; - avoid that; it makes your code more fragile. It doesn't even make it shorter!

• Streaming input without checking. If you use >>, it's essential to only use the value if it was actually written. For a simple program like this, it's easiest to just set std::cin to throw exceptions when it fails.

• We used std::min without including <algorithm>. Include the documented headers; it's unsafe to assume that all compilers will transitively include the same ones as yours does.

• Failure to delete[] storage allocated with new[]. Prefer smart pointers or containers whenever possible.

• Use of int for counting where an unsigned type would be more appropriate.

• Use of int where it might not have sufficient range (INT_MAX only has to be 32867, but we expect values in the hundreds of thousands).

• Writing output that's not a complete line - just add << '\n' there.

• Misspelling of "introduced" in variable name suggests sloppiness. A shorter name might be more readable - I'd suggest seen.

• Comments that extend far off the edge of the screen.

---

After addressing the trivial issues, my next concern is that there's no automated tests - we have to drive the whole program from outside to test the algorithm. It's much easier to experiment and make changes if we have a good suite of unit tests.

---

We don't need to special-case r == 0 if we defer marking a number seen until after that loop (so that the test is false for that case).

We can halve the work done in the inner loop by testing XOR of the two straddling flags to test both ascending and descending sequences simultaneously:

for (int r = 1;  r <= range;  ++r) {
     correct_sequences +=  seen[a - r] != seen[a + r];
}

---

Putting this together, I have:

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

int main()
{
    std::cin.exceptions(std::ios_base::failbit|std::ios_base::badbit);
    std::int_fast32_t input_length;
    std::cin >> input_length;
    std::uint_fast32_t count = 0;

    // consider using vector<char> for faster access, in exchange for size
    auto seen = std::vector<bool>(input_length + 1, 0);

    for (auto i = input_length;  i;  --i) {
        int_fast32_t a;
        std::cin >> a;
        const int range = std::min(input_length - a, a - 1);
        for (int r = 1;  r <= range;  ++r) {
            count +=  seen[a-r] != seen[a+r];
        }
        seen[a] = true;
    }
    std::cout << count << '\n';
}

Answer 2

no naked new

See ⧺R.11 and a few other guidelines that mention "naked new".

bool* whether_itroduced = new bool[input_length + 1]{0};

Use a std::vector rather than a bare allocated array. (This also fixes the problem where you are not freeing it, as it becomes automatic).

On the other hand, vector<bool> is weird. It is optimized to be "packed" to use one bit per element, which causes issues with making it behave properly with iterators. That won't bother you here, but you don't want the space/speed tradeoff to favor space.

So, use a std::deque instead, or use Boost's vector container instead, or actually define it as a vector<uint8_t>.

use prefix increment

You're using postix ++ everywhere. You should prefer writing it as a prefix. E.g. ++r. For int it doesn't matter, but as a general style you should get used to it, as it will generally be used for iterators that are more complex than just built-in pointers.