last day (15 days later) » 

2:15 PM
0
Q: Range withing an array in C

Nikos KLonI came up with an algorithm and I wanted to ask something. Is there any way to set a range of values within an array? Eg int N = 8; int array[N] = {2,6,5,9,4,3,5,9,4,9}; and using a loop to increase the start value with each pass. for (int A = 1; A < N - 2; A++) { for (int B = 1; B < N -...

 
No, you'd have to write your own summing function and provide it with the array and the indices range.
 
you mean waht exactly? Is there any other way? Please explain.
the complexity of the prgramm is O(n^2) not O(n^3) . What I suppose to do to make the above code more efficient?
 
You could write a function which takes the array and indices as parameters, something like (assuming the array stores ints) - int Sum(int *array, int start, int end);
 
@lared you mean for the sum function right?
 
Yes, i do mean the sum function. As to efficiency the above program is O(n^3) due to the naive usage of Sum - it has to traverse the array to get the sums after all. You should consider caching the sums (for example ProfitA changes only by array[A-1] with each iteration of the outer loop, but you perform (N-2)*(A-1) operations per iteration of the outer loop (N-2 iterations of the inner loop + A-1 iterations to calculate the sum per iteration) instead of just a single one!
 
2:15 PM
Hmmmmm this is frustrating. So the best complexity is O(n^3)?
 
You can reduce it to O(n^2) by use of caching the sums and modifying them accordingly. Notice that ProfitA doesn't depend on the value of B, but you still included it in the inner loop. Similarly with each change of B ProfitB and ProfitC only vary by the value of ONE element of the array. Try to write the sums in the consecutive iterations down to see the pattern. There might be an even faster solution but I don't know what the code is meant to do.
 
hello
 
hi
Do you understand what I meant by caching the sums?
 
no exactly
can I send you the problem in a graph to understand my problem?
 
ok
 
2:17 PM
explain me your points as I prepare
heres the problem
 
Let us fix some numbers first, let's say that N is 20 and (for sake of simplicity) assume that we are inside the A loop with A=3
 
Ok, first let's discuss the caching
 
It's the easiest thing to do
As I've said before A=3
now I'd like you to become a sort of a computer
 
2:19 PM
what do you mean?
 
You'll tell me what computer does when it executed the code
it's a sort of mental exercise
 
works great in my experience
so let's say that we're just starting executing YOUR code
 
wait ..
 
and we've gone through two loops of A with no problem and now we're entering the third one
A=3
 
2:21 PM
yes..?
 
now we're in the second line
 
what's the value of B?
 
good.
now we advance one line since we've entered the loop, didn't we?
 
2:22 PM
yes
 
what's the value of ProfitA?
 
we assume that the array is just [1,2, 3, 4, 5, 6, 7,8, ...]
 
a
36
the value of ProfitA is 36
 
ok, i'm not going to count that, I believe in your computing abilities D:
:D*
 
2:23 PM
hahaha
 
does it depend on B at all?
 
I don't think so
no
 
good. And do we compute it again when B changes?
 
no it doesn't matter
wait
yes but it doesn't depends on B
 
So can we move it somewhere else, so that it;s available there, but not computed again?
 
2:25 PM
what is your point?
 
you are doing unnecessary computation
that's why I said it's roughly O(n^3)
it would have the same value if it were in front of the B loop, wouldn't it?
and then we would only calculate the sum once, instead of every time B changes?
that's going to save us some time
 
to move the ProfitA procedure in the above loop?
or to use 2 different loops?
 
to move it to the A look
in front of the B loop
 
OOOOO
yes!
well
your right but there is a problem
 
go on
 
2:27 PM
first read the problem
now this is the procedure graphically
The number of permutations is:
- given: 3 brothers, N numbers
- permutations: 1+0.5*N*(N-3)
- E.g. N=8 --> permutations = 1+0.5*8*5 = 21
- E.g. N=20 --> permutations = 1+0.5*20*17=171
 
So what's the problem again?
I'm fairly sure we can do it faster than O(n^3)
O(n^2) is perfectly achievable in 3 steps
it's just one of them
the easiest one at that
we'll get to the rest
 
I send you the problem!
didn't you recieve it?
a comment above yours
 
I did, I believe you want to generate all the sequences and pick the most favourable one
 
yes
but the sequence isn't suffled
you saw the diagram
is my logi correct?
is the code what we want id there an better aproach?
 
I believe so, yes
 
2:33 PM
is good?
 
What I want to do is to refine your code
the approach is correct
but execution has some inefficiencies
 
go on
 
the diagrams will come in handy
 
yes
so can you help me to refind the loop?
 
But do you agree that the ProfitA can be taken out of the inner loop to reduce the computational load?
yes
 
2:34 PM
yes
i agree
 
good, so now in the inner loop there are only two expressions
 
profib and c
 
take a look at the B column
 
#profitB
 
yup
you can see that with each loop iteration in your code you calculate the two sums from scratch, don't you?
 
2:36 PM
ok
yes
 
and the next sum differs from the previous one only by value of one array element?
 
yes the pointee value
 
so why don't you store the previous sum somehow and add the relevant value?
 
no understanding?
 
this way you only add one elelemt to the sum, and not calculate it again
 
2:37 PM
and the other two?
 
I'm talking about profitB now
let's leave profitC
 
ok
but you shoyld keep in mind the profitA also change
 
yes, but we've taken care of it
 
#sorry for bad typing
ok I listen
 
please wait a while, I'm going to write some code of what we already have
 
2:38 PM
ok
 
yes
 
Do you agree with what's there?
That's what we've established so far
assuming that SUM operation actually exists
 
yes I also did it in my notepad
ok
 
good
I'm going to change it a little, brb
 
2:40 PM
I'm waiting
 
sorry, had a bit of a bad experience with github, as always
As you might've noticed I've changed ProfitB a little
at first, it has value equal to array[A]
 
yes
 
In other words, sum(rray[A .. A + 1 - 1])
so exactly the same as it would have been in your version
but now we can access the value of the previous sum in the next iteration
 
okay
 
I should have moved the sum to the back of the loop
but the point stands that my code does exactly the same as your
yours*
can you see it?
 
2:45 PM
yes
well..
we can change A B and C ?
as the diagram
 
we can change ProfitA and so on
I don't exactly know what you mean
 
this will be automatically I assume
we move one element at a time
 
instead of calculating the sum completely each time, we add the enxt element to the previous sum
 
AAAAAAAAh
now I took the point!
haha
 
and now to see if you understand it completely can you do ProfitC?
it's sort of the same as ProfitB
 
2:49 PM
you mean?
 
instead now you start with the sum and subtract the enxt element
instead of starting with one element and adding the next ones
 
no understand
I lost you
int ProfitC = Sum(array[A+B...N-1]); is inside the second loop
you want me to make the function?
 
an you see how similar they are?
look at the C column
in your graph
 
you say
int ProfitC = Sum(array[A...N])
but don't we want A..N-1?
 
it should've been A+1...N, sorry
and probably N-1 too :D
off by one errors are the bitch
 
2:52 PM
hahaha
please re-edit it
 
shit
well, almost
I've eaten the 1
 
//here the values are "current
what do you want to say?
 
before the loop terminates you have to add the next elements
 
and don worry about the 1 in int ProfitC
 
and subtract respectively
I got subtraction wrong to
 
2:55 PM
yes but you did it
 
now take a look at the complexity
the outer loop executes roughly ~N times
 
O(n^2) :D
 
yup
 
but we forgot something
when I created the pseudocode
for A=1 to N-2 do loop
for B=1 to N-1-A do loop
ProfitA = Sum(Salary[0...A-1])
ProfitB = Sum(Salary[A...A+B-1])
ProfitC = Sum(Salary[A+B...N-1])
ProfitMax = Max(ProfitA, ProfitB, ProfitC)
if Min is greater than ProfitMax then
Min = ProfitMax
Permutation = [A,B,C]
end if
end loop
end loop
I also use an if statement to save the smallest weigh
 
you can do it there where the values are "current"
 
2:58 PM
I now
I just wanted to sure that you undestand correctly
bu why before
ProfitB = ProfitB + array[A+B-1];
ProfitC = ProfitC - array[A+B]);
?
don't we want it after the calculation?
 
because I've set up the initial values correctly BEFORE the loop executes
 
that's why
 
and at the end i am making them correct again for the next iteration
 
can you wait to update your code with the if ?
 
I'm short on time, really
but it's trivial
you have to pick the max of the three
and see if it's smaller than the previous value
 
3:00 PM
yes
 
at the beginning you can set it to INT_MAX or something
 
but I want to set the first minumum
 
the first minimum should be something extraordinarily high
so that ANY value is smaller
INT_MAX will do the trick
 
O.o
ok
 
what language is it in anyway?
 
3:01 PM
C
 
oh, so I;m right :d
 
yes!
 
it's from the header limits.h if I'm not mistaken
 
now what about sum?
yes your right
I need to create a function and use another loop?
 
you can use the code from the answers
you write another function called sum
and pass an array to it
 
3:02 PM
then the complexity goes n^3
 
not really
 
why?
 
you only use sum in the outer loop
 
and so?
 
so even if the sum is O(n) as it is, and the B look is O(n)
loop*
 
3:03 PM
yes
Oh
 
then the overall complexity is O(n * (n + n)) = O(n^2)
 
yes yes yes
hahah
 
and we're golden
I'm really late, sorry, I have to go :D
have a good day
or at least you are
 
array[A+B-1]; is exactly that right?
ok bye
really nice to meet you!
 

  last day (15 days later) »