[Community Puzzle] Beach volleyball

Puzzles
#1

Creating the topic manually as bot failed to do it

https://www.codingame.com/training/medium/beach-volleyball

Send your feedback or ask for help here!

Created by @Wontonimo ,validated by @LazyMammal @LastRick and @Westicles
If you have any issues, feel free to ping them.

#2

Validator 2 introduces an edge case where ballX < playerX that is never tested in the IDE.
Please fix, this is not good design.

#3

I don’t know why you would assume that ballX and playerX are always ordered the same way but I interverted ballX and playerX in testcase 2 so there should be no surprise now.

1 Like
#4

Thanks, inverting them is fine, but dropping it as a surprise during validation is not. Those who don’t have access to the contribution won’t understand what’s going on.

1 Like
#5

LOL - after seeing brute-force is not viable because of the huge range of possibe solutions, I tried to solve this on paper with calculus but failed miserably when the equation became of degree 4… Then my thoughts were around gradient descent and I started to feel dispair.
But in the end it turned out that this is much simpler than that, as f() has no other local minimums.
Using so much zoom last year should have given the idea earlier… :slight_smile:

#6

I also tried analytically but I’m to rusty for that now.
Brute force works fine when you take into account that the result has to be an integer :wink:

1 Like
#7

If you consider T(x) the time spent to reach the ball depending on the x you choose, then the derivative T’ is not too hard to calculate.
And then whatever formula you get, even if you have squareroots, powers etc, you just have to find its zero so even if you cannot solve the equation for exact value, any method that gives a good approximation of a zero would be fine (dichotomy, newton, etc).

#8

I am not sure about that, x range in the last test case is 20M integers.

Sure, but then it is no longer the analytic solution on paper I originally aimed for… :slight_smile:

Anyhow, a simple ‘zoom-in’ type of search is simpler than any newton and also works here as the time() seems to be monotone decreasing to the global minimum, then monotone increasing.
My post was meant more about the thought process than about the solution. :slight_smile:

#9

I just brute force all the way and it passed all test cases and validators.

Had it been not so easy, I would have used bisection to reduce the number of calculation.

#10

yeah i was trying to use wolfram alpha and im not even gonna mention how long i spent before actually just coding a solution

#11

There is mistakes in dart code of this puzzle

#12

What do you mean? Please provide more details. Thanks.

#13

after dart 2.12 there is null protection. But code is still for old version of dart.
List? inputs;
inputs = stdin.readLineSync()!.split(’ ‘);
int STARTX = int.parse(inputs[0]);
int STARTY = int.parse(inputs[1]);
int BEACHY = int.parse(stdin.readLineSync()!);
inputs = stdin.readLineSync()!.split(’ ');
int BALLX = int.parse(inputs[0]);
int BALLY = int.parse(inputs[1]);
int SPEEDLAND = int.parse(stdin.readLineSync()!);
int SPEEDWATER = int.parse(stdin.readLineSync()!);

#14

Do you mean the default code works, but should be updated? Also, is it more of a general issue instead of an issue on this particular puzzle? If so, I would suggest you to open a new topic to raise the issue. Thank you.

1 Like