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

Автор codepasta, 14 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
14 месяцев назад, # |
  Проголосовать: нравится +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.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +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)

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Well it just happened 0_0

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 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

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится 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.

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится +43 Проголосовать: не нравится
Story from the university where I work (unfortunately, real)

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.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +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?