0
\$\begingroup\$

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://imgur.com/a/RaYf5Hy Guess that it's not worth your time to fix all those indexes.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Not sure whether I understand the problem statement. Will the input always be a permutation of 1..n? (IOW, will every number from 1 to n appear exactly once?) \$\endgroup\$ – Toby Speight Apr 29 at 13:34
  • \$\begingroup\$ If I understood what you meant by "progressions" I might be able to suggest a faster way to do it. \$\endgroup\$ – JDługosz Apr 29 at 15:43
  • \$\begingroup\$ I don't really know, but I guess that the input will always be a permutation of 1...n. \$\endgroup\$ – amdlaihfgan Apr 29 at 17:27
  • \$\begingroup\$ Given the input 1 2 3 4 5 6 ... n, the number of 3-element arithmetic subsequences scales with n² (I believe it's actually floor((n² - 2n)/4)). So you will not be able to do better than quadratic time if you enumerate every such sequence. You need to find a way to count the sequences without enumerating them. \$\endgroup\$ – trentcl Apr 29 at 20:03
  • \$\begingroup\$ I found a guide about how I can make the code work in (n log (n) + m log (n^2)) time. Doing my best to translate it asap. \$\endgroup\$ – amdlaihfgan Apr 29 at 20:12
2
\$\begingroup\$

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';
}
\$\endgroup\$
8
  • \$\begingroup\$ signed is faster than unsigned, sometimes significantly so. I disagree that "unsigned is more appropriate"; if you don't need a size_t you should prefer signed. Even then, there is a movement to migrate to signed size where possible. \$\endgroup\$ – JDługosz Apr 29 at 15:41
  • \$\begingroup\$ Your use of vector<bool> is slowing it down, since this is a special case in the standard. \$\endgroup\$ – JDługosz Apr 29 at 15:42
  • \$\begingroup\$ I accidentally removed a comment saying that vector<char> might perform better (depending a lot on the effect of the larger storage on memory locality). I'll reinstate that. \$\endgroup\$ – Toby Speight Apr 29 at 15:56
  • \$\begingroup\$ I never knew that signed arithmetic is faster than unsigned, and it seems very surprising. Would you be kind enough to share the evidence for that? \$\endgroup\$ – Toby Speight Apr 29 at 15:57
  • 1
    \$\begingroup\$ Shouldn't be that surprising - I just fixed the obvious bugs and maintainability problems. Choosing a more efficient algorithm is left as an exercise. ;-) \$\endgroup\$ – Toby Speight Apr 29 at 20:14
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ std::deque seems an odd choice for a container of unchanging size. Why not vector<char>? \$\endgroup\$ – Toby Speight Apr 29 at 16:00
  • \$\begingroup\$ Using std::deque to avoid the explicit specialization of vector is something that was published as advice many, many years ago. Using char instead of bool might be harmless (though not optimal when testing a value since it has to insert a comparison) in this simple usage, in general it may cause differences with overloading, implicit conversion sequences, etc. \$\endgroup\$ – JDługosz Apr 29 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.