My planned post contest discussion stream

Dislike it because it's a speed-round. It seems that most people (at least my mates) get the first 5 problem and the time has become even more important.

Like it because I'm faster than them.

True, speed is an important factor in cp. Unfortunately, our Chinese participants often train using the OI format (no feedback during , evaluation after), so they may get disappointed again.

Problem E is way too standard,almost all have seen it or they can easily google it.

Just type — "sum of xor of all subarrays".

Speedforces (or Speedcoder)

The difficulty spike is insane because E has almost 3000 ACs but F and G has less than 300 ACs each

E — Xor Sigma Problem is a strictly easier version of CF1879D : Sum of XOR Functions. In fact, when I solved the harder version 10 days back, I had already prepared model solution for the easier version (was planning to write a blog and create an easy version). I was able to get AC by just changing 2 lines in the code from hard version. Well, lucky me, haha.

Code for ABC365E : XOR Sigma Problem

Code for CF1879D : Sum of XOR Functions

If you're a beginner to DP on Bit Manipulation, here are some easy problems.

• Xour
• XOR to All
• Xor Sigma Problem
• Sum of XOR Functions

If you're at an intermediate level, you can try these:

• Maximum And Queries (easy version)
• Birthday Gift
• A BIT of an Inequality

If you're at an advanced level, you can try these:

• GCD is Greater
• Cases

what is the idea for G?

Liked G but wasn't able to figure out F, Sol for F?

bruh

Origin & difficulty & data aside, I think F and G are good.

has anyone solved d with recursive dp?

Brute force passed G. Code

In problem G I came up with the idea that is similar to the Japanse editorial: comparing people with less than $$$\sqrt M$$$ segments by brute force (two pointers, for example), and precomputing something like prefix sums in $$$O(N \cdot \sqrt M)$$$ on compressed coordinates for people with more than $$$\sqrt M$$$ segments, so I could calculate in $$$O(\sqrt M)$$$ intersection for people with small and large amount of segments. But what should I do in case where I have to calculate intersection for people that both have more than $$$\sqrt M$$$ segments? The amount of such pairs still would be $$$O(M)$$$ worst case, or am I missing something?

P.S. I miss written English editorials :(

I think there is binary lifting solution to F as well but seems too much details will be involved.

Please share recursive memo solution for D ?

Can anyone tell me why this dp idea won't work(or is there something wrong with my code)
I have used dp[i][j] as maximum number of games that takahasi can win till index 'i' if
j=0, if the i^th round is drawn
j=1, if the i^th round is won by takahashi

  #pragma GCC optimize("-O2")
  #pragma GCC optimize("O3,unroll-loops")  
  #include <bits/stdc++.h>
  #define lli long long int
  #define pii pair<int,int>
  #define mii map<int,int>
  #define vi vector<int>                      //(num<<i) == num* pow(2,i);
  #define pb push_back                        //(num>>i) == num/pow(2,i);
  #define vlli vector<long long int>
  #define nl cout<<'\n'
  #define yy cout << "YES\n" 
  #define nn cout << "NO\n" 
  #define all(a) a.begin(),a.end()
  #define IM  INT_MAX
  #define IMN INT_MIN
  #define pc cout<<count<<'\n'
  #define int long long int
  #define mp make_pair
  #define vpii vector<pair<int,int>>
  #define Yy cout<<"Yes\n"
  #define Nn cout<<"No\n"
  using namespace std;
  signed main(){
     ios_base::sync_with_stdio(false);
      cin.tie(NULL);
     int n;cin>>n;
     string s;cin>>s;
     vector<vector<int>>dp(n,vector<int>(2,0));
     dp[0][1]=1;
     for(int i=1;i<n;i++){
        if(s[i]==s[i-1]){
            dp[i][0]=dp[i-1][1];
            dp[i][1]=dp[i-1][0]+1;
        }
        else{
            if(s[i]=='R'&&s[i-1]=='P'){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=dp[i-1][1]+1;
            }
            if(s[i-1]=='R'&&s[i]=='P'){
                dp[i][1]=max(dp[i-1][0],dp[i-1][1])+1;
                dp[i][0]=dp[i-1][1];
            }
            if(s[i]=='R'&&s[i-1]=='S'){
                dp[i][0]=dp[i-1][0];
                dp[i][1]=dp[i-1][1]+1;
            }
            if(s[i-1]=='R'&&s[i]=='S'){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=dp[i-1][1]+1;
            }
            if(s[i-1]=='P'&&s[i]=='S'){
                dp[i][0]=dp[i-1][0];
                dp[i][1]=max(dp[i-1][0],dp[i-1][1])+1;
            }
            if(s[i-1]=='S'&&s[i]=='P'){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=dp[i-1][1]+1;
            }
        }
        
     }
   
    cout<<max(dp[n-1][0],dp[n-1][1]);
  }

Could anyone tell me what's the time complexity of Problem C

Is there any simpler solution for it?