https://www.codingame.com/training/hard/legendary-archer-octavius
Send your feedback or ask for help here!
Created by @UnicornP,validated by @Nagato_Uzumaki,@King_Coda and @EliteDaMyth.
If you have any issues, feel free to ping them.
I don’t understand how can be 6.89 the right solution for the “Trivial” test case.
There are 2 UFOs, so aiming from first watch tower is already 2 * 3 sec.
Traveling to the second watchtower is out of question, because of the 20 sec travel time.
As first tower is at x = 0m, first UFO is at x = 200m, and arrow speed is 60m/s, the flight time is surely >3 sec for this one shot alone, so Total solution is surely >9 sec.
My solution is 10.27.
Or do I misunderstand something in the statement?
As a sidenote: choosing x and z for the horizontal coordinates, and y for the vertical one was rather odd choice…
1 Like
I have the same doubts. Some clarification from the problem creator would be much appreciated.
The aim time for the second UFO overlaps with the travel time of the first shot.
1 Like
Oh, this archer is clever… 
This puzzle is more interesting (and harder) than I originally thought.
Ah, interesting. Thanks for the clarification!
I guess the the arrow does not travel in straight line. It involves projectile equations in calculation, does it?
Yes, it is a parabole because of gravity. Had to use secondary school physics.
In my understanding the puzzle has two distinct parts:
- calculate arrow travel times (depending also from source watchtower and Oreo usage)
- schedule /order the firings / move / eat in an optimal way.
I am almost there (75%), just having off by exactly 1 or 2 secs in some test cases.
I guess the projectile equation is easy to google but if you want to find the equation by yourself, you can start from here:
from Newton’s second law,
mass * (acceleration vector) = sum of forces
Here the only force is gravity so:
mass * (acceleration vector) = mass * (gravity vector)
Thus:
acceleration vector = gravity vector
From there you can deduce speed vector (dspeed / dt = acceleration), and then position (dposition / dt = speed).
I’m trying to figure out arrow flight times using kinematics:
final position = initial position + initial velocity * time + 1/2 * acceleration * time^2
time = displacement / velocity
y velocity = velocity * sin(angle)
x velocity = velocity * cos(angle)
And I’m running into a wall trying to find the angle that the archer must fire at; winding up with an equation that I can’t solve containing multiple squared trig functions. The ballistics section of my Physics 200 textbook actually says something like “finding projectile firing angles from one height to a different height is too much algebra for this book”. Am I making this harder than it needs to be?
1 Like
You’re on the right track, just note that the “x” you use is actually the “horizontal distance”.
I’ll call that “x” h to avoid confusion.
Now try to get a more explicit formula for h and y positions.
Then you can calculate, for a given angle, the time it takes to reach the desired y.
Inject this time in the h equation and you can deduce the angle needed to reach both h and y you’re aiming at.
(Try to express everything with tan(angle).)
You’ll have to deal with edgecases, when the target is at the same h coordinate for example.
Also if somewhere in your calculations you have to deal with squareroots of negative numbers, it will usually mean that the target cannot be reached, so you can return an “infinite” time in this case.
1 Like
Success!
I wussed out on the algebra and found my firing angles by estimation. It was possible to dial in angles to within microns of a “hit”, and recognize “misses”, with ~100 guesses per UFO. That actually worked out to be less time-complex than my scheduling routine so it didn’t muck things up noticeably, time-wise. Could’ve been tighter and prettier with an unknown additional amount of work. Like everything.
1 Like