Latest posts for the topic "CodeFights zadaca"

CodeFights zadaca

Perez — GMT

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

CodeFights zadaca

petarsor — GMT

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)

Re:CodeFights zadaca

Perez — GMT

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

Re:CodeFights zadaca

petarsor — GMT

[quote=Perez]Sakam da znam kako so binary search ... potocno so lower_bound i upper_bound ili ... [/quote]
Pa da, na primer so niv. Ima dobri tutoriali na MENDO za ova vo delot za Algoritmi.

Eve uste eden hint.
[code]#include
#include
#include
using namespace std;

int main() {
vector v = {1, 3, 2, 5, 4};
sort(v.begin(), v.end());

//kolku ima pomali od 3 (pecati "2" bidejki imame 1 i 2)
cout << (lower_bound(v.begin(), v.end(), 3) - v.begin()) << endl;
return 0;
}[/code]

Re:CodeFights zadaca

Perez — GMT

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

Re:CodeFights zadaca

petarsor — GMT

[quote=Perez]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 ...[/quote]
Da, rabotat lower_bound i upper_bound bez razlika dali taa vrednost postoi ili ne.

Re:CodeFights zadaca

Perez — GMT

[code]int combinationCount(vectora, vectorb, vectorc) {

sort(a.begin(),a.end());
sort(b.begin(),b.end());
sort(c.begin(),c.end());
int s=0;
for(int i=c.size()-1; i>=0; i--)
for(int j=0; j {
vector::iterator up,low;
low = lower_bound(b.begin(),b.end(),c[i]);
up = upper_bound(b.begin(),b.end(),a[j]);
if((low-b.begin())-(up-b.begin())<0)break;
else s+= ((low-b.begin())-(up-b.begin()));

}
return s;
}
[/code]

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

Re:CodeFights zadaca

petarsor — GMT

[quote=Perez]еве вака јас го напишав и немав проблеми , А нешто по побрз начин ? [/quote]

Povekje mislev vaka.
[code]long long solution(vector a, vector b, vector c) {
long long sum = 0;

int n = c.size();
sort(a.begin(), a.end());
sort(c.begin(), c.end());

for (int p=0; p
int number = b[p];

int aa = lower_bound(a.begin(), a.end(), number) - a.begin(); //pomali vo a

int R = upper_bound(c.begin(), c.end(), number) - c.begin();
int cc = n - R; //pogolemi vo c ima (N - R), odnosno (kolku ima elementi) minus (kolku ima pomali ili ednakvi)

sum += (aa*cc);
}

return sum;
}[/code]