I'm not a fan of this problem, but it's fine. I don't see a reason to hate its existence.

You have created 100s of problems, and the expected value of the number of problems people will absolutely hate is more than 1. Let's just assume it's one of them.

We can agree to disagree here and just move on.

I think this is a good implementation problem, as I said before in the comment section of contest announcement "no DS, no obscure algo, no gpt".

I'd like to share my own version of the answer which uses the same logic.
I'd like reader's feedback on my style of explaining.

#include<bits/stdc++.h>
using namespace std;

void solve();

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

enum{
    NEED_I = 0, // count position of ?V
    NEED_V = 1, // count position of I?
    BLOCKS = 2  // count position of ??
};

void solve(){
    int n,q;
    string s;
    cin>>n>>q>>s;
    vector<int> cnt(3); // count of patterns ?V, I?, ??
    int sum = 0; // preliminary sum
    int blank = 0; // count number of ? to be filled
    {// process input, finding ?V, I?, ??, I?V patterns
        int group_size = 0; // length of continuous ???
        for(int i=0;i<n;++i){
            if(s[i]=='?'){ // ?
                blank++; // increase blank
                if(i&&s[i-1]=='I'){
                    cnt[NEED_V]++; // I? pattern found
                }else{
                    group_size++; // increase group length
                }
            }else{ // IVX
                if(s[i]=='V'||s[i]=='X'){ // VX
                    sum += 5 * (1 + (s[i]=='X')); // increase sum
                    if(i&&s[i-1]=='?'){// ?V pattern found
                        if(i>1&&s[i-2]=='I'){// I?V pattern found
                            sum -= 2;
                            cnt[NEED_V]--; // previous I? pattern no longer valid
                        }else{
                            cnt[NEED_I]++; // normal ?V pattern
                            group_size--; // borrow 1 '?' from the group
                        }
                    }else if(i&&s[i-1]=='I'){ // IV pattern found
                        sum -= 2;
                    }
                }else{ // I
                    sum += 1;
                }
                // count the number of blocks of ?? (2-sized)
                cnt[BLOCKS]+=group_size/2;
                group_size=0;
            }
        }
        cnt[BLOCKS]+=group_size/2;// leftover
    }
    while(q--){
        int cnt_X,cnt_V,cnt_I;
        cin>>cnt_X>>cnt_V>>cnt_I;
        cnt_I = min(cnt_I, blank);// use most I
        cnt_V = min(cnt_V, max(0,blank-cnt_I));// use most V
        cnt_X = min(cnt_X, max(0,blank-cnt_I-cnt_V));// whatever left
        int ans = sum + cnt_I + 5*cnt_V + 10*cnt_X; // answer before utilizing I? or ?V pattern
        int blankleft = blank; // number of position we can fill
        cnt_V += cnt_X; // V and X is the same pattern
        cnt_X = 0; // no longer needed
        {// put as many as possible I into ?V pattern
            int mn = min(cnt[NEED_I], cnt_I);
            ans -= mn*2;
            cnt_I -= mn; // update
        }
        {// put as many as possible IV into ?? pattern/block
            int mn = min(cnt[BLOCKS], min(cnt_I, cnt_V));
            ans -= mn*2;
            // cnt_I -= mn; // update not needed, but left as comment for reader
            cnt_V -= mn; // update
        }
        {// put as many as possible V into I? pattern
            int mn = min(cnt[NEED_V], cnt_V);
            ans -= mn*2;
            // cnt_V -= mn; // update not needed, but left as comment for reader
        }
        // whenever an IV pattern is found we use -2 instead of -1 because it changes the 1 to -1
        cout<<ans<<"\n"; // output
    }
    cout<<"\n"; // aesthetic
}

Thanks for the explanation! I think an I/V problem is a less casework than I/V/X, so probably more manageable.

Personally although I didn't solve it, I think this was an okay problem. Maybe if a future contest was longer or had a lot lower problems an I/V/X problem would be okay?

Not only is repalcing all X with Vs much needed, the fact that you have to prepocess the string to get what you want is also pretty anonying. If your only concern is the second "hard" part, then you can simply maximize the number of "01" substrings (neglecting the first very easy observation). Another place is allowing the available counts > number of '?', that alone added 10 lines for no good reasrons.

I have heard of a much more direct solution using convex convolution (presumably merged small to large), Unfortunate, with some thinking the code would probably be equally long, not to the only "hard" part but to the above reductions.

Another problem is that it is placed before problem E.

I just VCed this contest, and I honestly don't mind this problem? I like that it rewards slowing down a little and thinking through your solution, and there aren't any tricky/hidden corner cases. I also think the implementation wasn't actually that terrible (mine was 80 lines or so, and I'd be pretty sad if we got to the point where 80 lines of implementation was too much). It's reasonable that some people have a stylistic preference problems where more of the emphasis is on untangling the mathematical structure and the code is shorter, but I don't think this is an objectively bad problem (I would not reject it if I was a coordinator).

