a_for_abdullah's blog

Massive cheating in yesterday's Codeforces Round 968 (Div. 2)
By a_for_abdullah, history, 5 hours ago, In English

Yesterday even after solving three problems i got a delta negative which doesn,t usually happens when you solve three questions at the rating where i am so i searched for telegram channels and guess what i found, I found a telegram channel with over 3300 members, I don,t want to write the name here for obvious reasons, here are some of the solutions that were floating there

Solutions of C:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
void maximizeGoodPairs(string &s) {
    int n = s.size();
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    string result(n, ' ');
    int idx = 0;
    while (true) {
        bool filled = false;
        for (auto &[ch, count] : freq) {
            if (count > 0) {
                result[idx] = ch;
                idx++;
                count--;
                filled = true;
                if (idx >= n) {
                    idx = 1;
                }
            }
        }
        if (!filled) {
            break;
        }
    }
    cout << result << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        maximizeGoodPairs(s);
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> freq(26, 0);
    // Count frequency of each character
    for (char c : s) {
        freq[c - 'a']++;
    }
    string even, odd;
    // Fill two separate strings: one for even index positions and one for odd index positions
    for (int i = 0; i < 26; ++i) {
        if (freq[i] > 0) {
            string chars(freq[i], 'a' + i);
            if (even.size() <= odd.size()) {
                even += chars;
            } else {
                odd += chars;
            }
        }
    }
    // Now alternate between even and odd strings
    string result;
    int i = 0, j = 0;
    while (i < even.size() || j < odd.size()) {
        if (i < even.size()) result += even[i++];
        if (j < odd.size()) result += odd[j++];
    }
    cout << result << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Solution of D1:

#include <iostream>
#include <unordered_set>
#include <sstream>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tes;
    cin >> tes;
    ostringstream sb;
    while (tes--) {
        int que;
        long long m;
        cin >> que >> m;
        int max_val = 0;
        while (que--) {
            int n;
            cin >> n;
            unordered_set<int> set;
            int a[n];
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
                set.insert(a[i]);
            }
            int first = 0;
            while (true) {
                if (set.find(first) == set.end()) {
                    set.insert(first);
                    break;
                }
                ++first;
            }
            while (true) {
                if (set.find(first) == set.end()) {
                    max_val = max(max_val, first);
                    break;
                }
                ++first;
            }
        }
        if (m >= max_val) {
            long long ans = (long long)max_val * (max_val + 1);
            long long big = (m * (m + 1)) / 2 - ans / 2;
            sb << (ans + big) << '\n';
        } else {
            long long ans = (long long)max_val * (m + 1);
            sb << ans << '\n';
        }
    }
    cout << sb.str();
    return 0;
}

Solution of D2:

