Блог пользователя SecondThread

Автор SecondThread, история, 4 года назад, По-английски

Brookfield Computer Programming Challenge (BCPC)

Hi everyone!

TLDR: Speedrunnable contest here, bad solution videos + original standings here.

Last week I learned how to use Polygon, so I uploaded and regenerated data/solutions to the first contest I ever wrote, and uploaded it to the gym. The final score of the original contest is available here. In the original contest, the last problem was only unlocked after solving everything else (which no teams did). Originally this was a set for high school students in Wiscosin, but I thought some people here might enjoy speedrunning it.

Solution videos are also available here. They aren't very good because I was a young child when I made them, but they should at least convey the main ideas pretty well. The one interesting thing to mention is:

For problem LAST Robotics:

Spoiler

I hope you enjoy! Let me know if there are any technical issues, because those may indicate that I've set something up incorrectly, which was kind of the main thing I was trying to avoid here.

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Spoiler
»
4 года назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

As a tester I think people will like this round because of interesting problems,diverse topics and short statements

»
2 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I know that this post is two years old so most people probably don't care, but I found what I believe to be an error in one of the test cases. The issue is in Problem G, "Bike Race". I submitted what I thought to be a good BFS solution (code is here: https://codeforces.me/gym/102680/submission/164928358), but unfortunately, it did not pass the second test case.

I was confused by this, and after I tried a few more submissions, I decided to look at the problem test cases provided by this website: https://wumbogames.com/BCPC/BCPC1. While I believe that most of my solutions match, there seems to be an issue with the 11th test case (it starts with "10 10"). While the official document suggests the answer should be 8, my program printed out 5, which I believe to be the correct answer. This is because the graph provided is just a circle (1-->2, 2-->3, ... 9-->1), so the maximum distance between nodes, assuming the bikers move optimally, should be no more than 5. But the solution document says the answer is 8.

It's worth noting that all the solutions found on the contest website are 1 larger than the actual solutions, as currently, Codeforces lists the solutions to the shown problems as 1 and 4, while the document lists them as 2 and 5. I believe that this is because the document assumes we're looking for the # of intersections (nodes), while Codeforces is looking for the # of roads (edges).

Does anyone know what's going on here? Am I just crazy? Also, SecondThread, if you are reading this, I am a big fan! I tried this problem in the middle of watching your AlgorithmsThread 8: Tree Basics video.