Hello sir, In the Problem C as we can only change one character so I am changing every character of the string to all the character from A to B but it is giving wrong on test case 9. This is my code. #include #define ll long long int using namespace std; // author: Krishna Sharma int main() { ll t; cin >> t; while (t--) { string s; cin >> s; vector v(5, 1); vector vr(s.size() + 1, 1); for (int i = 1; i < 5; i++) { v[i] = v[i - 1] * 10; } multiset se; for (int i = 0; i < s.size(); i++) se.insert(s[i]); ll ans = 0; for (int i = 0; i < s.size(); i++) { if (!se.empty() && s[i] < * (--se.end())) { ans = ans - v[s[i] - 'A']; vr[i] = -1; } else { ans = ans + v[(s[i] - 'A')]; vr[i] = 1; } se.erase(se.lower_bound(s[i])); } ll o = ans; for (int j = 0; j < 5; j++) { char req = 'A' + j; ll sum = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == req) continue; ll x = (vr[i]) * v[s[i] - 'A']; o = max(o, ans + v[j] - x - 2 * sum); if (x > 0 && s[i] < req) sum += x; } } cout
In D , i tried making a graph for intersecting components and tried removing the nodes with maximum edges, but when came to know the edge cases, I realized it req dp but it was too late.
after a long streak of fcuked up contests i was finally able to solve A B in an hour but again a few WA submissions (2 on A :-: ) so could have done it better :|
We have to increase from left and and decrease from right. but why the solution lies on the leftmost or rightmost occurrence of the letters? why don't we change a letter from the that is not the first occurrence? I didn't get this?
can you explain your code for this case abcaacbbbbbb...........1e5..........bbbb. I think your code will detect for first c , and try to make it a,b but think for 2nd c ? I am little confuse
Sir , In problem D what do you meant by Interval related problem. I mean i search the tag in codeforces but didn't found any. can you plz tell me where i can get interval related problems for practicing?
For Problem D: i had similar logic..but my code fails on 5 th test case, can anyone help me finding the error #include using namespace std; #define ull unsigned long long #define int long long int n; // ok = 0 .. means new picking... ok = 1 change even int generate(int i,int j, bool ok,pairarr[],vector &dp){ if(i == n){ if(ok== 0) return 0; else return 1e9; } if(dp[i][j+1][ok] != -1) return dp[i][j+1][ok]; if(j == -1){ // first interval auto p1 = generate(i+1,-1,0,arr,dp); auto p2 = generate(i+1,i,1,arr,dp); return dp[i][j+1][ok] = min(1+p1,p2); } int res = 1e9; if(ok == 1){ // completing already picked interval int p1; if(arr[i].first = arr[j].first){ auto temp = arr[i]; arr[i] = {min(arr[i].first,arr[j].first),max(arr[i].second,arr[j].second)}; res = min(res, generate(i+1,i,0,arr,dp)); arr[i] = temp; } else return dp[i][j+1][ok] = 1e9; res = min(res,1+ generate(i+1,j,1,arr,dp)); } else{ if(arr[i].first = arr[j].first){ res = min(res,1+generate(i+1,j,0,arr,dp)); } else{ res = min(res, generate(i+1,i,1,arr,dp)); res = min(res,1+generate(i+1,j,0,arr,dp)); } } return dp[i][j+1][ok] = res; } void solve(){ cin>>n; vector dp (n+1,vector(n+2,vector(2,-1))); pair arr[n]; for(int i = 0; i < n ; i++){ cin>>arr[i].first>>arr[i].second; } sort(arr,arr+n); int p = generate(0,-1,0,arr,dp); if(p >= 1e8) cout
Discord server: discord.gg/HNVWzHDMTF
Enjoyed doing problem C with dp. Problem D was interesting, if possible can you discuss or link some more problems like D?
Top notch content from a top notch coder .
Congratulations for candidate master brother😄😄
You've inspired me to become a cm too
Thanks
Congratulations for becoming CM!❤
Thanks man, keep the good work coming.
🔥editorial🛐
bro where to find those interval dp similar practice questions, which u were referring to, when u were explaining D problem.
Several such problems you can find on LC (i meant interval based problems)
@@Acodedaily ohh ok
Hello sir,
In the Problem C as we can only change one character so I am changing every character of the string to all the character from A to B but it is giving wrong on test case 9.
This is my code.
#include
#define ll long long int
using namespace std;
// author: Krishna Sharma
int main() {
ll t;
cin >> t;
while (t--) {
string s;
cin >> s;
vector v(5, 1);
vector vr(s.size() + 1, 1);
for (int i = 1; i < 5; i++) {
v[i] = v[i - 1] * 10;
}
multiset se;
for (int i = 0; i < s.size(); i++) se.insert(s[i]);
ll ans = 0;
for (int i = 0; i < s.size(); i++) {
if (!se.empty() && s[i] < * (--se.end())) {
ans = ans - v[s[i] - 'A'];
vr[i] = -1;
}
else {
ans = ans + v[(s[i] - 'A')];
vr[i] = 1;
}
se.erase(se.lower_bound(s[i]));
}
ll o = ans;
for (int j = 0; j < 5; j++) {
char req = 'A' + j;
ll sum = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == req) continue;
ll x = (vr[i]) * v[s[i] - 'A'];
o = max(o, ans + v[j] - x - 2 * sum);
if (x > 0 && s[i] < req) sum += x;
}
}
cout
what's the logic? why would changing all characters from A to B give you right answer?
@@Acodedaily Thanks I have got the logic now 🙂
In D , i tried making a graph for intersecting components and tried removing the nodes with maximum edges, but when came to know the edge cases, I realized it req dp but it was too late.
Long time no see 😂 .. Good to see you back
after a long streak of fcuked up contests i was finally able to solve A B in an hour but again a few WA submissions (2 on A :-: ) so could have done it better :|
Progress is still progress ❤️
We have to increase from left and and decrease from right. but why the solution lies on the leftmost or rightmost occurrence of the letters? why don't we change a letter from the that is not the first occurrence? I didn't get this?
Nearly in every div 2 i m able to solve A but not able to solve B...😥 help...how to solve B, and then C,D
B is mostly intuition based, have you tried solving a lot of problem of 1000-1400?
@@Acodedaily thanks 😊
B is more or less based on implementation and observation, try to uplsolve b from past few DIV 2 contests
Why are we taking only first and last occurance of a,b,c,d,e ? Why not all the occurances ?
because we want to maximise our solution.
It would be great help if you could suggest some standard practice problems for problem D.
check comments, someone already suggested.
hey
can you please tell in prob D on line 68 why is there a need to run a loop when in dfs function we are either leaving the element or taking it
we need to specify the starting element, the starting element could be any. hence need to start from all the elements.
@@Acodedaily oh yes
Thank you
What If Alice Take 1st n-1 And Then Bob Will Only Be Left With Summation N-1 And 1 So Bob Will Always Win Then In n>=3
why would alice want bob to win ?
Okay 😅, Thanks 😊
@@Acodedaily
Your implementation of C is O(n^2) right ?
Yep
How is it working then ?
@@rishabh507 it's constraints allow n2
@@Acodedaily for C or you’re saying about D ?
i don't thik so , we are only trying for changing first occurance OR last Occurance of A,B,C,D,E
means our algo runs in O(N*50)
can you explain your code for this case abcaacbbbbbb...........1e5..........bbbb. I think your code will detect for first c , and try to make it a,b but think for 2nd c ? I am little confuse
There may be a,b b/w the first and second c. There sign would be negative if you change 2nd only.
Sir I am not able to solve any questions wt shud I use cpp, python or javascript
solving questions isn't dependent on language but in general cpp is best for CP
Problem A:
iF N = 5,
1 1 1 1 1:
Alice -> 2 1 1 1
Bob -> 2 2 1
Alice -> 4 1
Now in this case Bob is the winner right ??
Why would alice select a move which makes her loose?
Sir , In problem D what do you meant by Interval related problem.
I mean i search the tag in codeforces but didn't found any.
can you plz tell me where i can get interval related problems for practicing?
You can find it on leetcode... Problem merge intervals, overlapping intervals, my calender, my calender 2..just google these names
Bro very nice explanation I am trying to do Dp in C whose implementation becomes much tougher for me😅
you'll learn with time :) keep grinding
@@Acodedaily In C time complexity is n^2, so it could get TLE. Luckily not got in this problem.
@@GauravKumar-jw9cf It will O(10*n) -> o(n)
For Problem D: i had similar logic..but my code fails on 5 th test case, can anyone help me finding the error
#include
using namespace std;
#define ull unsigned long long
#define int long long
int n;
// ok = 0 .. means new picking... ok = 1 change even
int generate(int i,int j, bool ok,pairarr[],vector &dp){
if(i == n){
if(ok== 0) return 0;
else return 1e9;
}
if(dp[i][j+1][ok] != -1) return dp[i][j+1][ok];
if(j == -1){
// first interval
auto p1 = generate(i+1,-1,0,arr,dp);
auto p2 = generate(i+1,i,1,arr,dp);
return dp[i][j+1][ok] = min(1+p1,p2);
}
int res = 1e9;
if(ok == 1){
// completing already picked interval
int p1;
if(arr[i].first = arr[j].first){
auto temp = arr[i];
arr[i] = {min(arr[i].first,arr[j].first),max(arr[i].second,arr[j].second)};
res = min(res, generate(i+1,i,0,arr,dp));
arr[i] = temp;
}
else return dp[i][j+1][ok] = 1e9;
res = min(res,1+ generate(i+1,j,1,arr,dp));
}
else{
if(arr[i].first = arr[j].first){
res = min(res,1+generate(i+1,j,0,arr,dp));
}
else{
res = min(res, generate(i+1,i,1,arr,dp));
res = min(res,1+generate(i+1,j,0,arr,dp));
}
}
return dp[i][j+1][ok] = res;
}
void solve(){
cin>>n;
vector dp (n+1,vector(n+2,vector(2,-1)));
pair arr[n];
for(int i = 0; i < n ; i++){
cin>>arr[i].first>>arr[i].second;
}
sort(arr,arr+n);
int p = generate(0,-1,0,arr,dp);
if(p >= 1e8) cout
when you close a pair [{l1,r1},{l2,r2}] then you have to check that the next pair doesn't have intersection with max (r1,r2) not just r2.
@@Acodedaily While picking for the second time, i had changed the r2 as max(r1,r2)..
@@rishukumarsingh3926 can you ping on discord and mention your code as well ?