This is the wording of a problem...I understand the target, what I have to do is count the possible ways to climb a ladder having the option of walking just one step or two step(the decision is new each time)...anyway that part the wording explain properly...the trouble comes from the way to output the amount of ways to climb a ladder..it is referenced to a result module of 2^p but it is not clear.....Initially we get two vectors...the vector A is the amount of rungs at a concrete ladder(each element of array A is a different ladder) and vector B is used to expressed in a more compressed way the amount of way to climb a ladder....what I think is returned is the amount of ways of climb a ladder(it is obtained from a fibonacci secuence being N rungs in a ladder then fibonacci(N+1) ways to climb a ladder...example a ladder with 4 rung the fifth number in the fibonacci secuence is the amount of ways) module of 2^B[i]....so with A[i] = 4 and B[i] = 2 it will be...fibonacci(4+1) % (2^2)...this is what I understand but there is an example on the wording and it doesn't match with what I'm thinking....anyone has any different idea??...I guess I must be wrong with the concept of what is a module here or something but I'm not sure....I have pasted the wording in case my explanation is not very accurate...thanks!!!!
You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely:
with your first step you can stand on rung 1 or 2,
if you are on rung K, you can move to rungs K + 1 or K + 2,
finally you have to stand on rung N.
Your task is to count the number of different ways of climbing to the top of the ladder.
For example, given N = 4, you have five different ways of climbing, ascending by:
1, 1, 1 and 1 rung,
1, 1 and 2 rungs,
1, 2 and 1 rung,
2, 1 and 1 rungs, and
2 and 2 rungs.
Given N = 5, you have eight different ways of climbing, ascending by:
1, 1, 1, 1 and 1 rung,
1, 1, 1 and 2 rungs,
1, 1, 2 and 1 rung,
1, 2, 1 and 1 rung,
1, 2 and 2 rungs,
2, 1, 1 and 1 rungs,
2, 1 and 2 rungs, and
2, 2 and 1 rung.
The number of different ways can be very large, so it is sufficient to return the result modulo 2P, for a given integer P.
that, given two non-empty zero-indexed arrays A and B of L integers, returns an array consisting of L integers specifying the consecutive answers; position I should contain the number of different ways of climbing the ladder with A[I] rungs modulo 2B[I].
For example, given L = 5 and:
A[0] = 4 B[0] = 3
A[1] = 4 B[1] = 2
A[2] = 5 B[2] = 4
A[3] = 5 B[3] = 3
A[4] = 1 B[4] = 1
the function should return the sequence [5, 1, 8, 0, 1], as explained above.
The example that is written on the wording...It doesn't match with what I understand...this has been extracted from the wording....
***********************************************************************
For example, given L = 5 and:
A[0] = 4 B[0] = 3
A[1] = 4 B[1] = 2
A[2] = 5 B[2] = 4
A[3] = 5 B[3] = 3
A[4] = 1 B[4] = 1
the function should return the sequence [5, 1, 8, 0, 1], as explained above.
***********************************************************************
This is how I would do this according what I understand
for example fibonacci serie is. [0,1,1,2,3,5,8,13,21....]
so A[0] and B[0] would be 5%2^3 ->5/8 = 0,625 being its module 6
A[1] and B[1] would be 5%2^2-> 5/4 = 1,25 being its module 2
A[2] and B[2] would be 8%2^4-> 8/16 = 0,5 being its module 5
A[3] and B[3] would be 8%2^3-> 8/8 = 1 being its module 0
A[4] and B[4] would be 1%2^1-> 1/2 = 0,5 being its module 5
My resulting vector is [6,2,5,0,5] and the resulting vector according to the wording is [5,1,8,0,1]so they don't match......that's why I know I'm doing something wrong...
Thanks...the point is while I don't know what they do...I can't start coding the solution that I think it would not be so difficult....thanks but I think it is neither 2 * B[I] nor 2B[I]...
Going back and doing modulus not division, we have :
A[0] and B[0] 5 % (23) == 5
A[1] and B[1] 5 % (22) == 1
A[2] and B[2] 8 % (24) == 8
A[3] and B[3] 8 % (23) == 0
A[4] and B[4] 1 % (21) == 1 // excellent, there is 1 rung, so 1 way to do it !!
So this gives the same answers as what they had :+)
L is an integer within the range [1..30,000];
As is always the way with these, brute force doesn't work, one has to come up with some other cunning plan :+)
The problem here is the 30000 fib number is way too huge, even using a big number library the cost of calculating it would be ridiculous. There is probably some other particularly clever and elegant way of doing this.
There is probably some sort of pattern, or way of using the previous result to calc the next one. So my instinct would be to get it working for some small numbers, then look for patterns.
It is not clear as to where to get the arrays A and B from.
Could you explain in detail what you understand for modulus...because I was doing what you, but I have been getting other result???....and yes...I can say to you in advance I have been looking for solution and the trouble is that power operation apparently cost a lot so the code must avoid use that operation...for that reason the use shift operator...I'm not sure why yet...but the code that I have seen use that......
going back to the modulus...for me a modulus is for example 3/2....1,5 is the normal division...and 5 is its modulus.....i think I'm doing bad this....but operator % brings that.......
I have just got it...oh my god...sometimes the easiest things are the hardest things....it's the remainder...and just that...it's not the right part of the result after the coma as I was thinking....now I can code,ehhehehe
The problem here is the 30000 fib number is way too huge, even using a big number library the cost of calculating it would be ridiculous. There is probably some other particularly clever and elegant way of doing this.
There is probably some sort of pattern, or way of using the previous result to calc the next one. So my instinct would be to get it working for some small numbers, then look for patterns.
So I noticed that array A could go from 1 to 30000, and array B might be always 1 or 2 less than the number in A.
Also, look at what the effect of incrementing (by one) the number of rungs is.
the trouble is that power operation apparently cost a lot so the code must avoid use that operation.
I am not sure whether c++11 pow function overloads are smart enough to do multiplication when the argument is an int, as opposed to doing a binomial expansion. Might pay to ask someone about that, I am not sure. Actually I will ask myself :+)
I don't know what I was thinking before...i guess I was a bit blunt...
Any element from vector B can be from 1 to 30....and pow function doesn't get int..i have already checked it...but we can always cast a double to a int...in this concrete case there won't be lose of information....I'm getting a trouble with operator %.....for the rest I think It will work , not with a good performance but It's a beggining...
So no need to worry about casting anything, and you probably should use your own power function with the shift operator. Sorry for the confusion there.
yes, I got that, the shift operator does the pow operation because the binary code is base 2...it's simple and efficient......by the way, are you from Australia or about??
About the Rugby...I'm a Spanish living in London, so maybe I 'll have a paint tomorrow watching the match...they are really surprised ( and upset too) about the final...congratulations then!!!
Normally I try to get 100% in performance and 100% in correctness but this case is beating me up, I don't know how to improve it....You said about creating a independent function for get the fibonacci numbers..but I will have the same complexity I guess...or maybe I don't see it like you do...
I think is a good idea, or why not try to get the wording done.....and get 100% in both targets, it's quite addictive
but I will have the same complexity I guess...or maybe I don't see it like you do...
No you won't, at the moment you have a for loop for the fib numbers inside the other for loop. So that makes it at least O(N2)
By separating them and assuming they both run N times, then it will be O(2N)
Calculating the fib numbers only needs to be done once, as does the initialisation of the A and B vectors. After that just do a "LookUp" of the value required.
At the moment you are unnecessarily recalculating the fib numbers N times.
I suggested only do a small number first, then look for patterns. It is the nature of these problems, brute force doesn't work - one has to come up with a clever plan.
Also with your code:
Don't have unneeded includes, particularly avoid mixing c and C++ style - you have stdio.h
Don't have usingnamespace std; it defeats the purpose of having namespaces. Google to read up about namespaces. The easiest thing to do is put std:: before each std thing, that is what all the expert coders do. Ideally ones own code should go into it own namespace/s
I would avoid having those vectors as local variables, pass them by reference into the functions instead.
You can avoid using the iterators, by employing a range based for loop instead - this is suitable because you are processing the whole container.
Always use braces for statements inside an if or loop or whatever, even if there is only 1 statement. This will save you one day when you add more code.
> The problem here is the 30000 fib number is way too huge, even using a big number library the cost of calculating it would be ridiculous. There is probably some other particularly clever and elegant way of doing this.
(a + b) mod m = (a mod m + b mod m) mod m
you need to store all the fib sequence for each possible modulo.
> Always use braces for statements inside an if or loop or whatever, even if there is only 1 statement. This will save you one day when you add more code.
I'd rather learn to indent.