### codepasta's blog

By codepasta, 17 months ago,

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.

• -19

 » 17 months ago, # |   +5 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.
•  » » 17 months ago, # ^ |   +13 "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)
•  » » 17 months ago, # ^ |   +1 Well it just happened 0_0
•  » » » 17 months ago, # ^ |   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
•  » » » » 17 months ago, # ^ |   0 [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.
 » 17 months ago, # | ← Rev. 2 →   +43 Story from the university where I work (unfortunately, real)A year ago, a professor gave 3rd year students a theoretical test on graph algorithms. This test contained the following question: Screenshot of the question Translation for those who don't know RussianQuestion: 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 treeExplanation: "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.
•  » » 17 months ago, # ^ |   +18 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?
•  » » » 17 months ago, # ^ |   +3 "You are not an expert." — I find that funny because you literally are an expert by CF standards.
•  » » » » 17 months ago, # ^ |   0 Haha, apparently CF is a bozo platform for his standards :P