gong-ui jang - 1 year ago 84
C++ Question

count distinct slices in an array

I was trying to solve this problem.

An integer M and a non-empty zero-indexed array A consisting of N
non-negative integers are given. All integers in array A are less than
or equal to M.

A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice
of array A. The slice consists of the elements A[P], A[P + 1], ...,
A[Q]. A distinct slice is a slice consisting of only unique numbers.
That is, no individual number occurs more than once in the slice.

For example, consider integer M = 6 and array A such that:

``````A[0] = 3
A[1] = 4
A[2] = 5
A[3] = 5
A[4] = 2
``````

There are exactly nine distinct slices: (0, 0), (0, 1), (0, 2), (1,
1), (1,2), (2, 2), (3, 3), (3, 4) and (4, 4).

The goal is to calculate the number of distinct slices.

``````#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 100002

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

using namespace std;

bool check[MAX];

int solution(int M, vector<int> &A) {
memset(check, false, sizeof(check));
int base = 0;
int fibot = 0;
int sum = 0;

while(fibot < A.size()){

if(check[A[fibot]]){
base = fibot;
}

check[A[fibot]] = true;

sum += fibot - base + 1;
fibot += 1;
}

return min(sum, 1000000000);
}
``````

First of all, let me show you a counter example. Let `A = {2, 1, 2}`. The first iteration: `base = 0`, `fibot = 0`, `sum += 1.` That's right. The second one: `base = 0, fibot = 1`, `sum += 2`. That's correct, too. The last step: `fibot = 2`, `check[A[fibot]] is true`, thus, `base = 2`. But it should be `1`. So your code returns`1 + 2 + 1 = 4` while the right answer `1 + 2 + 2 = 5`.
The right way to do it could be like this: start with `L = 0`. For each `R` from `0` to `n - 1`, keep moving the `L` to the right until the subarray contais only distinct values (you can maintain the number of occurrences of each value in an array and use the fact that `A[R]` is the only element that can occur more than once).
There is one more issue with your code: the `sum` variable may overflow if `int` is 32-bit type on the testing platform (for instance, if all elements of `A` are distinct).
As for the question WHY your algorithm is incorrect, I have no idea why it should be correct in the first place. Can you prove it? The `base = fibot` assignment looks quite arbitrary to me.