MEDAA's blog

Div2 problems are not Div2 problems?
By MEDAA, history, 7 hours ago, In English

In today's round Codeforces Round 996 (Div. 2), the gap between problem difficulties was hilariously wide, according to clist. The last two problems are rated approximately 3000 and 3500, which clearly means that they are not suitable for participants rated below 2100.

I think this makes the round literally consist of only four problems, where your performance depends mostly on speed. According to Carrot, the performance of the second-place participant was LGM, who solved four problems. There are also participants who solved four problems and achieved a CM-level performance, which is very weird.

I am not complaining only about today's contest, but it serves as a great example of the unbalanced difficulty seen in recent contests. This imbalance particularly affects CPers rated between 1600 — 2100, who do not have the opportunity for rated contests except for div 2 contests, making us have fewer opportunities to achieve a positive delta, as luck starts to play a significant role in determining our rating.

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

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

It's honestly not very obvious to me why so few people have solved problem E. I'm not saying this is a simple task, I haven't solved it either (I really don't like this kind of task), but judging by the analysis, this is a common task a little more complicated than d2E, definitely not deserving of the complexity of 3000

→ Reply
  • »
    »
    7 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Let us neglect the 3000, it is still complicated for a < 2100 participant

    Also, note that the only one who solved it in div2 was a grandmaster. XD

    → Reply
    • »
      »
      »
      7 hours ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      yep, I agree it is hard even for some 2100+ guys, but still solvable. Also I would like to have more 2300+ tasks in div2s, rather then 2700+. But challenging tasks create strong programmers)

      Wow, only GM solved this? This is really strange)

      → Reply
»
6 hours ago, # |
  Vote: I like it -27 Vote: I do not like it

GPT era

→ Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am still puzzled about the difficulty of D. I could't find out a complete correct sol during the contest with thinking the situation is too complicated. Maybe I am so bad at greedy. How could so much people solve this problem? Could anyone introduce some similar greedy problems?

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Tbf I think that the editorial solutions are usually hard to follow as they keep optimizing the solution so it is shorter and faster to consume for people up-solving. I thought in a much simpler way and was able to solve the question, take a look at my submission (I added some comments for clarity):

    #include<bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using vi = vec<int>;
using ii = pair<int, int>;
using vii = vec<ii>;
using i64 = long long;
using vi64 = vec<i64>;


void solve(){
    i64 n, k, l; cin >> n >> k >> l;
    // multiply all distances by 2 so we don't have to deal with .5 values
    k *= 2;
    l *= 2;

    vi64 a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] *= 2;
    }

    bool pushing = false; // pushing means there is a scarecrow behind pushing it
    int i = 0; // current scarecrow to process
    i64 total_time = 0; // all time elapsed since beginning
    i64 curr = 0; // current position of the crow
    i64 ans = 1e18; // best time found
    while(true){
        if(curr >= l) // we reached the desired position
            ans = min(ans, total_time);
        else if(pushing) // if we didn't but there is a scarecrow pushing
            ans = min(ans, total_time + (l - curr));
        if(i == n) // if we processed every scarecrow just quit
            break;
        // if the scarecrow being processed now is in front, it should move
        // in the direction of the crow to move it, otherwise it won't contribute
        if(a[i] >= curr){
            i64 optimal_pos = max(curr, a[i] - total_time);
            i64 delta_meet = optimal_pos - curr;
            if(pushing)  // if there is a scarecrow pushing it we meet at the midpoint
                delta_meet /= 2;
            total_time += delta_meet;
            curr += k;
            if(pushing)
                curr += delta_meet; // distance traveled while being pushed
        }
        // if the current scarecrow is behind the crow, it moves in the direction of
        // the crow to push it as much as possible, not going past the crow
        else{
            i64 optimal_pos = min(curr, a[i] + total_time);
            // maybe the current scarecrow won't be able to push it a single bit
            // in that case we don't change the position of the crow
            curr = max(curr, optimal_pos + k);
        }
        // after the very first scarecrow the crow will always be pushed
        // (either by the first one or any other following crow
        pushing = true;
        i++;
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases = 1;
    cin >> testCases;

    while(testCases--)
        solve();

    return 0;
}
    → Reply
    • »
      »
      »
      2 hours ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      It seems that it is a simple and good sol that is suitable for contest. The editorial need to talk about why their sol is completely right in all situations, so it always seems to be much harder. I have to say that clearly making sure your sol is always correct may be not easy, but that's greedy. I could't control my mind to think the proof of my sol during the contest. Without that, I even don't dare to come up with a full sol because I get confused and stop at some points. Maybe that's not a really suitable method for greedy problems during the contest.:(

      → Reply
      • »
        »
        »
        »
        2 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh boy, what if I tell you that half of questions A I am not even sure if my solution is right until I get AC. I think a better approach is to have faith:

        Think of some solution and try to hack it (that is, find a counter example). If you can't find a counter example to a solution, chances are that solution is right (remember, codeforces questions are meant to be solved. Unless you are doing a really hard question, the solution shouldn't be too difficult).

        → Reply
»
4 hours ago, # |
  Vote: I like it +32 Vote: I do not like it

"who do not have the opportunity for rated contests except for div 2 contests, making us have fewer opportunities to achieve a positive delta".

→ Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

It's another one of these: https://codeforces.me/blog/entry/129569

Whenever I bring up this topic, the usual claim is that these problems are too standard for higher divisions. But in my opinion, if a problem is too standard to appear in a higher division, it shouldn't appear in ANY division at all and should only be made as a non-contest problem. I don't really get why these problems are considered to be okay if they are in low enough division so that they aren't solvable for almost anyone in the division. To be honest, I feel that the standard for this standardness is in general too high, but that's for another discussion.

Even if we keep the current trend of having unsolvable-for-official-participants problems, they should at least not be counted when we construct a problemset. I think every problem that fits a division should at least have a nontrivial chance to be solvable by the official participants, and these participants shouldn't only be someone whose actual skill level is something like GM but has low rating just because of too few contest participation or something. I think at least 5 problems should be feasible for some good number of CMs, and even for some Experts, considering that Div. 2 was originally meant to be targeted to up to Experts. Otherwise, we will only be able to keep having these huge difficulty gaps between problems, causing huge performance difference between fast $$$X$$$ solves and slow $$$X$$$ solves for every $$$X$$$.

I also think we shouldn't be afraid of having too many AKs, if that 'too many' is something like 50. It's still only a very small proportion of the participants (even within CMs alone), and most of them would only have solved them in the very last 15 minutes. Almost no official participant "wasted" more than 15 minutes.

→ Reply
  • »
    »
    81 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe it's good to raise the upper bound of the rating distribution up to ~2399, as most div2Fs are unsolveable for <2100 contestant(at least for me) (:з」∠)

    → Reply
»
3 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

it's just one kind of div2—fewer problems but more difficulties, which is foreseen if u read the score distribution carefully on the announcement.

→ Reply
  • »
    »
    52 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    every contest is speedforces as umnik wrote somewhere. it just so happened that it was 4 questions speedforces instead of 5-6 for this one.

    → Reply