Having trouble finding the fault in my logic for this coding question(it's heavily math related)

Question

So I have been doing some coding questions to practice my coding and I ran into this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=989

The general gist of the problem is that there is a person named Bessie is racing a length of $K\ge1$ meters. She starts at $0$ meters per second at the $0$ second mark, and then every second after that, she can either increase her speed by $1$ meter per second, stay at the same speed, or decrease her speed by $1$ meters per second. Her speed can not drop below zero(so if Bessie is at $0$ meters per second, she can not decrease her speed.).

Bessie wants to finish the race in an integral amount of seconds, either finishing at the $K$ meter mark or past the $K$ meter mark. But Bessie also doesn't want to finish the race too quick. At the instant when she finishes $K$ meters, she wants to be traveling at a speed of no more than $X\ge1$ meters per second. Bessie wants to know the minimum speed required to finish $K$ meters, given $K$ and $X$.

---

The logic I use to solve this problem only works for the first 4 test cases, and I'm sure it's not because of an coding error. So my logic is as follows:

Before we do anything, we first have to test whether or not a speed of $X$ meters per second can be reached, as the following solution assumes that $X$ meters per second is reachable.

To do so, we first note that the quickest way to get to $X$ meters per second is to increase the speed by $1$ each second for $X$ seconds. We then note that if after increasing $X-1$ times, if the distance covered is $<K$ meters, then it is guaranteed that $X$ meters per second is reachable. But if after increasing $X-1$ times the distance covered is $\ge K$, then we know that $X$ meters per second is unobtainable.

To calculate the distance covered after $X-1$ increases, we can calculate the following sum:$$1+2+\cdots+(X-2)+(X-1)$$which can be represented as$$\frac{X(X-1)}2$$. We want to test whether or not$$\frac{X(X-1)}2\ge K$$. If this inequality is false, then go to the solution under the gray line. If this inequality is true, then we know $X$ meters per second is unobtainable, and therefore we need to calculate how many increases are required to surpass $K$ meters. We will call this amount $n$. To find the value of $n$ that will cause the distance to go over $K$ meters, we first need to find the formula of the distance covered after $n$ increases. That can be represented with the sum $$1+2+3+\cdots+n=\frac{n(n+1)}2$$. So then we set this sum to be $<K$, then use this inequality to maximize $n$:$$\frac{n(n+1)}2<K\\\frac{n^2+n}2<K\\n^2+n<2K\\(n+1/2)^2-1/4<2K\\n+1/2<\sqrt{2K+1/4}\\n<\frac{\sqrt{8K+1}-1}2$$So the value of $n$ would be:$$n=\left\lceil\frac{\sqrt{8K+1}-1}2\right\rceil$$(without the ceiling function we would be calculating the largest amount of increases that doesn't surpass $K$ meters, instead of actually passing $K$ meters)

---

First we want to find the maximum speed in which Bessie can go at. Let's say that this maximum speed is $m$ and the target speed(the speed we want to have at $K$ meters) be $X$ meters per second(as stated in the problem). We can find the maximum speed by allowing Bessie to increase its speed every second until it reaches $m$, then immediately start decreasing her speed until she hits $X$ meters per second. We then know that the total distance traveled after this increase and decrease is(which I will denote as $d$): $$d=\underbrace{1+2+3+\cdots+m}_{\text{increasing speed}}+\underbrace{(m-1)+(m-2)+\cdots+(X+1)+X}_{\text{decreasing speed}}$$. We can then find the formula for this sum to be: $$d=m^2-\frac{X(X-1)}2$$. This sum has to be $\le K$(or else we can't decrease enough in time), so we have the following inequality:$$m^2-\frac{X(X-1)}2\le K$$. $K$ and $X$ are already given as inputs in the problem, so we just have to isolate $m$. We get that: $$m\le \sqrt{K+\frac{X(X-1)}2}$$(positive square root). To get the highest $m$, we just need to take the floor of the RHS so:$$m=\left\lfloor\sqrt{K+\frac{X(X-1)}2}\right\rfloor$$. Then if $d$ is $<K$, we need to find out the remaining distance that we need to cover. That is easy to calculate: $K-d$. From this we can calculate how many seconds we need to stay at $m$ meters per second(if we stay at a speed $<m$, we can always stay at a higher speed to potentially reach $K$ meters quicker. Not too sure about this logic though). Each second we stay at $m$ meters per second adds an extra $m$ meters to our distance. So we need to divide $K-d$ by $m$ to see how many times we need to add $m$ to $d$ to reach $K$(I will denote this as $s$). So we get that we need to stay$$s=\left\lceil\frac{K-d}m\right\rceil$$seconds at $m$ meters per second to pass $K$ meters. Then we need to calculate the amount of seconds that passed for traveling $d$ meters using the method stated. To calculate this, we need to count how many terms we added together in the sum. So we need to find the length of this list:$$1,2,3\dots,m,(m-1),(m-2),\cdots,(X-1),X$$This can be calculated with the following formula: $$2m-X$$So finally we calculate $$2m-X+s$$ to obtain the final answer.

---

The problem is this only works for the first 4 test cases, and this strategy only works for certain values of $K$ and $X$ past test case 4, and is really close to the actual answer for other values(yes, I downloaded the test data), so I'm actually not too sure where I went wrong here. If you guys want the code I can also put it here, but this is more of a math problem, so I decided not to put the code for now.

Answer 1

The error is in assuming that the form must be

We can find the maximum speed by allowing Bessie to increase its speed every second until it reaches $m$, then immediately start decreasing her speed until she hits $X$ meters per second.

Do you see why?

For large $X$, if the previous second gets us really close to the finish line, then it might be possible that we have a smaller minimum speed so that we can slow down earlier and finish the race faster. Yes, the total distance covered will be smaller (but as long as it's longer than the race, we're fine).

---

In fact, assuming that the race must be of your form (increase or decrease every second, end with X), then there are some distances which do not work out (as you pointed out).

For example, with $X = 5$, $K = 40$, you'd calculate a max speed of $7 < \sqrt{ 40 + \frac{5\times 4}{2} }$. We verify this with $1+2+3+4+5+6+7+6+5 = 39 < 40 < 54 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 7 + 6 + 5 $.
However, she then can't run a increasing/constant/decreasing race with a max speed of 7, an end speed of 5, a distance of 40 since
$1 + 2 + 3 + 4+5+6+7+7+6 = 41 $.

Answer 2

This is how I would approach:

First let us assume that $K \ge \frac{X(X-1)}{2}$; otherwise accelerate as quickly as you can to the finish.

ETA This is the problem with the formula in the OP; it is correct only if Bessi reaches a speed of $X$ or greater. She will not if the inequality $K < \frac{X(X-1)}{2} -X$ is satisfied. If $K \le \frac{X(X-1)}{2}$ then let $l$ be the smallest integer such that $\frac{l'-1}{l'} \ge K$ is satisfied, then that is the time needed to run, and the schedule is $1+2+ \ldots + (l'-1)+ l'$.

For each integer $l >X$, let $f(l)$ be the furthest one can travel in $l$ seconds so that one is traveling at speed no more than $X$ at the end. Then for $l \ge X$:

$$f(l) = 1+2 + \ldots + m_l + (m_l-1) + \ldots + x$$

where $m_l \doteq \frac{l+X}{2}$ if $l+X$ is even and

$$f(l)= 1+2 + \ldots + m_l + m_l + (m_l-1)+ \ldots + x$$

where $m_l \doteq \left(\left \lfloor \frac{l+X}{2} \right \rfloor\right)$ if $l+X$ is odd.

Also: if there is an $l'$ such that $f(l')=K$ then that is the time it needs to finish the race. Note that $l' > X$ so use the above to get a schedule that goes precisely $f(l')$ in $l'$. Otherwise, let $l'$ be the largest integer such that $f(l') < K$. Then $l' \ge X$, and also, the time to finish the race is at least $l'+1$. We now show that there is indeed a schedule that finishes in time $l'$, where the maximum speed is $X$:

If $l+X$ is odd let $d=K-f(l')$; then $1 \le d \le m_l$. If $d \le X$ go at paced $X$ at second $l'+1$; otherwise go at speed $d$ for another second.

If $l+X$ is even let $d=K-f(l')$; then $1 \le d \le m_l-1$. If $d \le X$ go at paced $X$ at second $l'+1$; otherwise go at speed $d$ for another second.

Answer 3

I checked based on the example you gave. Yes your earlier solution did not handle the case when you crossed the finish line before you could attain $X$. On your new logic to handle that case, you need to modify it a bit. Also there are a few other problems as I suspected on boundary conditions.

A) Problem with the newly added logic -

Take an example of $K = 10^9, X = 44721$

$\frac{X(X-1)}{2} = 999961560,$ which is less than $K$. So you would go to your original logic. That will give you a max speed of $44720$ and you will stay at that speed for $(k-d)$ distance to cross the finish line. But this is not optimal. You can attain the speed of $44721$ before the finish line and cross at that speed. (Or you fix your max speed logic that currently considers floor function that I have called out later, it would work too).

So you should check whether $\frac{X(X+1)} {2} \geq K$ and your formula for $n$ works.

B) On your original logic -

i) you are not attaining max speed every single time. Take example of $K = 22, X = 5$. Your logic will get to max speed of $5$ but you can actually attain $6$. Another example is $K = 27, X = 4$ or $K = 31, X = 3$.

