USACO January 2024 Bronze problem 2

Solution by Stanford M.S., AlphaStar full-time USACO Instructor, Alex Moreira.
While watching him, you can learn:
★ Contest strategies
★ How to approach the problems?
★ How to solve the problems?
★ Implementation tips
Please check usaco.org/ for the details of the contest
Don't forget to subscribe our channel!
If you're interested in USACO contest preparation or currently competing at USACO, you can check our USACO training courses at: alphastar.acad...

[@ethanwu5431]

You can very easily figure out when bessie is stuck in a loop, if she is stuck in a loop, that means she is stuck between to boost pads that don't increase her V. Therefore they get hit and then reverse bessie direction so on and so forth. If that weren't the case, then bessie wouldn't be stuck in a loop. You create a "lastboostpad" variable and store it and if its 0 and the current boostpad is 0 v, then you can stop you're program because bessie is in a loop that you have already iterated over once. The runtime of this problem is 100000/1+100000/2+100000/3+100000/4......+100000/100000 which is approximately O(n log n).

[@shors5841]

okay but his point still stands that there’s no need to do this in a comp

[@passionyu1309]

I love the solution, but can you code it in c++ if possible?

[@boas_]

I think a better solution is to create a set with the number of targets broken, the current position and the current v value, and check in each iteration of the loop if the exact same three values occurred earlier, and if so: stop immediately

[@adbb1404]

Instead, I think you could create the following:
An array "powers" with size of N
Initialize all values to 0
When Bessie lands on position i if Bessie's power is equal to powers[I] break the loop. If not set powers[I] to Bessie's power. I mean this is very similar to your approach but might have a slight time advantage

[@Foodtruck53]

W solution lmao

[@pinruihuang8463]

That's just kind of dirty. Instead, figure out whether you're bouncing between boost pads with power 0.

[@Foodtruck53]

Who tf cares if its dirty. You passed the problem 💀.

[@pinruihuang8463]

@@Foodtruck53 Brian Dean might DQ for dirty sols like that one

[@Foodtruck53]

@@pinruihuang8463 Nothing in the rules states the possibility for a disqualification by using probability. Only thing it says is to not have a program that generates different results each time. Clearly that isn't the case here.

[@pinruihuang8463]

@@Foodtruck53 Using feedback to reverse engineer the solution is banned.