Subarrays with length

Question

You are given an array A of length N (where N is as large as 2×10⁵). All elements of the array are positive integers less than or equal to N. Determine the count of subarrays (contiguous subsequences) of A which contain their length as an element.

The time limit on CodeChef is 1 second. My code exceeds the time limit.

#include<bits/stdc++.h>
using namespace std;
int main()
{
 int T,N;
 cin>>T;       // the number of test cases
 for(int i=0;i<T;i++)
 {vector<int> A;
  cin>>N;              // length of array
  for(int i=0;i<N;i++)
  {
    int x;
    cin>>x;           // array elements
    A.push_back(x);    
  }

  int c=0;
  for(int i=0;i<N;i++)
  {
   for(int j=i;j<N;j++)
   {
    for(int k=i;k<=j;k++)   
    {
     if(A[k]==j-i+1) {/*j-i+1 is length of the subarray that starts at 
     c++;                  index i and ends at index j.*/
     break; }
    }
    }
   }
   cout<<c<<endl;
 }
 return 0;
 }

Answer 1

Algorithm

When you need to save resources, a better algorithm is always the first thing to look into.

Currently, you go over every potential sub-array, and test each element whether it is the length.
And while brute force always works in theory, it can easily be so incredibly inefficient that it doesn't in practice.
Cubic runtime like in this case is infeasible for anything but tiny problems. May be useful to test the scaleable solution.

A more intelligent algorithm using double the space but linear time:

1. Input: Array A with lengths of length N.
2. Helper: Array B of length N+1 with index of the first element not yet used in a sub-array of length k, starts all zero.
3. For i from 0 to N - 1:
   1. Determine StartIndex = max(B[A[i]], i - A[i] + 1)
   2. Determine EndIndex = min(i + A[i], N)
   3. Mark current element as used: B[A[i]] = i + 1
   4. count += min(0, EndIndex - StartIndex - A[i] + 1)

Implementation

1. The most basic part is using a consistent and readable coding style.

   • A single space is barely any indentation. Use a tab, or at least two (better four) spaces.
   • Putting any code on the same line after an opening brace { hinders readability. Refrain consistently.
   • Putting in a bit more space doesn't make things inefficient, and increases readability. Put some space around most binary operators but . and -> as well as { and }, and after , and ;.
   • The opening brace can be on the same line as the control-flow instruction owning the block (if, for, while, ...), the closing brace } can be on the same as else, but nothing else.
   • Choose meaningful names, instead of adding comments where possible. Yes, adhering to the naming of your sources is important, though that might mean you have to add a comment.

2. Don't use <bits/stdc++.h>, it's unportable and inefficient. See "Why should I not #include <bits/stdc++.h>?" for the details.
   Only include what you need, in your case <vector> and <iostream>. <bits/stdc++.h> is not a standard header, and likely much more than you need.

3. using namespace std; is plain evil. That namespace is not designed for inclusion, thus there is no comprehensive, fixed and reliable list of its contents, allowing for conflicts just because it's Friday.
   See "Why is “using namespace std;” considered bad practice?" for details.

4. Input can always fail. Deal with it, at least by asking for exceptions.

5. As you only read ints, consider using a std::istream_iterator.

6. Don't put multi-line-comments next to the code. You comment out the code too!

7. Don't force flushing a stream unless you really mean it, as it flushes performance down the drain. std::endl outputs a newline and then flushes, stream << std::endl being exactly equivalent to stream << '\n' << std::flush. Thus if you really have to, better be explicit and use std::flush.
   See "What is the C++ iostream endl fiasco?" for more detail.

8. return 0; is implicit for main().

Improved code keeping the algorithm

#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::cin.exceptions(std::ios_base::failbit);
    auto stream = std::istream_iterator<int>(std::cin);

    const auto T = *stream; // the number of test cases
    for (int i = 0; i < T; ++i) {
        std::vector<int> A;
        const auto N = *++stream; // length of array
        for (int i = 0; i < N; ++i)
            A.push_back(*++stream); // array elements

        int count = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = i; j < N; ++j) {
                int length = j - i + 1;
                for (int k = i; k <= j; ++k) {
                    if (A[k] == length) {
                        ++count;
                        break;
                    }
                }
            }
        }
        std::cout << c << "\n";
    }
}

Answer 2

Check the repercussions of using namespace std;, especially in headers/source to be included.

The code presented gives no clue what it is to achieve:
Document your code, in the code! For C++ I remember doxygen.

---

I see the code trying the most simple thing that might work
(for each sub-array, compare each element to the length).
Nothing inherently wrong with that, on the contrary, this is where to start.
When brute force turns out to require too much resources, the simplest solution still is useful for testing smarter procedures.

A "dual" approach would start with the element values:
No value smaller than one or exceeding the length of the array can be the length of a sub-array.
Each 1 is the length of a sub-array containing just itself.
Each x is the length of x sub-arrays of length x unless too close to start or end of array. But some may have been counted already if another x is close.

---

Naming:
Good names leave little doubt what the value (operation, object) means.
The code picks up A & N from the 3rd. party problem statement.
It would have spared me seconds of misunderstanding seeing the same for L & R.

The one name not "excused" by the problem statement is c:
Prefer sub_arrays over count. (In a context with many names: sub_array_count).

The bracing & indentation is slightly inconsistent. There is good reason why frequent amounts of indentation per level are from 4 to 8:
Easy to follow, some pressure not to nest too deeply.