CodeFights zadaca

Given three equal-length arrays, array1, array2, and array3, your task is to find the number of combinations of indices i, j, and k, such that array1[i] < array2[j] < array3[k].

Example

For array1 = [12, 6, 8, 3], array2 = [1, 3, 5, 8], and array3 = [9, 15, 7, 5], the output should be combinationCount(array1, array2, array3) = 7.

The possible combinations are:
{3, 5, 7}
{3, 5, 9}
{3, 5, 15}
{3, 8, 9}
{3, 8, 15}
{6, 8, 9}
{6, 8, 15}

For array1 = [25 25], array2 = [30 30], and array3 = [35 37], the output should be combinationCount(array1,array2,array3) = 8.

The possible combinations are:
{25, 30, 35}
{25, 30, 37}
{25, 30, 35}
{25, 30, 37}
{25, 30, 35}
{25, 30, 37}
{25, 30, 35}
{25, 30, 37}

[execution time limit] 0.5 seconds (cpp)

[input] array.integer array1

The first array of numbers.

Guaranteed constraints:
1 ≤ array1.length ≤ 10^4
0 ≤ array1[i] ≤ 2 · 10^4

[input] array.integer array2

The second array of numbers.

Guaranteed constraints:
array2.length = array1.length
0 ≤ array2[i] ≤ 2 · 10^4

[input] array.integer array3

The third array of numbers.

Guaranteed constraints:
array3.length = array1.length
0 ≤ array3[i] ≤ 2 · 10^4

[output] integer

Number of combinations of i, j, and k values such that array1[i] < array2[j] < array3[k].

Едно знам дека алгоритам O(n^3) нема шанси , а и друга идеја немам . Помош ! Ако треба и линк
https://app.codesignal.com/challenge/9nhvJeSsEa9PKcHXc

Hint: shto ako imash eden for koj gi izminuva elementite od vtorata (srednata) niza, eden po eden? Da kazheme deka si vo momentov kaj element so vrednost "5" od vtorata niza. Dali mozhesh sega polesno da izbrois kolku ima soodvetni elementi od prvata i tretata niza?
(Ushte eden hint: mozhe, so soodvetna struktura ili ako ti se odnapred sortirani prvata i tretata niza so binary search)

Sakam da znam kako so binary search ... potocno so lower_bound i upper_bound ili ...

Perez wrote:Sakam da znam kako so binary search ... potocno so lower_bound i upper_bound ili ...

Pa da, na primer so niv. Ima dobri tutoriali na MENDO za ova vo delot za Algoritmi.

Eve uste eden hint.

This message was edited 1 time. Last update was at 14/08/2018 14:23:13

Da toa ako ima 3ka vo nizata ... ami sho ako nema i da sakam da vidam kolku broevi ima pomalku od 3...

EDIT
moja greska bez razlika dali ima 3ka ili nema ...

Perez wrote:Da toa ako ima 3ka vo nizata ... ami sho ako nema i da sakam da vidam kolku broevi ima pomalku od 3...

EDIT
moja greska bez razlika dali ima 3ka ili nema ...

Da, rabotat lower_bound i upper_bound bez razlika dali taa vrednost postoi ili ne.

This message was edited 1 time. Last update was at 14/08/2018 16:18:49

еве вака јас го напишав и немав проблеми , А нешто по побрз начин ?

Perez wrote:еве вака јас го напишав и немав проблеми , А нешто по побрз начин ?

Povekje mislev vaka.