A non-empty array A consisting of N integers is given. A prefix suffix set is a pair of indices (P, S) such that 0 ≤ P, S < N and such that:
- every value that occurs in the sequence A[0], A[1], ..., A[P] also occurs in the sequence A[S], A[S + 1], ..., A[N − 1],
- every value that occurs in the sequence A[S], A[S + 1], ..., A[N − 1] also occurs in the sequence A[0], A[1], ..., A[P].
The goal is to calculate the number of prefix suffix sets in the array.
For example, consider array A such that:
A[0] = 3 A[1] = 5 A[2] = 7 A[3] = 3 A[4] = 3 A[5] = 5There are exactly fourteen prefix suffix sets: (1, 4), (1, 3), (2, 2), (2, 1), (2, 0), (3, 2), (3, 1), (3, 0), (4, 2), (4, 1), (4, 0), (5, 2), (5, 1), (5, 0).
Write a function:
int solution(vector<int> &A);
that, given a non-empty array A of N integers, returns the number of prefix suffix sets.
If the number of prefix suffix sets is greater than 1,000,000,000, the function should return 1,000,000,000.
For example, given:
A[0] = 3 A[1] = 5 A[2] = 7 A[3] = 3 A[4] = 3 A[5] = 5the function should return 14, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..40,000];
- each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
// you can also use includes, for example:
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int solution(vector<int> &A)
{
int count = 0;
int len = A.size();
int i,j;
set<int> outer, inner;
for(i=0;i<len;i++)
{
outer.insert(A[i]);
inner.clear();
for(j=0
{
}
}
return count;
}
In file included from user.cpp:18: func.cpp: In function 'int solution(std::vector<int, std::allocator<int> >&)': func.cpp:18: error: expected ';' before '{' token func.cpp:21: error: expected primary-expression before '}' token func.cpp:21: error: expected ';' before '}' token func.cpp:21: error: expected primary-expression before '}' token func.cpp:21: error: expected ')' before '}' token func.cpp:21: error: expected primary-expression before '}' token func.cpp:21: error: expected ';' before '}' token
// you can also use includes, for example:
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int solution(vector<int> &A)
{
int count = 0;
int len = A.size();
int i,j;
set<int> outer, inner;
for(i=0;i<len;i++)
{
outer.insert(A[i]);
inner.clear();
for(j=len-1;j>=0;j--)
{
inner.insert(A[j]));
if(outer == inner)
{
cout << "(" << i << "," << j << ")" << endl;
count++;
}
}
}
return count;
}
In file included from user.cpp:18: func.cpp: In function 'int solution(std::vector<int, std::allocator<int> >&)': func.cpp:19: error: expected ';' before ')' token func.cpp:23: error: 'cout' was not declared in this scope func.cpp:23: error: 'endl' was not declared in this scope
// you can also use includes, for example:
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int solution(vector<int> &A)
{
int count = 0;
int len = A.size();
int i,j;
set<int> outer, inner;
for(i=0;i<len;i++)
{
outer.insert(A[i]);
inner.clear();
for(j=len-1;j>=0;j--)
{
inner.insert(A[j]);
if(outer == inner)
{
cout << "(" << i << "," << j << ")" << endl;
count++;
}
}
}
return count;
}
In file included from user.cpp:18: func.cpp: In function 'int solution(std::vector<int, std::allocator<int> >&)': func.cpp:23: error: 'cout' was not declared in this scope func.cpp:23: error: 'endl' was not declared in this scope
// you can also use includes, for example:
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int solution(vector<int> &A)
{
int count = 0;
int len = A.size();
int i,j;
set<int> outer, inner;
for(i=0;i<len;i++)
{
outer.insert(A[i]);
inner.clear();
for(j=len-1;j>=0;j--)
{
inner.insert(A[j]);
if(outer == inner)
{
//cout << "(" << i << "," << j << ")" << endl;
count++;
}
}
}
return count;
}
// you can also use includes, for example:
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int solution(vector<int> &A)
{
int count = 0;
int len = A.size();
int i,j;
set<int> outer, inner;
for(i=0;i<len;i++)
{
outer.insert(A[i]);
inner.clear();
for(j=len-1;j>=0;j--)
{
inner.insert(A[j]);
if(outer == inner)
{
//cout << "(" << i << "," << j << ")" << endl;
count++;
}
}
}
return count;
}
// you can also use includes, for example:
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int solution(vector<int> &A)
{
int count = 0;
int len = A.size();
int i,j;
set<int> outer, inner;
for(i=0;i<len;i++)
{
outer.insert(A[i]);
inner.clear();
for(j=len-1;j>=0;j--)
{
inner.insert(A[j]);
if(outer == inner)
{
//cout << "(" << i << "," << j << ")" << endl;
count++;
}
}
}
return count;
}
The following issues have been detected: timeout errors.
medium random tests, length = 400
running time: >0.24 sec., time limit: 0.10 sec.
medium random tests, length = ~1,000
running time: >1.02 sec., time limit: 0.10 sec.
large tests with one rare different element , length = ~10,000
running time: >1.01 sec., time limit: 0.10 sec.
large random tests, length = ~20,000
running time: >1.02 sec., time limit: 0.16 sec.
range test, length = 40,000
running time: >1.01 sec., time limit: 0.36 sec.
maximal number of pairs, length = ~30,000
running time: >1.01 sec., time limit: 0.16 sec.