gong-ui jang - 6 months ago 43

C++ Question

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.

Thanks in advance.

`#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);

}

Answer

The solution is not correct because your algorithm is wrong.

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.

Source (Stackoverflow)