r/codeforces

What type of thought arrived you to solution of c like what observation or thinking or which type of questions helped you arrive you to solution
Please help as i am newbie

I cannot stop checking my profile for a rating change.
Gave yesterday's edu div 2 contest. How did it go for you all?

In yesterday's edu div2, imo spotting LCS was undoubtably easy but where to apply it made the problem way harder...

So this is a question to the ones who successfully solved D: how did you arrive/think about the "Prefix sum % 10" possibility and how did you prove/know it was correct? because in my eyes spotting that is not intuitive at all, even now im not fully convinced on why that approach works as correctly as it does.

What do you guys think about today's problems? B tripped me up real bad then had an insane comeback and solved till D by 1 hr 20 mins. E seems like something I would do if given 2 more hours😭

I am a specialist currently and genrerally solve a,b,c in an hour but like today solved a,b in 25 mins but spent 60 mins on C to solve it but the number of solves for C aren't showing its toughness or am I just dumb

I feel like crying and feel like I am extremely dumb whenever I perform below my rating level what should I do I feel like quitting sometimes

I am kinda new on reddit(and also on cf) and made this account just to post this but i feel like the intuition for B was tougher than C like i got the idea for C in just a few mins but couldnt think of the fact that B required suffix max. Also i feel implementation wise C was also easier but i guess thats just my personal opinion. Pls tell how to think of problems like B like i was thinking greedy but that wasnt working.

Hi,i solved around 300 questions on cf and mostly between 1200 and 1500,and my current rating is 1100 (max rated 1200),in today's contest i was able to solve only a, and solved b and c within 10 min after the contest,the main problem with me is i have a lot of anxiety when the contest is running and I'm unable to think under pressure,my mindset throughout the contest was to solve the questions as fast as possible,and i think i have the wrong mindset,any advice from seniors about mindset would be very grateful,what should be the mindset in cp and while giving the contest ?

The observation i had was just find the smallest partition possible for first 2 by counting number of 1 in 1st half and when it exceeds no of 2s and 3s change boolean variable to true and close the 2nd partition with the same concept of counting nos of 1 and 2. Basically make the 2nd partition as soon as it is possible so that there is atleast 1 element left for 3rd partition.

Code:

void solve(){


    int n;
    cin>>n;
    vector<int> v(n);
    for(auto& x: v) cin>>x;
    int count1=0;
    int count23=0;
    int count12=0;
    int count3=0;
    bool found=false;
    bool found2=false;
    int number;
    for(int i=0;i<n;i++){
        if(!found){
            if(v[i]==2||v[i]==3){
                count23++;
            }else{
                count1++;
                if(count1>count23){
                     found=true;
                     if(v[i+1]==3) i++;
                }else if(count1==count23 ) found=true;
            }
        }else if(!found2){
           
            if(v[i]==3) count3++;
            else{
                count12++;
                if(count12>=count3){
                       found2=true;
                       number=i;
                       break;
                } 
            }
        }
        
        
    }
  
    if(found && found2&& number!=n-1) cout<<"YES\n";
    else cout<<"NO\n";
    
}

https://preview.redd.it/kbvs5viu0nbh1.png?width=1471&format=png&auto=webp&s=0f14d618b2521081efa9a82d2c1af9b19234ba74

i wasted so much time on b for no reason i was trying to find better way but endup with the idea from where i started just check if count of 3 current no. and last valid place for 1 found is less than half of size ....
after than c was long question in my opinion it was long in solving part logic was easy tbh but reach there took time for me it was multi step processs idk man
i had find freq. and then find sf summation of it and then check the condition with k for each i
i could have got alot better rank i belive if didnt wasted alot of time and b and because it i had no time for d
i could be pupil
btw its my practice account i am pupil on my account

At first I thought i could solve it and i even wrote the code but realised that to cover all scenarios i would need dp at that point I quit it seemed like 1900 rated what do u guys think????

