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

Автор a_for_abdullah, история, 5 часов назад, По-английски

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.

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

»
5 часов назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

skill issue mate, D1 was very easy

  • »
    »
    4 часа назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    37 минут назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Yep!! Too much cheating!

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

ABC are easy but D1 and D2 are harder for sure

  • »
    »
    4 часа назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

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

    • »
      »
      »
      4 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        3 часа назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 часа назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            2 часа назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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!

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

            (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. :(

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

              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$$$.

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 часа назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 часа назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

»
46 минут назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.