#include<bits/stdc++.h> using namespace std; #dPfinn int long long int sum(int x) { return x*(x+1) ; } int interval(int I,int r) { return sum(r)-sum(I-1); } vector<int> son[1000001]; int dp[1000001]; void solve() int n,m,s=0,mint=0; map<int,int> cnt; cin B; n B; m; for(int i=1,u,v;i<=n;++0 { int I; cin B; I; set<int> t; for(int i=1,x;i<=1;++0 { cin B; x; t.insert(x); } bool flag=true; for(int i=0;;++i) { if(!t.count(i)) { if(flag) { flag=false; u=i; mint=max(mint,u); } else { v=i; break;}
}
} s=max(s,v);
son[v].push_back(u);
cnt[u]++;

} for(int i=0; i<=s; ++0 dp[i]=-1; for(int i=s; i>=0; --i) if(dp[i]==-1) dp[i]=i; for(int j:son[i]) dp[j]=max(dp[j],dp[i]);
  } int pp=0; for(int i=0; i<=s; ++0 if(i<=mint) dp[i]=max(dp[i],mint); for(auto i:cnt) if(i.second>=2) pp=max(pp,dp[i.first]);
  } for(int i=0; i<=s; ++0 dp[i]=max(dp[i],pp); for(int i=0; i<=s; ++0 son[i].clear(); if(m<=s) int sum=0; for(int i=0; i<=m; ++0 sum+=dp[i]; cout B+ sum B+ endl; return;
  } int sum=0; for(int i=0; i<=s; ++0 sum+=dp[i]; sum+=interval(s+1,m); cout B+ sum B+ endl;
} signed main() {
cin.tie(0);
 cout.tie(0);
 ios_base::sync_with_stdio(0);
 int t;cin>>t;
 while(t--)solve()

above D2 sol if rewritten using GPT

#include <bits/stdc++.h>
using namespace std;
#define int long long
int sum(int x) {
    return x * (x + 1) / 2;  // Corrected the sum formula
}
int interval(int I, int r) {
    return sum(r) - sum(I - 1);
}
vector<int> son[1000001];
int dp[1000001];
void solve() {
    int n, m, s = 0, mint = 0;
    map<int, int> cnt;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int l;
        cin >> l;
        set<int> t;
        for (int j = 1; j <= l; ++j) {
            int x;
            cin >> x;
            t.insert(x);
        }
        bool flag = true;
        int u, v;
        for (int j = 0;; ++j) {
            if (!t.count(j)) {
                if (flag) {
                    flag = false;
                    u = j;
                    mint = max(mint, u);
                } else {
                    v = j;
                    break;
                }
            }
        }
        s = max(s, v);
        son[v].push_back(u);
        cnt[u]++;
    }
    for (int i = 0; i <= s; ++i) {
        dp[i] = -1;
    }
    for (int i = s; i >= 0; --i) {
        if (dp[i] == -1) dp[i] = i;
        for (int j : son[i]) {
            dp[j] = max(dp[j], dp[i]);
        }
    }
    int pp = 0;
    for (int i = 0; i <= s; ++i) {
        if (i <= mint) dp[i] = max(dp[i], mint);
    }
    for (auto i : cnt) {
        if (i.second >= 2) pp = max(pp, dp[i.first]);
    }
    for (int i = 0; i <= s; ++i) {
        dp[i] = max(dp[i], pp);
    }
    for (int i = 0; i <= s; ++i) {
        son[i].clear();
    }
    if (m <= s) {
        int sum = 0;
        for (int i = 0; i <= m; ++i) {
            sum += dp[i];
        }
        cout << sum << endl;
        return;
    }
    int sum = 0;
    for (int i = 0; i <= s; ++i) {
        sum += dp[i];
    }
    sum += interval(s + 1, m);
    cout << sum << endl;
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

please zltzlt and Mike Mirzayanov do the testing again and ban all the accounts with these and similar solutions. Thank you and please upvote.

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

»
5 hours ago, # |
  Vote: I like it -14 Vote: I do not like it

skill issue mate, D1 was very easy

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

    who said D1 was hard, still so many people solving D1 is unusual

    → Reply
  • »
    »
    39 minutes ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Yep!! Too much cheating!

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

ABC are easy but D1 and D2 are harder for sure

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

    I think difficulty is relative...For example, some candidates found D1 easier than C during the contest.

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

      True, C was more of an intuition based question while D1 was observation. While both were nice questions, difficulty might vary from person to person

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

        In C ,there were two condition on which we can count a pair (i,j) in the answer.

        • s[i]=s[j](say 1)
        • s[k]!=s[k+1] and (s[i]!=s[k] or s[k]!=s[j])(say 2)

        now try to combine both, as any one condition will be enough...

            (s[i]==s[j]) or (s[k]!=s[k+1] and (s[i]!=s[k] or s[k]!=s[j]))
        cond.1                      cond,2

        try to find 1 OR 2.Breakdown 2 into smaller conditions and apply De Morgan's Law. I hope you will find the path to the answer. Hope this provides a new POV.

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

          I didn't quite get it. Don't you think you just reiterated what the question had given? As in, I don't think using de Morgan's law and breaking down into smaller conditions helps. Could you give a detailed example for this?

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

            I agree, I thought I had a proof during the contest. Only to later realise that my solution is only one of the many correct solutions. And my "proof" is incorrect!

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

            (s[i] == s[j]) or (s[k] != s[k + 1] and (s[i] != s[k] or s[k] != s[j]));

            (s[i] == s[j] or s[k] != s[k + 1]) and (s[i] == s[j] or s[i] != s[k] or s[k + 1] != s[j]);

            this means for a substring a.....b there must be a X in between such that a!=X and minimum length will be 3 as ab is not valid but acb or ac.....b will add 1 to the answer each.

            so the task becomes to maximise the number of b's for every a..X..b, this will be maximised when a and X are not equal, and the string be of the form aX.....b and by doing this all rest of the upcoming b's will be valid.

            to tackle this problem we can equalise the most frequent character to the second most frequent character and then thereafter just alternating the characters while decreasing there count.

            i think i am not able to convey it properly. :(

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              26 minutes ago, # ^ |
              ← Rev. 4   Vote: I like it 0 Vote: I do not like it

              Problem C was to find best string where at best $$$1<=i<n $$$ and $$$a[i]!=a[i+1]$$$ which means you can use 2 letters with maximum frequency every step and find answer no matter what.

              And Problem D1 was just find best second $$$MEX$$$.

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

Auto comment: topic has been updated by a_for_abdullah (previous revision, new revision, compare).

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

This is what I have got from telegram group!

// #include <bits/stdc++.h> // using namespace std; // #define int long long
// int sum(int x) { // return x*(x+1)/2; // } // int f(int l,int r) { // return sum(r)-sum(l-1); // } // void solve() { // int n,m,s=0; // cin >> n >> m; // for(int i=1;i<=n;++i) { // int l; // cin >> l; // set t; // for(int i=1,x;i<=l;++i) { // cin >> x; // t.insert(x); // } // bool flag=true; // for(int i=0;;++i) { // if(!t.count(i)) { // if(flag) flag=false; // else { // s=max(s,i); // break; // } // } // } // } // if(m<=s) cout << s*(m+1) << endl; // else cout << s*(s+1)+f(s+1,m) << endl; // } // signed main() { // int t; // cin >> t; // while(t--){ // solve(); // }

// }

FOR D1 @Mirzayanov

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

I think the average IQ has increased by 70-80% in India. That is why greys and pupils from there solve ABCD under 30 mins. I believe if they try, they might invent a time machine.

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

yeah! Check D1 submission of newbies and pupil in last contest you will find :

int sum(){
}
int interval/val/calulateinterval(){
}
int main(){
  for(){
    for(){
       set<t>;

    }
  }
}

Like they cant be more identical.

→ Reply