(Unfortunately, I lost 40 minutes by writing S[i] == N-1 instead of i == N-1, but that's my skill issue...)

On reducing implementation complexity: removing X seems fine, but I don't think it would change the implementation difficulty substantially (and for flavor text purposes, it is sort of fun to have three of the Roman numerals instead of just I and V--I think the problem would feel a little bit more contrived if three letters were used).

Another small thing you could have done to cut down a bit of implementation is to guarantee that $$$c_X + c_V + c_I$$$ is equal to the number of question marks in the string. It's pretty obvious that we should use as many of the smaller numbers as possible, so dropping this would cut a couple lines of mindless implementation. But, like removing X, this wouldn't substantially change the difficulty of implementing the solution.

I did think D ended up not being great for the balance of the round. I thought E was about the same difficulty conceptually but easier to implement, and I think it would have worked well to put E before D. I also think F was easier than usual (clist seems to agree; it thinks F is rated 2400, which is somewhat easier than the last problem on a div 2 tends to be). I enjoyed all the problems individually, but the fact that E/F were relatively easy maybe makes D feel a little worse, since it means strong competitors are likely to spend more time on D than on the harder problems that are more interesting to them. (It would have felt less bad to go through D if there was a deeper/more challenging problem F to think about afterwards.)

I'm also sad that there appears to be a larger than usual number of cheaters near the top of the scoreboard--hopefully this will be resolved through the post-contest checks, but it's still a little unfortunate to see cheating temporarily rewarded (though it seems likely that this will become a more common occurrence over the coming months...)

Thanks for the round!

Programming in the programming contest?

It is completely fair and ok . One side setters/contest authors on cf and otherside , Look at meta hacker cup , what they did accepted wrong solutions for B and did not even appologise with a blog till now .

There isn’t much to say. I don’t think this problem was actually that bad. The real issue was that I trapped myself in blind casework and special-case handling instead of stepping back and thinking globally. That made me wrongly classify it as a type-1 problem — “a problem where you have to write a lot of boring code or examine a lot of corner cases.” This problem gave me a rather painful but valuable lesson about implementation.

Here is the terrifying code I wrote during the contest; perhaps this will help you understand why so many people (including myself) considered it a type-1 problem.

#include <cassert>
#include <iostream>
using namespace std;

void solve()
{
    // 一个字符串的所有'?'可以用什么描述？
    // 如果下个字符是'XV'，则可以描述为XV
    // 如果前一个字符是'I'，可以描述为IXV
    //
    // 如果下一个字符是‘V'，可以描述为IV
    // 如果下一个字符是'?'，可以描述为'?'
    // 是否要将所有连续'?'字符两两破坏？这样贪心看起来很对
    // 因为我一定优先让I变成-1
    // 随后再安排V?不，先让I尽可能多点
    // 即破坏双'?'，产生一个XVminas
    // 现在问题是
    // I??V
    // 怎么描述？
    // 一个double or 一个IXV+IV?
    // 很明显后面更灵活
    //
    // 或许可以更简单，前i_1个I是-1的贡献，这里绝对不会影响后续填VX。然后I再填到所有后面有'?'的位置，
    // 此时会增加vx_i，增加的上限取决于'??'，随后填入VX，这样应该不会错
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    s = '#' + s + "###";

    int  i_1     = 0;
    int  doubleq = 0;
    int  normq   = 0;
    int  xv_i    = 0;
    int  both    = 0;
    auto is_xv   = [](char c) { return c == 'X' || c == 'V'; };
    for (int i = 1; i <= n;) {
        if (s[i] == '?') {
            if (s[i - 1] == 'I' && is_xv(s[i + 1])) {
                normq++;
                // 算入normq
                both++;
                i++;
                continue;
            }
            if (is_xv(s[i + 1])) {
                i_1++;
                i++;
                continue;
            } else if (s[i - 1] == 'I') {
                xv_i++;
                i++;
                continue;
            } else if (s[i + 1] == '?') {
                if (!is_xv(s[i + 2])) {
                    {
                        doubleq++;
                        i += 2;
                        continue;
                    }
                } else {
                    normq++;
                    i++;
                    continue;
                }
            } else if (s[i + 1] == 'I' || s[i + 1] == '#') {
                normq++;
                i++;
                continue;
            } else {
            }
        } else {
            i++;
            continue;
        }
    }
    int baseval = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '?') {
            continue;
        } else {
            if (s[i] == 'I') {
                if (is_xv(s[i + 1])) {
                    baseval--;
                }
                // else if (s[i + 1] == '?') {
                //     continue;
                // }
                else {
                    baseval++;
                }
            } else if (s[i] == 'X') {
                baseval += 10;
            } else if (s[i] == 'V') {
                baseval += 5;
            }
        }
    }
    baseval -= both * 2;
    // 这里both相当于把I由1变为-1
    while (q--) {
        int c1, c2, c3;
        cin >> c3 >> c2 >> c1;
        int n_i_1     = i_1;
        int n_doubleq = doubleq;
        int n_normq   = normq;
        int n_xv_i    = xv_i;
        int ans       = baseval;
        // try i_1
        int c1_i_1 = min(c1, n_i_1);
        n_i_1 -= c1_i_1;
        c1 -= c1_i_1;
        ans -= c1_i_1;

        // try doubleq
        int c1_doubleq = min(n_doubleq, c1);
        n_doubleq -= c1_doubleq;
        c1 -= c1_doubleq;
        ans += c1_doubleq;
        n_xv_i += c1_doubleq;

        // trynorm
        int c1_normq = min(c1, n_normq);
        n_normq -= c1_normq;
        c1 -= c1_normq;

        ans += c1_normq;

        // try xv_i
        int c1_xv_i = min(c1, n_xv_i);
        n_xv_i -= c1_xv_i;
        c1 -= c1_xv_i;
        ans += c1_xv_i;
        // IIIV?
        n_normq += n_doubleq * 2 + n_i_1 + n_xv_i;
        ans -= n_xv_i * 2;
        int c2_normq = min(n_normq, c2);
        n_normq -= c2_normq;
        c2 -= c2_normq;
        ans += c2_normq * 5;
        ans += n_normq * 10;
        cout << ans << '\n';
    }
}

signed main(signed argc, char** argv)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}