Problem statement made by the author:
Given a list of N cities and the distances between M pairs of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? (N, M <= 2*10^5)
Intended solution by problem author: write a greedy or DP in $$$O(n^2)$$$
What actually happens during the contest: author discovers that this is actually an NP problem and cannot be solved for big N, M. Contest becomes unranted because of bad problem.
Conclusion: always check for impossible problems before the contest.
That situation cannot happen, since in order to publish a contest, the author must, obviously, write the solution first, then get the entire problem + solution get reviewed by people who know exactly what they're doing, then these problems will have to go through some testing before the contest are held on Codeforces. That process can take like months, so there's no way an impossible problem can slip in . Don't tell experienced people who know what they're doing how to do their job, while your contest history looks literally like a binary string lol.
"your contest history looks literally like a binary string lol"
Seriously though, that's the funniest insult I've seen on codeforces for a long time, I've been laughing for 2 minutes =))))
(by the way, this blog is a parody, of course no sane mind would accept a problem like TSP into a real contest)
Well it just happened 0_0
Which contest? I only upsolved the A, B, C, D question of the recent contest, so I don't know when did it happen
[problem:1780C] is impossible within the limits. Everyone who "solved" it (including the authors) used a greedy method which fails on some test cases. See the announcement of that contest (and the comments there) for more info.
A year ago, a professor gave 3rd year students a theoretical test on graph algorithms. This test contained the following question:
Question: the classical Travelling Salesman problem is formulated as follows. You have to find the shortest path that visits all cities at least once and returns to the starting city. Which algorithm can be used to solve it?
Answer options:
building a spanning tree
building a minimum spanning tree
Bellman-Ford algorithm
Depth First Search
Correct answer: building a minimum spanning tree
Explanation: "Well, that's obvious"
When I got sent this by one of the students, my initial reaction was just WTF. Unfortunately, I wasn't able to convince the faculty dean that this professor was incompetent to conduct the graph theory course because, well, she's a professor, and I'm just a random bozo who coaches CP.
In all seriousness, when I read problem C, my first reaction was "this looks NP-hard af, how do they actually solve that? Do they have a concrete proof? I think they don't", and it turns out my skepticism was correct. Nevertheless, I feel like in general, the problems were nice. It's unfortunate that the contest was ruined by that single problem, people responsible for other problems don't deserve the criticism on the whole contest.
Lately, I have realized that this is way too common in academics. I feel like a lot of people with PhDs have never implemented any of the algorithms they learn, and honestly, it feels like sometimes they have no idea what they are talking about. Personally, I have seen the following two cases:
A professor gave an assignment to students to find the shortest path in an unweighted graph. A friend of mine implemented BFS because I told him it is faster and more simple than Dijkstras for this scenario. The professor replied with the following: "Using BFS for the shortest path calculation is extremely slow. The reasoning behind using BFS over Dijkstras algorithm is not convincing". When I heard this, I was banging my head on my desk, this really makes me think that they have never implemented BFS in their life. This person is a professor at a well-known university teaching advanced computer networks...
Another professor had the following question in a final Algorithms and Complexity exam: "Describe a dynamic programming algorithm". Most of the students answered "Fibonacci" to this question. He literally gave zero credits to the students that had this answer, arguing that "Fibonacci is just a simple arithmetic calculation". When I argued back that in that sense, even 0-1 knapsack can be considered "a simple arithmetic calculation", plus that it is literally a basic memorization example in the "Cracking the coding interview book", he said that "you are not a professor, nor an algorithms expert" (aka a random bozo as well, that doesn't even teach CP :)).
I wonder how common is this nonsense in academics. Has anyone else had similar scenarios?
"You are not an expert." — I find that funny because you literally are an expert by CF standards.
Haha, apparently CF is a bozo platform for his standards :P