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

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

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!

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

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +33 Проголосовать: не нравится

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

»
12 месяцев назад, скрыть # |
Rev. 3  
Проголосовать: нравится +27 Проголосовать: не нравится

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

Does incorrect problem ratings count as an issue?

  • »
    »
    12 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится -7 Проголосовать: не нравится

      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 месяцев назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится -13 Проголосовать: не нравится

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

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

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

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

    • »
      »
      »
      9 месяцев назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      3C--rated about 1000 points too high.

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

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

936E - Iqea.

The problem can't be seen.

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +28 Проголосовать: не нравится

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

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

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

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

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

1340E - Nastya and Bees No correct solution.

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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 месяцев назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +13 Проголосовать: не нравится

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

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.

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +28 Проголосовать: не нравится

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

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

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

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

101628K - Know Your Statement Denial of judgement

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

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

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

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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 месяцев назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

Broken English: 1651C - Fault-tolerant Network

The line just above the input section is wrong.

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

2041A - The Bento Box Adventure

1.simple solution(can be seen right away)

should be a 800 problem(its a 1300 problem)

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Broken English: 1682D - Circular Spanning Tree

Error is in 2nd line of the statement:

"report that there such tree does not exist"

»
8 месяцев назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

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

Problem — 802K statement relies on easier version

»
8 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится -10 Проголосовать: не нравится

upd: I misread the problem.

»
8 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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

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

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
7 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

»
7 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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.

»
5 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

1028H - Make Square Denial of judgement

Submission: 348247841

»
4 месяца назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

2174F - Mosaic Tree

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

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

1526C1 - Potions (Easy Version)

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

»
3 месяца назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

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

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 месяца назад, скрыть # |
Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, скрыть # |
Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

Задача 80B — Депрессия — условие на русском языке недоступно по ссылке

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

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

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

»
5 дней назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

1110C - Meaningless Operations

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