Were you able to get ahold of someone in Aneo’s team about the article I was looking to publish?
Unfortunately, they’re not replying to us.
We’ve decided to remove this puzzle from the platform. So I’d say that you can publish your article, even if the puzzle won’t be up anymore 
Is the removal decision due to sponsorship ? In that case, instead of retiring the puzzle, would it be possible to redesign it ? I think it is a very valid puzzle for noobs.
In this respect, I have stumbled recently on the retired puzzle “The Great Dispatch”, a NP complete problem, which I find quite interesting. Would CG accept that someone submit a similar optim with a rewritten statement and reused test cases ?
3 Likes
Yes, feel free to reuse TGD’s puzzle idea and its test cases.
Same goes for ANEO’s challenge. The puzzle’s rating wasn’t that high so I didn’t mention it.
2 Likes
Unfortunately, they’re not replying to us.
We’ve decided to remove this puzzle from the platform. So I’d say that you can publish your article, even if the puzzle won’t be up anymore
I understand. Thanks for the update. I’ll probably describe the puzzle and let people know the link may not exist for much longer.
i solved this puzzle using the brute force approach: for all traffic lights and for all speeds calculate if it gets through all green. then take the highest speed that got through.
i noticed that speed given in km/h but traffic light distance and duration given in meters and seconds. at first i thought this was the puzzle designer being careless. but then i thought that it (very likely) was a deliberate decision to enforce the rounding errors.
i think this puzzle main challenge is to understand that the computer does not store numbers in arbitrary precision. i think the numbers in the puzzle are deliberately chosen to trigger those 59.99999 rounding errors.
here is my attempt for an explanation of the rounding problem. i hope it explains the .999999 results many people (including me) are stumbling upon in this puzzle.
let’s go back a couple of decades and be in the bussines of manufacturing calculators. because of cost constraints you can only handle four digits in the processor (let’s pretend processors calculate using decimals). that means the largest integer is 9999 and the smallest non zero is 0001 (let’s also ignore negatives. they add nothing to the rounding problem).
now you want to allow non integer division (for example 100/3=33.333…). you can introduce a decimal point somewhere between the four digits. for example right in the middle. that allows you numbers like 33.33. but now your largest number is only 99.99 and the smallest non zero is 00.01.
better is a floating decimal point. that means the decimal point floats left and right on the display as needed. so the largest number is still 9999.0 (with .0 off screen) but the smallest number is now 0.0001 (with 0. off screen).
(this is why floats are named floats. because the decimal point can float left and right as needed. doubles are named doubles because they are “double” as precise as floats).
now we come to the rounding problem.
suppose you have 0.0011 as value (remember the 0. is off screen). now you divide by 10 then multiply by 20. result should be 0.0022. right? wrong. when you divide by 10 you lose a digit. because the calculator can only handle four digits it can’t handle 0.00011 (five digits). instead it stores 0.0001 (four digits) as result. if you now multiply by 20 you get 0.0020.
similar problem when adding large number to small number. for example 100.0 and 1.01. both numbers are not too near the edge of precission. still if added the result is 101.0. one digit is lost.
one advantage of floating point is that the lost digit is always the least significant digit. but still, if you are not careful, if the puzzle is designed around exactly this digit, you will get wrong results because of “rounding errors”.
i hope you understand now why the rounding errors in this puzzle are not stupid but instead are … the puzzle. (though i think it could have been communicated a bit better)
how to solve (or at least reduce) this problem? (besides more precision?) reorder the operations.
observe the examples above:
(0.0011 / 10) * 20 = 0.0020 (digit lost)
(0.0011 * 20) / 10 = 0.0022 (no digit lost)
rule of thumb: if you have small numbers then multiply first before divide.
in this puzzle we have neither very small nor very large numbers. instead we have numbers presumably tailored to trigger enough lost digits to get 59.99999… instead of 60.00001…
still; thoughtfully reordering multiplications and divisions solved this puzzle at least for me. and it seems for some other fellow perhaps unknowingly: https://www.codingame.com/forum/t/aneo-sponsored-puzzle-discussion/42954/36
or you can “cheat” and say if the difference from x is less than 0.0001 then then number is x for crying out loud. (actually this is done more often than you might think).
or you can prevent most rounding by calculating using fractions. the rounding then happens only once when forcing the fraction back to a real number.
or, maybe, you can use another algorithm that does not use floating point division. at least some post alluded to that possibility. although i did not understand whether they meant another algorithm or just meant to just do integer division. https://www.codingame.com/forum/t/aneo-sponsored-puzzle-discussion/42954/130
okay this post is long enough. i hope you learned something from reading this. that would make me happy. even though i might never know.
bonus:
you don’t even need complicated calculations to trigger “rounding errors”. a simple 0.1 + 0.2 is enough.
here is a short explanation: https://0.30000000000000004.com/ including a thorough list how different programming languages deal with this phenomena.
and here is a detailed explanation and calculation of what exactly happens down to the bits: https://betterprogramming.pub/why-is-0-1-0-2-not-equal-to-0-3-in-most-programming-languages-99432310d476
i had a course in university about this problem. it was not fun. but insightful. like probably most courses in school.
2 Likes
I know it is forever later, but since no one has replied to this, I’ll leave one to help people in the future. The object of this puzzle was to find a solution where precision doesn’t matter. It is more of a math problem than a coding problem, but is necessary way to think when dealing with precision. The most comprehensive way to solve this will require NO floating point numbers. The “arbitrary” choices were to force you to find a way around precision. Also, if you think you are crossing lights before they turn green you are doing the math wrong.
I think the skill “Modular Arithmetic” would be more appropriate rather than “Arithmetic”
Honestly, an awesome puzzle. If going the “obvious” route it presents you with some serious problems to solve in terms of floating point precision. If those are avoided by using integer calculations only, it was still a nice challenge using Modular Arithmetics.
For people beeing stuck, try to think in distance traveled during duration instead of time to the light.
Probably a dumb question, but how many states do the lights have? 2? or 3?
2 states. Light is either green or red.
A traffic light alternates a period of duration seconds in green and then duration seconds in red
2 Likes
Thank you! I’ll try that out. I was having a big problem with the math. Tried so many times, but some of the test cases just don’t work out
I’ll try it out. Thanks for the new perspective! : D
let’s take an exemple:
the light is at 1000m
the speed is 60Km/h or 60 * 1000 / 3600 ms ( 60 / 3.6 )ms for short
if you try to compute the time to reach the light by doing
1000 / ( 60 / 3.6 ) there is a chance you get a fancy float cause 60/3.6 is a fancy float
but if you remember that a / ( b / c ) = (a * c) / b
you do ( 1000 * 3.6 ) / 60 and you get the proper time aka 60 sec
4 Likes
Lang: JS
There is an error that it lets the distance and duration not being defined. Mean I cannot use the input that it gives.
With the following js code, input is displayed … :
const speed = parseInt(readline());
console.log(speed);
const lightCount = parseInt(readline());
console.log(lightCount);
for (let i = 0; i < lightCount; i++) {
var inputs = readline().split(' ');
const distance = parseInt(inputs[0]);
const duration = parseInt(inputs[1]);
console.log(distance);
console.log(duration);
}
I don’t see any error or bug.
1 Like
try to split the per_sec_speed it goes to infinite length float value to 16.6666666666666…for 7th case that change to 16.66666666667 by default in python and c.
try to split the string and get upto 10 by splitting and that case should be pass
its because python and c return float(1) value equal to 1.00000000000004591 something like that, its Language’s internal problem
although the first “village” tests are supposed to be the easiest, they are the only ones i can’t do atm. somethings about my code just doesnt want to work with only one traffic light 
umm i dont understand the problem ;(
Continuing the discussion from ANEO Sponsored Puzzle discussion:
please i need some help. i try to understand the problem but cant so i am very confused.
This is the comment that finally got me my last two tests. I’m too far removed from algebra these days.