2
\$\begingroup\$

You are given an array A of length N (where N is as large as 2×105). 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;
 }
\$\endgroup\$
0

3 Answers 3

4
\$\begingroup\$

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";
    }
}
\$\endgroup\$
5
  • \$\begingroup\$ Can you please tell what would be the helper array of this array: 2 3 1 3 5 and how did you find it \$\endgroup\$ Jun 3 at 10:16
  • \$\begingroup\$ @VaibhavVishalSingh It starts out as a zeroed array of length N+1: 0 0 0 0 0 0. That gets updated while evaluating each element, and ends with: 0 3 1 4 0 5 \$\endgroup\$ Jun 3 at 10:21
  • \$\begingroup\$ It would be helpful if you provide code \$\endgroup\$ Jun 3 at 10:31
  • 3
    \$\begingroup\$ @VaibhavVishalSingh: It would be helpful if you provide code helpful in taking to heart the advice given, or in sparing everyone finding this answer the effort of understanding the solution and coding it themselves? I guess a specific question where something wasn't clear would be welcome & answered.) \$\endgroup\$
    – greybeard
    Jun 3 at 10:35
  • 2
    \$\begingroup\$ Leave it to the @Deduplicator to come up with an elegant way to avoid double-counting matching subarrays! \$\endgroup\$ Jun 3 at 10:38
1
\$\begingroup\$

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.

\$\endgroup\$
-2
\$\begingroup\$

Two equal subarray elements can have at most two valid subarrays in common. If the distance between two equal subarray elements is greater than or equal to the element value, they have no valid subarrays in common. The number of valid subarrays of which an element can be a part depends on the element value, the distance of the element from the beginning of the array and the distance of the element from the end of the array. If an array element has a "previous" array element equal to it, then the the number of "uncommon" subarrays of that element is calculated based on the element value, distance not from the beginning of the array, but from that "previous" array element and the distance from the end of the array.

#include<iostream>
#include<vector>
#include<unordered_map>
int main() {
int T,N;
std::cin>>T;
for(int t=0;t<T;t++)
{
 std::vector<int> A;
 std::cin>>N;
 for(int i=0;i<N;i++)
 {
  int x;
  std::cin>>x;
  A.push_back(x);
 }
 std::unordered_map<int,int> m;
 for(int i=0;i<N;i++)
 {
  if(m[A[i]]==0)
  m[A[i]]=i+1;
 }
 long c=0;
 int x,y,z;
 for(int i=0;i<N;i++)
 {
   x=A[i]-(N-i);
   if(i+1>m[A[i]]) {
   y=A[i]-((i+1)-m[A[i]]);
   m[A[i]]=i+1;
   }
   else
   y=A[i]-(i+1);
   if(x<0)
   x=0;
   if(y<0)
   y=0;
   z=A[i]-x-y;
   if(z<0)
   z=0;
   c+=z;
  }
  std::cout<<c<<'\n';
  }
}
\$\endgroup\$
5
  • 2
    \$\begingroup\$ (Can you read that?) \$\endgroup\$
    – greybeard
    Jun 4 at 17:34
  • \$\begingroup\$ Documentation of the problem tackled and the approach taken belong in the source code. The observations pacmaninbw asked about would have been about the code presented for review (in the question). \$\endgroup\$
    – greybeard
    Jun 5 at 5:30
  • \$\begingroup\$ @greybeard Take another look at this answer. \$\endgroup\$
    – pacmaninbw
    Jun 5 at 14:55
  • 1
    \$\begingroup\$ Program source code is not just to be machine interpreted. It is a means of communication - with the maintenance programmer, with the "white-box tester", with a later you not wanting to re-invent the wheel when a similar problem comes up. (@pacmaninbw: There is an observation offered (and in a prominent place since your edit) - about the code presented in the answer rather than the question, save for an implied this is an improvement. Code layout has gone from inconsistent to haphazard, naming (variable, for lack of procedures) is desolate.) \$\endgroup\$
    – greybeard
    Jun 5 at 15:24
  • \$\begingroup\$ Can this problem be solved using segment tree? \$\endgroup\$ Jun 7 at 7:51

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.