KAN's blog

By KAN, 12 months ago, In English

Hi all!

The official Codeforces problemset contains more than $$$10\,000$$$ problems from past rounds. We try to prepare the problems as good as we can by the time we hold the round, but we don't have enough resources to also take care of them later on. As time goes, it can happen that older problems become broken in various sense. Also, some mistakes can be found. In the context of the new feature of sampling random problems, and the blitz type matches, I want to try to find and fix these problems.

Some of the issues can be identified automatically, but many can't. I'd like to therefore ask you to comment here with links to the problems that you find broken. Please use the [problem:1A] tags to link the problems like this: 1A - Theatre Square, and specify the issue. Examples of possible issues:

  • Incorrect main solution.
  • Incorrect tests.
  • Severely inappropriate time or memory limits.
  • Incorrect statement, or broken English. (Please don't include problems that may be not very easy to understand, but that don't have any formal errors in the statement.)
  • Statement relies on the statements of another problem (e.g., the harder version's statement is not complete).
  • Problem is not self-contained, requires some context (e.g., "Print the name of the contest.").

Do not include problems from language-restricted, April fool's, or marathon rounds.

To keep the comments organized, please don't duplicate the problems. However, I'd like to ask red members of the community (GM or higher) to verify or decline the issues suggested by lower-rated people, one verification per problem is enough.

Thank you!

  • Vote: I like it
  • +215
  • Vote: I do not like it

»
12 months ago, hide # |
 
Vote: I like it +33 Vote: I do not like it

I see blitz matches going to a high level in the near future...Interesting :))

»
12 months ago, hide # |
Rev. 3  
Vote: I like it +27 Vote: I do not like it

670D2 - Magic Powder - 2 is the difficult version of 670D1 - Magic Powder - 1, but its statement is incomplete.

819A - Mister B and Boring Game has wrong model solution.

»
12 months ago, hide # |
 
Vote: I like it +44 Vote: I do not like it

