CareerCup

It is m^n and m*(m+1)^(n-1).

Could someone clarify how the trie is built?

It seems that it isn't klogk, but nlogk

For one who would like to use C++.

bool idistant_internal(std::vector<int>& arr, int curr) {
    if (curr == 0) return true;
    for (int pos = 0; pos < (int)arr.size() - curr - 1; ++pos) {
        if (arr[pos] == 0 && arr[pos + curr + 1] == 0) {
            arr[pos] = arr[pos + curr + 1] = curr;
            if (idistant_internal(arr, curr - 1)) return true;
            arr[pos] = arr[pos + curr + 1] = 0;
        }
    }
    return false;
}

std::vector<int> idistant(int n) {
    std::vector<int> res(2*n);
    if (idistant_internal(res, n)) return res;
    return {};
}

You can do it in O(n*lg(n)) with a sweep line algorithm.

> Sort all rectangles left x and all points by x.
> Move sweep line with 3 kinds of event points: start/end of rectangle and point.
> If left/right rectangle boundary is encountered then add/remove its y-interval to a line. Can be done in log(n) because rectangles don't intersect.
> If a point is encountered then check to which y-interval it belongs. Can be done in log(n) because intervals on the line stored sorted.

Looks like ugly numbers but not sure how would it work with primes around 10^4 and N around 10^6?

It might seem to work if

p

is close to

0

or

1

, but clearly doesn't work if

p

equals to

0.5

.

It is O(n) because it uses memoization.

We can use adjacency matrix representation to provide an answer in O(E*V).

01234
0 x  x
1    x
2
3
4

For every edge (x) go along to rows, eg. 0 and 1 for edge 01, to check if there are columns where both rows have x in it. Do it for every edge.

There is no solution with allowed singletons.

Time is not linear, because you need to maintain L pointers in your trie.

Maybe not

Array1[i] * 10

, but

Array1[i] * 10^k

.

to find two identical substrings of a string one can build a suffix tree.

If zr.roman elaborated his solution with hashtable it would be nice.

So, is it O(n^3) of what? Anyway would be nice to have very succinct description of the algorithm.

Another thread could have modified the string.

Can we deduce a direct numerical formula?

This will not always work in O(n), because quickselect takes O(n^2) in worst case.