challenge

[Winsu]

I have got this exercise to do...It's in a website that has a lot of exercises to do ,whoever want to know where it's just ask me...

this is the wording..

A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

For example, array A such that:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

contains the following example slices:

slice (1, 2), whose average is (2 + 2) / 2 = 2;
slice (3, 4), whose average is (5 + 1) / 2 = 3;
slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

The goal is to find the starting position of a slice whose average is minimal.

Write a function:

int solution(vector<int> &A);

that, given a non-empty zero-indexed array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.

For example, given array A such that:
A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

the function should return 1, as explained above.

Assume that:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−10,000..10,000].

and I have done this...The program is working fine, it does what is expected to do, but it's so slow...because I had to nest two for statement to go along the vector....I can't imagine how I could do it faster....

this is the code..

#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int>& A){
	vector<int>::iterator it;
	
	int internalcont = 0;
	float cont = 0;
	int internal = 0;
	int pos = 0;
	float minimal = 100000;
	for(it = A.begin();it != A.end()-1;it++){
		internalcont++;
		for(unsigned int i = internalcont;i <= A.size();i++){
				vector<int>::iterator it1 = it + 1;
				cont = *it +*it1;
				internal = i-internalcont;
				while(internal>0){
				internal--;
				it1++;
				cont += *it1;
				}
				if(minimal>cont/((i-internalcont)+2)){
					minimal = cont/((i-internalcont)+2);
					pos = internalcont-1;
				}
				cont = 0;
			}
		}
		
		return pos;
}


int main(){
	
	vector<int> myvector{4,2,2,5,1,5,8};
	cout<<solution(myvector);
	
}

if somebody is able to provide a faster solution I'll be grateful, because I'm starting to have a big headache..

[dhayden]

As a start, create a new array B that contains the running sum of items from A. In other words, B[i] = A[0]+A[1]+....+A[i-1]+A[i].

Now the average of the slice (P,Q) is just (B[Q]-B[P-1]) / (Q-P+1). Now you can do an exhaustive search in about (100,000*100,000) steps, which should take only a few seconds.

[Winsu]

I have removed the while and I guess I save some time...but it's not good enough I leave you the update..

#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int>& A){
	vector<int>::iterator it;
	
	int internalcont = 0;
	float cont = 0;
	int internal = 0;
	int pos = 0;
	float minimal = 100000;
	for(it = A.begin();it != A.end()-1;it++){
		internalcont++;
		vector<int>::iterator it1 = it + 1;
		cont = *it +*it1;
		for(unsigned int i = internalcont;i <= A.size();i++){
				if(i-internalcont>0){
					it1++;
					cont +=*it1;
				}
				if(minimal>cont/((i-internalcont)+2)){
					minimal = cont/((i-internalcont)+2);
					pos = internalcont-1;
				}
				
			}
		cont = 0;
		}
		
		return pos;
}


int main(){
	
	vector<int> myvector{4,2,2,5,1,5,8};
	cout<<solution(myvector);
	
}

do you mean create an array with all the possible slices and later look for the first minimal average??

[Winsu]

but I guess for doing what you mean I would need two for statement nested too, wouldn't I?

[Winsu]

but once I have my B array I have to look for the minimal average and then I'll have to nest again two for statements...or I don't know then what you mean exactly...

[dhayden]

Yes, you will need 2 for loops. But your original function has 3 loops. That might make all the difference.

[Winsu]

yes, but my last version just use two for..maybe I could remove more instructions, but I don't think It makes a difference...It's a website where i introduce my code and it test it how is its correctness and its performance, its correctness is perfect but its performance is quite slow...the time complexity is O(N**2), when it should be 0(N)....

[dhayden]

If it has to be O(N) then you need a better algorithm. I can't think of one, at least not off hand.

[Winsu]

As a minimum I would need to use other container with more features that in just one iteration I could check all slices....but me neither I can't manage with this at the moment....if you get any idea please let me know...even just a starting idea...thanks!!!

[TheIdeasMan]

Hi,

This sounds like a variation on the max sub sequence sum problem. Except you are looking for a minimum. Once you have a sum the average is straight forward. Although you will have to keep track of how elements you had since the last MaxSum (MinSum)

I am not sure whether the code below can be adapted for your needs. It is O(N)

The code is from a book by Mark Allen Weiss "Data Structures and Algorithm Analysis in C", Second Ed. 1997 ISBN 0-201-49840-5 page 29. I have altered it a little: Declare & initialise on 1 line, braces for single statements.

int MaxSubsequenceSum (const int A[], int N) {

  int ThisSum = 0;
  int MaxSum = 0;
  int j;

  for (j = 0; J < N; j++) {
    ThisSum += A[j];
   
    if (ThisSum > MaxSum) {
      MaxSum = ThisSum;    
    }
    else if (ThisSum < 0 ) {
      ThisSum = 0;
    }
  }
  return MaxSum;
}

The author of that book has published a C++ version.

Algorithms are really important, a bad one can take 1000 years to complete, a good one can do the same in less than 1 second. Good ones are also scalable, imagine if your problem went to 1 million numbers or more :+)

Hope all goes well :+)

[dhayden]

Okay, a little digging led to this link: http://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/. I didn't read the code but read part of the proof which contains the brilliant observation that there must be a minimum average slice (MAS) of length 2 or 3. You can prove this by contradiction: suppose there exists a MAS with length >=4. Divide it into two slices, one with length 2 and one with length N-2. If the averages of these two are different then one must be smaller than the overall average, and the other must be greater. But the one that is smaller is the real MAS, contradicting our original assumption.

I'll leave it to you to solve the problem from here. Note that you only need to find the starting position of the MAS. This makes it easier.

[Winsu]

Hey sorry for replaying late...yes that's true there are a lot of documentation about that...it can be done..the key of the problem was basically in the mathematical thinking....once you get the idea it can be thanks...thanks for giving me the link....I was trying by myself get that idea...

[TheIdeasMan]

Hi,

Sorry my idea wasn't of any help, I guess it all depended on the meaning of "minimal" not being the same as "least". I have adjusted my in- brain DB to suit :+)