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.
skill issue mate, D1 was very easy
who said D1 was hard, still so many people solving D1 is unusual
Yep!! Too much cheating!
ABC are easy but D1 and D2 are harder for sure
I think difficulty is relative...For example, some candidates found D1 easier than C during the contest.
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
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...
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.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?
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!
(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 butacb
orac.....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 whena
andX
are not equal, and the string be of the formaX.....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. :(
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$$$.
Auto comment: topic has been updated by a_for_abdullah (previous revision, new revision, compare).
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
for D1 Mike Mirzayanov
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.
yeah! Check D1 submission of newbies and pupil in last contest you will find :
Like they cant be more identical.