Does incorrect problem ratings count as an issue?

  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Let's say yes if the rating is off by more than 500.

    • »
      »
      »
      12 months ago, hide # ^ |
       
      Vote: I like it -7 Vote: I do not like it

      Seems reasonable. I have a recent example: 2066A - Object Identification, which clist says is 1855 (rounding up, 1900), but it's rated 1400 on CF. I think this is particularly noteworthy, because 800-1600 is the rating of problems that beginners try to solve, and thus it affects a lot more people than, say some 3000 being rated 2400, or something.

    • »
      »
      »
      12 months ago, hide # ^ |
      Rev. 2  
      Vote: I like it -13 Vote: I do not like it

      Most Div. 3 and Div. 4 problems rated at least 2000 (and definitely true for those rated at least 2400) deserve at least a 200-300 rating point deduction (I know the formula isn't perfect but it skews things too much for these problems), as their true difficulty is much lower than similarly rated problems in Div. 1 or even Div. 2 contests. It affects practice habits of many users who use rating based filters.

      One example of a problem which is around 500 rating off is 863B - Kayaking, which can be reduced to a simple sorting and brute force. I can come up with other examples too if needed.

      • »
        »
        »
        »
        12 months ago, hide # ^ |
         
        Vote: I like it -7 Vote: I do not like it

        Actually, my comment was about cases where the rating given by Codeforces does not align with the rating according to the rating system (clist or TLE, where the rating system is implemented as-is). I think the example you're giving (Div 3 contests) is where Codeforces rating aligns with the rating according to the rating system, but due to lower average skill of users, the problems are rated higher than you might expect from their difficulties. Back when I was Div 3 eligible, I thought the problems were quite appropriate for their difficulty levels, and I think lowering the rating for such problems is quite subjective, because in the end, the rating system for those problems says something different, and if we modify that, it sets a bad precedent in my opinion, where we're willing to give higher weight to the subjective difficulty opinions of higher rated users. For tourist, the problems of Div 2 might seem very standard and uninteresting, and thus he might rate them around 300 points lower than what they actually are, but that doesn't change the fact that the formula says something else, and in the end I believe that what the formula says should be treated as truth, and not the subjective opinions of higher rated users. In fact, the comment is only about the cases where the formula as implemented by Codeforces somehow glitches (but the clist.by and TLE seem to work fine), and this is unanimous (the I being 1900 rated is obviously a glitch), and not about subjective higher/lower ratings of problems.

        • »
          »
          »
          »
          »
          12 months ago, hide # ^ |
           
          Vote: I like it -13 Vote: I do not like it

          This is why I singled out the problems on the higher end of the Div. 3/Div. 4 spectrum because I think there could be some technical solution which allows for an adjustment of these problems to reflect their difficulty better.

          There are Div. 3 problems rated 2500 or even higher, but I doubt most low GM users would seriously struggle with them if they occurred in a Div. 1/Div. 2 contests.

          Personally I believe both your and my point are reasonable and should be dealt as such, and my reply wasn't to you actually.

    • »
      »
      »
      12 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Based on clist and standings, https://mirror.codeforces.com/contest/668/problem/F is probably not 2300.

    • »
      »
      »
      9 months ago, hide # ^ |
      Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      3C--rated about 1000 points too high.

»
12 months ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

1726F - Late For Work (submissions are not allowed)

Submissions are in fact allowed but you will get wrong answer Submissions to this problem are not allowed -- see statement.

»
12 months ago, hide # |
 
Vote: I like it +33 Vote: I do not like it

936E - Iqea.

The problem can't be seen.

»
12 months ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

713C - Sonya and Problem Wihtout a Legend: Typo in the title (Wihtout -> Without)

»
12 months ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

What about weak test cases? For 464E - The Classic Problem, I have a test case on which 284778122 takes > 1 minute locally. I think that for this problem, it's particularly relevant because this problem is often recommended to students for training purposes.

  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it +16 Vote: I do not like it

    Yes, but that won't be my priority. Please provide a test generator that is either deterministic or uses testlib.h, the script line to run it, the target submission and expected verdict.

    Also, let's not target specific hash functions, etc.

    • »
      »
      »
      12 months ago, hide # ^ |
       
      Vote: I like it +11 Vote: I do not like it

      Thank you!

      Test generator:

      #include <bits/stdc++.h>
      
      using namespace std;
      
      int main(){
      	cout << "100000 99999\n";
      	for(int i = 1; i < 50000; i++){
      		cout << i << " " << i+1 << " " << i-1 << "\n";
      	}
      	for(int i = 50001; i < 100000; i++){
      		cout << "50000 " << i << " 0\n";
      	}
      	cout << "50000 100000 1\n";
      	cout << "1 100000\n";
      
      }
      

      Submission: 284778122

      Expected Verdict: Time limit exceeded

      It doesn't target specific hash functions or anything, just wrong time complexity.

»
12 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

1340E - Nastya and Bees No correct solution.

»
12 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

1000F - One Occurrence — Severely inappropriate time or memory limits

Using the Mo algorithm get time limit exceeded, and the Mo-based solution in the editorial also times out.

Sorry for my poor english

  • »
    »
    12 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it +13 Vote: I do not like it

    Sorry, but I don't think it's the issue with the problem. The model solution, which is $$$O(n \log n)$$$, passes comfortably. Mo-based solutions are very difficult to squeeze into the limits, but that should be fine since they are asymptotically worse.

    Maybe it's the issue with the editorial, then we should remove the Mo solution from it.

    upd: Okay, I tried other solutions from the editorial and some of them also get TLE. So there's actually some issue with the limits, I will try to fix it in a day or two.

»
12 months ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

186E - Clever Fat Rat It seems that the judge has some test cases is broken, and it seems like we can't get an AC without writing a mysterious if statement to handle a specific case.

  • »
    »
    8 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It seems the model solution was the same as yours (a 4-dimensional DP), and that turned out to be incorrect. Therefore, the if is needed to print the correct answer to a hack. See discussion here: https://mirror.codeforces.com/blog/entry/4468?#comment-90817

    Can you please confirm that there's no good solution? We'll then mark this problem as invalid.

»
12 months ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

401E - Olympic Games There is no problem statement. I solved it by guesseing the problem statement from https://blog.csdn.net/u013920003/article/details/21084005.

»
12 months ago, hide # |
 
Vote: I like it +37 Vote: I do not like it

The presence of some "marathon-style problems" that are impossible to solve, and the lack of a setting to hide them, personally reduces the usability for me. However, reporting such problems is not the point of this article, is it?

»
12 months ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

206D1 - The Beaver's Problem - 3 The download link is broken. (D2 to D10 is the same)

»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

101628K - Know Your Statement Denial of judgement

  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it +24 Vote: I do not like it

    That's a gym problem, not for the official problemset. You should contact the gym authors.

»
12 months ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

Not a CF problem, but in this article I wrote, specifically the line:

  • Given a sequence $$$A$$$ of length $$$N$$$ and Q queries $$$1 \le i \le j \le N$$$, compute the length of Longest Increasing Subsequence of $$$A[i], A[i + 1], \ldots, A[j]$$$.

If I replace this to the following, by changing "Q queries" to "$$$Q$$$ queries":

  • Given a sequence $$$A$$$ of length $$$N$$$ and $$$Q$$$ queries $$$1 \le i \le j \le N$$$, compute the length of Longest Increasing Subsequence of $$$A[i], A[i + 1], \ldots, A[j]$$$.

Then the whole math formatting gets broken. Someone recently messaged me about this issue, which had not occurred when I originally wrote the post.

»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

1740D - Knowledge Cards I posted a blog about it before but it got downvoted and no one cared. Explanation animation is broken

»
12 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

An INSANE nitpick: I think, technically, https://mirror.codeforces.com/contest/2085/problem/A is wrong. "A string a is lexicographically smaller than a string b of the same length, if and only if the following holds: in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b." "r is universal if and only if r is lexicographically smaller than the reversal of r." I think, mathematically, this means that a palindrome is universal, since it is vacuously true, that any palindrome is lexicographically smaller than itself, by the above definition.

  • »
    »
    12 months ago, hide # ^ |
    Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    This is not vacuous. The statement is simply undefined for two equal strings. It reads "first position", not "exist a position v which satisfies the later condition". Any sensible logical system would RE immediately. We would not be able to tell if the string is universal from the above definitions (alone) and is undefined.

    But yes I agree that the definition of lex smaller should be changed.

    • »
      »
      »
      12 months ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      I agree that the definition is rather invalid than vacuous, however one can argue that if $$$a = b$$$, then $$$a$$$ can't be less than $$$b$$$ for any possible definitions of less.

      Anyway, I've added $$$a \ne b$$$ for all future uses of this definition. Probably won't update already existing statements.

»
12 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

I suggest removing the limits of the problems ratings, for example some problems can be rated 200 and some can be 600 or 800 and some, yes this happened, is rated 0, all of these are being rounded up to 800 which make the 800 reflects many different difficulties which can let it be hard for the absolute beginners, I will not speak too much about the 3500+ problems that some of them are rated 4000+ and one of them is 4700, but I think this will only be important for the top rated users, but it is the same case :)