So please fix your logic to calculate $d$ as per (ii). Then to find maximum speed,

$m$ is either a floor or a ceiling (Round function does not work for all cases either. I checked further.). There are two ways to fix -

Take $m$ as floor like you are doing right now and then do a test with $m + 1$ to confirm whether $m$ or $m+1)

or

Take the floor to find $m$ the way you do right now. Recalculate $d$ and check whether $(K - d + X - 2m) \geq 2$. If so, you can attain speed of $m + 1$ and you will still be able to get back to $X$ and cross the finish line.

ii) It is not clear how you calculate $d$. As per details in your questions,

You calculate $d=m^2-\frac{X(X-1)}2$. Then go on to calculate

$m=\left\lfloor\sqrt{K+\frac{X(X-1)}2}\right\rfloor$ but I do not see you refreshing $d$ based on the final value of $m$ you choose (which is a floor function). You should do that.

iii) Last point - calculation of $s$. While the final answer $2m - X + s$ comes correct. It needs a bit more clarification as there may be two different speeds (adjacent) at which you go for more than a second. Take example of $K = 29, X = 3$. How long will you go at speed of $m = 5$ beyond one initial second? It should be one more time (till distance is $20$). Then you go twice at a speed of $4$. Then you reduce to $3$. Your logic does not fully clarify that though the final answer works.