[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
CodeFights zadaca  XML
Forum Index » Други задачи
Author Message
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

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
petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

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)
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

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



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

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.
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

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 ...

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

petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

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.
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline



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

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

petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

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


Povekje mislev vaka.
 
Forum Index » Други задачи
Go to:   
Powered by JForum 2.1.8 © JForum Team