Need Help in this question
Mark has 'N' days. Initially he is at position (h1,0) on the X-axis. On each day he can go to the co-ordinates (h1+a,0) or (h1+b,0) or (h1+c,0) . He can select any one of the choice he wants. Each day he can go to (+a , +b or +c). At the N-th day, he has to reach the position (h2,0). Count the number of ways in which Mark can reach (h2,0) in N days.
Values of N,h1,h2,a,b,c are large(co-ordinates and values of a,b,c can be negative as well, in some cases a=b or b=c or c=a or a=b=c)
My approach is:- At each day, I store the positions which he can reach on that particular day with the count(number of ways) to reach that position. I am using a map to do this. And this approach is not efficient.
Can somebody share a much more efficient approach ?
My second approach which must work is the variation of coin-exchange-problem :-)
Example:-
N=3,h1=0,h2=6,a=1,b=2,c=3
Answer : -7(number of ways)
1st way:-(1+2+3)
2nd way:-(1+3+2)
3rd way:-(2+1+3)
4th way:-(2+3+1)
5th way:-(3+1+2)
6th way:-(3+2+1)
7th way:-(2+2+2)
Format:-(Choice on 1st day+Choice on 2nd day+Choice on 3rd day)
Example:
2 0 0 1 0 -1
Sample Output:3
There are only 3 possible journeys - - (0 , 0, 0) , (0 , 1, 0) , (0 , -1, 0)
Constraints:- 1<=N<=10^5 .
-10^9<=h1,h2,a,b,c<=10^9 .
Values of N,h1,h2,a,b,c are large(co-ordinates and values of a,b,c can be negative as well, in some cases a=b or b=c or c=a or a=b=c)
My approach is:- At each day, I store the positions which he can reach on that particular day with the count(number of ways) to reach that position. I am using a map to do this. And this approach is not efficient.
Can somebody share a much more efficient approach ?
My second approach which must work is the variation of coin-exchange-problem :-)
Example:-
N=3,h1=0,h2=6,a=1,b=2,c=3
Answer : -7(number of ways)
1st way:-(1+2+3)
2nd way:-(1+3+2)
3rd way:-(2+1+3)
4th way:-(2+3+1)
5th way:-(3+1+2)
6th way:-(3+2+1)
7th way:-(2+2+2)
Format:-(Choice on 1st day+Choice on 2nd day+Choice on 3rd day)
Example:
2 0 0 1 0 -1
Sample Output:3
There are only 3 possible journeys - - (0 , 0, 0) , (0 , 1, 0) , (0 , -1, 0)
Constraints:- 1<=N<=10^5 .
-10^9<=h1,h2,a,b,c<=10^9 .
Last edited on
Link does no good if we have to register to read it.
> I am using a map to do this. And this approach is not efficient.
> Can somebody share a much more efficient approach ?
Maths.
Most of these competitions require you to THINK before writing code.
Just writing the code for the first thing that comes to mind is seldom the right answer.
http://www.cplusplus.com/forum/beginner/256066/
Given your propensity to change your mind, I'm not going to bust a gut saying too much.
> I am using a map to do this. And this approach is not efficient.
> Can somebody share a much more efficient approach ?
Maths.
Most of these competitions require you to THINK before writing code.
Just writing the code for the first thing that comes to mind is seldom the right answer.
http://www.cplusplus.com/forum/beginner/256066/
Given your propensity to change your mind, I'm not going to bust a gut saying too much.
man i will not delete it from onwards??
just can you help me?
i was thinking if three places can be filled by permutating the three places but it gives tle.
just can you help me?
i was thinking if three places can be filled by permutating the three places but it gives tle.
Isn't the purpose of competitive challenges to show the extent of your knowledge?
If someone had trouble to even start, then they would be successful at showing what they know and can.
The OP description contains nonsense (probably intentional distraction). Talking about "position" is meaningless, if you ever adjust just one value.
Okay, now there are four values to have: {h1, h1+a, h1+b, h1+c}
That makes no sense, if the goal is to find "paths".
It would make more sense to say: "Each day one can add a, b, or c to the current value".
That way it would be possible to "advance" towards the final value h2.
There is still "one can". Not "has to". If I can add something, then I'm at liberty to do nothing. In your first example: (0,3,3), (3,0,3), and (3,3,0) all advance by 6. Why work every day if you can get there with less effort?
I guess one has to add something every time.
There can be multiple (or none) solutions (x,y,z) for:
For each solution there are permutations.
The first example had two solutions: (1,1,1) and (0,3,0)
The (1,1,1) has six permutations.
The (0,3,0) has one permutation.
If (a=b or b=c or c=a or a=b=c), then you have less unknowns to solve. For example, if a=b=c, then (h1 + N*a == h2), or there is no path at all.
How to count permutations? Math has solution for that.
If someone had trouble to even start, then they would be successful at showing what they know and can.
The OP description contains nonsense (probably intentional distraction). Talking about "position" is meaningless, if you ever adjust just one value.
x = h1; // no problem with this each day can go to h1+a, h1+b or h1+cOkay, now there are four values to have: {h1, h1+a, h1+b, h1+c}
That makes no sense, if the goal is to find "paths".
It would make more sense to say: "Each day one can add a, b, or c to the current value".
That way it would be possible to "advance" towards the final value h2.
There is still "one can". Not "has to". If I can add something, then I'm at liberty to do nothing. In your first example: (0,3,3), (3,0,3), and (3,3,0) all advance by 6. Why work every day if you can get there with less effort?
I guess one has to add something every time.
There can be multiple (or none) solutions (x,y,z) for:
|
|
For each solution there are permutations.
The first example had two solutions: (1,1,1) and (0,3,0)
The (1,1,1) has six permutations.
The (0,3,0) has one permutation.
If (a=b or b=c or c=a or a=b=c), then you have less unknowns to solve. For example, if a=b=c, then (h1 + N*a == h2), or there is no path at all.
How to count permutations? Math has solution for that.
Last edited on
Topic archived. No new replies allowed.