|
I have a problem where I travel from point A to B and there is distance defined as `l`. In my car, I have a tank which can let me go only `b` kilometers. In `n` places there are gas stations and its cost for filling up my tank (I can only refill it fully). I start with a full tank.
What is the most efficient algorithm to get from the start of the highway to the end with the least cost?
My recent ideas:
Go with window sliding minimum algorithm to find (length is `b`) those stations where the cost is minimal. Code:
int n, range, targetDist;
scanf("%d %d %d", &n, &targetDist, &range);
int di, ci;
for (int k = 1; k <= n; k++)
{
scanf("%d %d", &di, &ci);
D[k] = di;
C[k] = ci;
}
D[0] = C[0] = bestcost[0] = 0;
for (int i = 1; i < n+1; ++i)
{
bestcost[i] = 1 << 30;
for (int j = 0; j < i; ++j)
{
int xx = bestcost[j] + C[i];
if (D[i] - D[j] <= range && xx < bestcost[i])
{
bestcost[i] = xx;
printf("(%d, %d)\n", i, bestcost[i]);
}
}
}
Input is:
3 8 4
2 1
4 2
6 3
Output is:
(1, 1)
(2, 2)
(3, 4)
So it corresponds to the cost to (i, cost(i)) - to get at i-th station, I have to pay cost(i).
How to find a minimal cost for whole distance with that information?
|
|
|
|
|
#include <vector>
#include <algorithm>
#include <deque>
#include <stdio.h>
typedef unsigned long long int ulli;
using namespace std;
void sliding_window_minimum(vector<pair<ulli, ulli>> st, ulli n, ulli targetDist, ulli range)
{
deque<pair<ulli, ulli>> minimize;
ulli j = 0;
for (ulli i = 0; i < n; i++)
{
if (st[i].first <= range)
{
while (!(minimize.empty()) && (minimize.back().second > st[i].second))
{
minimize.pop_back();
}
minimize.push_back(st[i]);
j++;
}
else
{
break;
}
}
for (ulli k = j; k < n; k++)
{
while (!(minimize.empty()) && ((st[k].first - minimize.front().first) > range))
{
minimize.pop_front();
}
if (minimize.empty()) {
break;
}
ulli tempCost = st[k].second + minimize.front().second;
while (!(minimize.empty()) && (minimize.back().second > tempCost))
{
minimize.pop_back();
}
minimize.push_back(make_pair(st[k].first, tempCost));
}
while (!(minimize.empty()) && ((targetDist - minimize.front().first) > range))
{
minimize.pop_front();
}
if (minimize.empty())
{
printf("NIE\n");
}
else
{
printf("%llu", minimize.front().second);
}
}
int main()
{
ulli n, d, b;
scanf("%llu %llu %llu", &n, &d, &b);
if (b >= d)
{
printf("%d", 0);
return 0;
}
int temp = n;
ulli d1, c1;
vector<pair<ulli, ulli>> st;
st.reserve(n+1);
while (temp--)
{
scanf("%llu %llu", &d1, &c1);
st.push_back(make_pair(d1, c1));
}
sliding_window_minimum(st, n, d, b);
}
|
|
|
|
|
|
Hello!
So I have this algorithm that outputs the highest value of an array:
Input: A[1,..,n], n>=1
Output: Highest value of an array
Maximum (A)
1. m = A[1]
2. i = 1
3. while i < n
4. if A[i+1] > A[i]
5. m = A[i+1]
6. i = i+1
7. return m
I have to prove this algorithm wrong and I'm confused how to do that, because to me the algorithm seems correct. Any advice on how to do this are very much appreciated.
Thanks!
|
|
|
|
|
What's wrong is lines 4 and 5. When i is one less than n, then you try to dereference A[i+1], which is the same as A[n], you will receive an access violation because arrays are indexed beginning from zero, not from one.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I was going to ask if his array was "zero-based", but his "spec" threw me off:
Quote: Input: A[1,..,n], n>=1
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Oh I see what you mean. You thought that he was specifying that HIS arrays were one-based. I guess it could be interpreted that way. 
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
But, if you take it that it is a 1 based array it will work, as demonstrated by the following bit of Python:
def maxi(A):
m = A[1]
i = 1
n = len(A) - 1
while i < n:
if A[i+1] > A[i]:
m = A[i+1]
i += 1
return m
modified 16-Apr-18 5:15am.
|
|
|
|
|
The error is in the line
if A[i+1] > A[i] It must be
if A[i+1] > m
|
|
|
|
|
Ha ha, the rest of us missed that. 
|
|
|
|
|
<pre>import timeit
start = timeit.default_timer()
import math
def fequals(a, b):
return abs(a-b) < 0.0000001
def matmult(a,b):
zip_b = list(zip(*b))
return [[sum(ele_a*ele_b for ele_a, ele_b in zip(row_a, col_b))
for col_b in zip_b] for row_a in a]
def area(theta):
r = [[math.cos(theta), -math.sin(theta), 0.0],
[math.sin(theta), math.cos(theta), 0.0],
[0.0, 0.0, 1.0]]
v = [[1], [-1], [1]]
point = matmult(r, v)
return abs(point[0][0]*point[2][0])
def position(theta):
r = [[math.cos(theta), -math.sin(theta), 0.0],
[math.sin(theta), math.cos(theta), 0.0],
[0.0, 0.0, 1.0]]
c_o= [[0.5, 0.0, 0.0],
[0.0, 0.5, 0.0],
[0.0, 0.0, 0.5]]
result = matmult(r, c_o)
return(result)
def OptimizeTheta(A):
if fequals(A, 1.0):
return position(0.0)
elif fequals(A, 1.414213):
return position(math.pi / 4.0)
l = 0.0
m = math.pi / 4.0
while True:
mid = (l + m)/2.0
a = area(mid)
if fequals(A, a):
return position(mid)
if a < A:
l = mid
else:
m = mid
t =int(input())
for i in range(t):
A = float(input())
cube = OptimizeTheta(A)
print("Case #{}:".format(i+1))
print(cube[0][0], cube[1][0], cube[2][0])
print(cube[0][1], cube[1][1], cube[2][1])
print(cube[0][2], cube[1][2], cube[2][2])
#GHOST999
stop = timeit.default_timer()
execution_time = stop - start
Beyond value 1.41...
it becomes extremely inefficient..
appreciate any help..
|
|
|
|
|
and this algorithm is ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
In what language was the code written?
|
|
|
|
|
|
Im building a indoor putting ramp and it will be possible to hit straight puts but also I will create breaks for variation.
I asking for help for an algorithm and the easy part of this is that the slopes will be fixed.
Imagine this like a pooltable. If a raise one side with 3cm. Which is 3 degrees to make it easy.
How much do I have to change my aim point compared to the straight putt?
Summary:
What I would like for this in the beginning.
Distance 1,2,3 Meters.
Fixed break. (Means the slope is the same on the entire surface)
Break 1,2,3,4 degrees.
2 different speeds:
One speed that the ball just make it to the hole.
Second speed that the ball ends up 70 cm behind the ball?
Why different speeds?
To show and illustrate how the aim point changes depending on how hard you roll the ball.
/Martin
|
|
|
|
|
|
I have a stored function in postgresql which is based on a recursive algorithm however this approach has some limitation especially when it's a matter of scalability, so i would like to ask if it is possible to switch from a recursive approach to an iterative approach. With the end goal being to optimize the computation time of the function.
Any answer will be very much appreciated.
Thank you.
|
|
|
|
|
Determine the maximum "depth of recursion" and then you will at least have a some starting point.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
|
Hello everyone!
I've a follow question: is there any way to optimize this algorithm, which recursively computes the square root of an positive integer?.
int mySqrt(int x, int left, int right)
{
static int result = 0;
if (left <= right)
{
int middle = left + (right - left) / 2;
if ((middle != 0 && middle <= x / middle) ||
(middle == 0 && middle <= x / (middle + 1)))
{
result = middle;
return mySqrt(x, middle + 1, right);
}
else
{
return mySqrt(x, left, middle - 1);
}
}
return result;
}
Thank you!
|
|
|
|
|
Why recursion? Binary search can be expressed as iteration, or, since you actually have a constant bound on the number of iterations here, an unrolled iteration. That would IMO still count as the same algorithm, just a different realization of it.
lnikon wrote: left + (right - left) / 2
This trick is to avoid overflow. There cannot be any overflow here anyway, since both left and right will be well below MAXINT (at most they'll be the square root of MAXINT). So you can write it the simple/shorter/faster way.
lnikon wrote: middle == 0 && middle <= x / (middle + 1)
Is this even correct? Note that the right operand of the && effectively checks whether 0 <= x which is not useful since x is known to be non-negative (pre-condition).
The whole zero business can be avoided by checking whether middle * middle > x (this multiplication cannot overflow unless incorrect bounds were passed), which by avoiding division is both "zero-safe" and more efficient.
|
|
|
|
|
Your answer is very useful. Thank you!
|
|
|
|
|
Use Newton's method[^].
You'll also need to use floating-point numbers, since most square roots are not integers.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
A square root function should have only 1 parameter and your recursive function with left and right should be for private use only.
The only way to have middle=0, is if x=0 from the beginning.
So if you check for x=0, you will not have to continuously check if middle=0 or not.
As far as I can see the only result your function can give is 0.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Hi,
I am interested on how to convert a point in 3D space (x,y,z) to 2D Space (x,y) using perspective accurate projection. I have found lots of things online showing how to do this, but they all use a bunch of stuff I don't understand like matrixes. I am only a grade 9 student so I don't know a lot of advanced math. If you guys could explain it to me in a simple way like:
x' = (something with x and z)
y' = (something with y and z)
That would be awesome
Thanks in advance everyone.
Sidenote, if you want to send me some example code please do it in python its the only language I'm any good at 
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