i have been doing leetcode and cf since 4-5 months. Genuinely i cannot think of Greedy problems . At times I can solve 1300 greedy ones sometimes get stuck at 900 ones too. What even is the greedy bullshit? its no algorithm , theres no theory involved its just TRUST ME BRO .

Was there a way apart from db to solve these questions??

took me way too long to do a and b, mainly cause stuff was happening around me, i skipped C and D because I couldnt figure out an approach, might revisit them later

finally, I figured out what to do for E, wrote a code, then spent an hour debugging the code, first for a sigfpe and then for an answer delivery error. I couldn't find the error, so after the contest ended, I gave it to gemini to see what it was.

ONE IF CONDITION ERROR.

The cherry on the top was that my code got accepted, too late though.

This was my code:

1. #include <bits/stdc++.h>
2. using namespace std;
5. void solve(){
6. int l, r, n, x = 0;
7. cin >> l >> r >> n;
9. vector<bool> a(32, false), b(32, false), c(32, false);
10. for(int i = 0; i < 31; i++){
11. if(r & (1 << i)) a[i] = true;
12. if(l & (1 << i)) b[i] = true;
13. //if(a[i] && b[i]) cout << i;
14. }
16. int i = 32;
17. while(i > 0){
18. i--;
19. if(a[i]==b[i]) c[i] = a[i];
20. else{
21. c[i] = a[i];
22. break;
23. }
24. }
26. for(int i = 31; i >= 0; i--){
27. x *= 2;
28. if(c[i]) x++;
29. //if(c[i]) cout << i << " ";
30. }
31. int y = l;
32. y = max(1 << (31 - __builtin_clzl(x - 1)), l);
33. //cout << x << " " << y << endl;
35. string s1 = "", s2 = "";
36. while(x > 0){
37. s1 += (x % 2) ? '1' : '0';
38. x /= 2;
39. }
40. while(y > 0){
41. s2 += (y % 2) ? '1' : '0';
42. y /= 2;
43. }
44. if (s1.empty()) s1 = "0";
45. if (s2.empty()) s2 = "0";
47. reverse(s1.begin(), s1.end());
48. reverse(s2.begin(), s2.end());
50. int p = s1.size(), q = s2.size();
51. for(int i = 0; i < n; i++){
52. if((s1[i % p] - '0') && (s2[i % q] - '0')) cout << '1';
53. else cout << '0';
54. }
55. cout << "\n";
56. }
58. int main() {
59. // your code goes here
60. int t;
61. cin >> t;
62. while(t--) solve();
63. }

Calculate the prefix sum for all indices using logic +1 for 1, -1 for 2 and 3.

Now iterate from backwards and calculate the suffix sum using logic +1 for 1 and 2, -1 for 3,and also maintain a mn,which tells us the min suf sum found from index i+1 to n-1,at any point,pre[i -1]> 0 and suf - mn >=0,we got the answer and we can print yes,if not do it till index 1,if no index satisfies this condition cout no.

Think why the ( suf - mn >= 0) logic works,its just the sum of subarray.from 0 till i - 1 is the part 1,i to mn -1 is second part and mn to n -1 is the third part.

Code

void solution(){

int n;

cin >> n;

vector<int> s(n);

for(int i = 0; i < n; i++) cin >> s[i];

vector<int> pre(n + 1,0);

pre[0] = (s[0] == 1) ? 1 : -1;

for(int i = 1; i < n; i++) pre[i] = pre[i - 1] + ((s[i] == 1) ? 1 : -1);

int sum = 0;

int mn = 1e8;

for(int i = n - 1; i > 0; i--){

sum += ((s[i] == 3) ? -1 : 1);

if(pre[i - 1] >= 0){

if(sum - mn >= 0){

cout<<"YES"<<endl;

return;

}

}

mn = min(mn,sum);

}

cout<<"NO"<<endl;

}