In many div3 or div4, we see the first 3 problems rated 800 or so, but third one is significantly harder than the first one.

»
12 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Broken English: 1651C - Fault-tolerant Network

The line just above the input section is wrong.

  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Fixed, thanks for the report. The statement should be updated in about 5-10 minutes.

»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Statement relies on the statements of another problem (e.g., the harder version's statement is not complete).

I don't remember the detail, but almost all problems of Helvetic Coding Contest 2016 online mirror (teams, unrated) relies on the statements of another problem.

»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

2094G - Chimpanzini Bananini Incorrect statement, or broken English.

The phrase

The first line of the input contains an integer q

should be

The first line of each test case contains an integer q

»
10 months ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

2045F - Grid Game 3-angle in the input section, $$$1\leq A_1\leq 10^9$$$ should be $$$1\leq A_i\leq 10^9$$$.

»
9 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

1335D - Анти-судоку The link from the statement explaining sudoku is broken (it probably expired after all of these years), I think replacing it with the Wikipedia link should be good enough.

»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

2041A - The Bento Box Adventure

1.simple solution(can be seen right away)

should be a 800 problem(its a 1300 problem)

»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

1547F - Array Stabilization (GCD version) The hyperlink that's supposed to explain GCD redirects to an unrelated news page.

»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Broken English: 1682D - Circular Spanning Tree

Error is in 2nd line of the statement:

"report that there such tree does not exist"

»
8 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

1078E - Negative Time Summation -- bug in the checker. Details here. I may have fixed it (sorry I don't know how polygon works), but I would like to know for sure (cc maspy)

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem — 802K statement relies on easier version

»
8 months ago, hide # |
Rev. 2  
Vote: I like it -10 Vote: I do not like it

upd: I misread the problem.

»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

190E - Контрнаступление solutions which passed during the contest get a TLE now. Maybe some issue with time limits.

»
7 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Fairly minor but 43B - Letter, 142A - Help Farmer, 101C - Vectors, 27B - Tournament, 14E - Camels, 147B - Smile House, 158D - Ice Sculptures, 26C - Parquet, 102E - Vectors, 48B - Land Lot, 420E - Playing the ball, probably others: English version contains "и" instead of "and". To find more of these you can search "и" site:codeforces.com/problemset -locale=ruon any search engine.

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Shouldn't this Problem 706 D2- E. Garden of the Sun be much lower rated (currently 2300)

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

590C - Three States

wrong grammar in english version at the end of the first paragraph

it was decided that a road between the states should be built to guarantee so that one could any point of any country can be reached from any point of any other State.

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

239A - Two Bags of Potatoes typo in first paragraph "gerater" -> "greater"

»
7 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

29D - Ant on the Tree, in the second paragraph

He sees that there are n vertexes in the tree

vertexes should be "vertices". (vertexes also might be correct but i never heard or see someone saying vertexes)

»
7 months ago, hide # |
 
Vote: I like it -36 Vote: I do not like it

https://mirror.codeforces.com/blog/entry/110092

In the tutorial for C the last word was written as enouth instead of enough

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

All the problems of contest MemSQL Start[c]UP 3.0 — Round 2 (onsite finalists) are broken and don't accept submissions without making mashup .

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

878B

"..each consisting of $$$k$$$ participants form the same city.." should be "from the same city".

"..determine how many participants have left in the line.." should be "are left".

"The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n (1 \leq  a_i  \leq 10^5)$$$, where $$$a_i$$$ is the number of city, person from which must take seat i in the bus." can be phrased a lot better as " where the $$$i$$$-th seat in the bus is taken by a person from city $$$a_i$$$".

»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

1423A - Wakanda Forever, Input section,

$$$N−1$$$ integers $$$A_{i,1}, A_{i,2},\ldots, A_{i,i-1}, A_{i,i+1},\ldots, A_{i,N-1}$$$

$$$A_{i,N-1}$$$ should be $$$A_{i,N}$$$.

Also, it seems there’s an obvious mistake in the judge. 345419243

»
6 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

https://mirror.codeforces.com/contest/2018/problem/F1

It contains a reference to problem D of the same contest. Likewise, F2 and F3 do as well.

  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This is just a reference, and the knowledge of D1B is not required to understand the problem. So it's fine.

»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

1028H - Make Square Denial of judgement

Submission: 348247841

  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    There seems to be no problem here, maybe it was a temporary glitch.

»
4 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

Blackslex and Another RGB Walking

All my submissions for this problem ended with the verdict "Loading presents for flight 1..." ("Delivery failed FL" after some time) .

Even the almost empty one test submission

»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

240 E Road Repairs the sloution sould be directed MST but simple bfs works and you could easily make a test case that would give wrong answer on most of the accepted solutions out there(the output graph is not connected)

»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

2174F - Mosaic Tree

Some hacks for this problem still result in Unexpected verdict (1160229 to 1160235)

  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you please describe what this test is, and maybe provide the generator?

    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Maximize the number of FFT uses in FFT+qpow using DP

      In the Unexpected verdict state, I cannot see the generator I used; perhaps only administrators can see it...

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

1526C1 - Potions (Easy Version)

The statement has error. "will decrease will health" should be "will decrease your health"

»
3 months ago, hide # |
Rev. 2  
Vote: I like it +3 Vote: I do not like it

830C - Bamboo Partition weak test cases. Solution provided in editorial 28572941 gives different answer compared to my solution 356538530 on the following test:

3 3 
1 1 3

My solution gives $$$2$$$, and other gives $$$1$$$.

If you need generator:

#include <iostream>

using namespace std;

int main() {
    cout << "3 3" << endl;
    cout << "1 1 3" << endl;
}

Submission: 28572941

Expected verdict: Wrong answer

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem: 1423A This problem "wakanda forever" has broken testing. It's a 3500 rated problem and this code got accepted:

#include <iostream>
using namespace std;

int main() 
{
    int n;
    cin>>n;
    for (int i=0;i<n;i++){
      cout<<i+1<<endl;
    }
    return 0;
}
»
3 months ago, hide # |
Rev. 3  
Vote: I like it 0 Vote: I do not like it

In some problems, it is not stated whether the outputs YES and NO are case-insensitive (they are).

»
3 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

1158A - The Party and Sweets

"g_j is equal exactly to the maximum among values b_1j, b_2j, ... " — seems should be a_ij instead of b_ij

Also in Russian statement used capital "И" right before this part

  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It seems isaf27 fixed this some time ago, now the statement is updated on CF as well.

»
3 months ago, hide # |
Rev. 3  
Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1249/problem/D1

This problem is rated 1800. I don't consider myself good or have solved a considerable amount of problems, but atleast good enough to identify that this problem rating doesnt deserve to be more than 1200.

The problem asks us for each point on a number line, if it has more than k segments covering it, we need to remove from them until their count is <= k, only catch is that we want the minimal removals, to achieve that if we sweep from left to right the obvious optimal choice is to always remove the segment which is covering the most from the right, aka the segment with the maximum ending, pretty straightforward.

  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    this is an old problem, the average problem solving skill of a specialist back then was different than it is today.

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

[problem:802A] in Russian statement: "уже есть книга нужная книга"

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In this contest, the inputs are setTestCase-d while the outputs aren't, making HTML broke when you hover your mouse over the inputs.

  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Works for me. Can you please specify what exactly breaks? Maybe a screenshot and browser version?

»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

1919H - Tree Diameter i think it was mentioned before that this was wrongly rated 2000 , with 0 solves in the actual round

»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

D1. Asesino (Easy Version)

D2. Asesino (Hard Version)

there is a misspelling in the statement under the table:

The response of the cell ... when i has role a and j has "row" b. ("row" -> "role")

»
2 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

2090A - Treasure Hunt

I found the answers in this problem's test #2 are contrary to my correct output. Therefore, it always returns "Wrong answer on test 2" although I checked it right.

It supposes to "output "NO" if Little B digs it up first; otherwise, output "YES"", while the judge's answers opposite.

»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The editorial's implementation of 1815B - Sum Graph gives WA on test 1, hope you fix it.

»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

1076E - Вася и дерево typo in the note, exapmle-> example

»
5 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

1110C - Meaningless Operations

reason: broken formatting, bitwise '&' is replaced with '>&>'