Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

ogfemboy's blog

google oa 2024
By ogfemboy, history, 2 years ago, In English

guys sorry for the bad formating yesterday

Question 1=>

so you are given an array of integeres, you need to count the maximum number of partiotions that you can do, here partition means dividing the array into 2 parts such that the sum of both parts are equal. In addition to this you can do this operation once, change a number to 0

test case 1=> 6

-1 5 0 0 5 0

answer is 3, here we change -1 to 0

Question 2 => you are given a string of lower case english alphabets, you need to find the numbebr of palindromic triplets, A palindromic triplets is as such, suppose you have 3 non overlapping substring S1,s2,s3 then this triplet is a plaindromic triplet if all the individual substrings are palindromes and non overlapping. We need to find the number of such triplets

test case 1=> 4

abaa

answer is 5

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

small correction: Instead of here we change -1 to 0, it should be here we change -1 to 5

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can a problem be done like this .. for every number store (rightsum-leftsum) in a map ..

for given case : 11 1 1 1 -9 -9 would be the corresponding (rightsum-leftsum)..

now check for each number .. if we change -1 to 0.. check how many times we have 1 in the map .. similarly check for -5 for element 5

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Correct, and if you do leftsum — rightsum, you'll have to check the same number in the map, not the negative of the number. Am I correct?

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    can you please elaborate more on that, like how 2 times -9 is there? and give some pseudo code....Pls

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it 
      int n;
cin>>n;
int arr[n];
for(int i = 0; i < n; ++i){
    cin >> arr[i];
}
int rightsum=0;
for(auto it:arr) rightsum+=it;
map<int,int> mp;
int leftsum=0;
for(auto it:arr){
    // leftsum-rightsum
    rightsum-=it;
    leftsum+=it;

    int x=leftsum-rightsum;
    cout<<x<<" ";
    mp[x]++;
}
int mx=0;
for(auto it:arr){
    mx=max(mx,mp[it]);
}
cout << mx  << "\n";

      i think this should work

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I don't think so , try for

        2 2 0 0 5 0 0 2 2

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          yes you are right .. now i was thinking to check for both -it and +it in the map .. and adding both the maxs.. is it still wrong ?

          → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

for first question compute prefix sum and store the frequency of element in map now start iterating from left to right if you making ith element zero count frequency of element (sum+pref[i])/2 on left side and right side and take max of the sum.

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

for second question first compute matrix is_palindrome[i][j] (0 and 1) now find number of palindrome from i to j using dp. dp[i][j]=dp[i+1][j]+dp[i][j-1]+is_palindrome[i][j]-dp[i+1][j-1] (takes o(n^2)) now compute number of triplet from (0,i),(i+1,j-1),(j+1,n) using two nested loop and take the sum of the product . I think this will work here is code for dp.

#include<bits/stdc++.h>
using namespace std;
#define int long long

int palindrome(int i,int j,string &s,vector<vector<int>>&dp1){
    if(i==j){
        return dp1[i][j]=1;
    }
    if(i+1==j){
        return dp1[i][j]=(s[i]==s[j]?1:0);
    }
    if(dp1[i][j]!=-1)return dp1[i][j];

    if(s[i]!=s[j])return dp1[i][j]=0;

    return dp1[i][j]=palindrome(i+1,j-1,s,dp1);
}

int pcount(int i,int j,vector<vector<int>>&dp1){
    if(i==j){
        return dp1[j][i]=1;
    }
    if(i+1==j){
        if(dp1[i][j]==1){
            return dp1[j][i]=3;
        }
        else return dp1[j][i]=2;
    }
    if(dp1[j][i]!=-1)return dp1[j][i];

    return dp1[j][i]=pcount(i+1,j,dp1)+pcount(i,j-1,dp1)-pcount(i+1,j-1,dp1)+dp1[i][j];
}

int32_t main(){
    string s;
    cin>>s;
    int n=(int)s.size();
    vector<vector<int>>dp1(n,vector<int>(n,-1));
    for(int i=0; i<n; i++){
        for(int j=i; j<n; j++){
            if(dp1[i][j]==-1){
                palindrome(i,j,s,dp1);
            }
        }
    }
    pcount(0,n-1,dp1);


    }

}
→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

2nd question is DP we choose a substring if it is palindrome and 3 palindromes are required so we decrease the required count by one and will try to find the next remaining palindromes we can precompute the next indices for an index that will form a palindrome or we can check on go that will be overall worst worst-case O(n^2) here is the code:-

#include "bits/stdc++.h"
using namespace std;

int dp[1005][4];

bool ispalindrome(string s)
{
    string temp=s;
    reverse(temp.begin(),temp.end());
    if(s==temp)
        return true;
    return false;
}


int counttriplets(int ind,int rem,string s)
{
    if(rem==0)
        return 1;

    if(ind==s.size())
        return 0;

    if(dp[ind][rem]!=-1)
        return dp[ind][rem];

    string temp="";
    int ans=0;
    for(int i=ind;i<s.size();i++)
    {
        temp+=s[i];
        if(ispalindrome(temp)==true)
            ans+=(counttriplets(i+1,rem-1,s));
    }
    for(int i=ind+1;i<s.size();i++)
    {
        ans+=counttriplets(i,rem,s);
    }
    dp[ind][rem]=ans;
    return ans;
}



int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;

    for(int i=0;i<=n;i++)
    {
        dp[i][0]=-1;
        dp[i][1]=-1;
        dp[i][2]=-1;
        dp[i][3]=-1;
    }
    int ans=0;
    ans=counttriplets(0,3,s);
    cout<<ans<<"\n";


    return 0;
}

I think this will work if any correction needed pls do let me know it would be grateful to know other approaches...

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    the second loop causes duplicate counting, rather remove the loop and replace it with ans+=counttriplets(i+1,rem,s);

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

whats the approach for second one?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    i used a sparse table to keep track of all palindromic substring so using that you can know if the substring i-j is palindrom in 0(1), now i need to count the number of palindromic substring which end before i and start after j then multiply them

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      in second step, you are going to multiply nofPalins(0, i) * nofPalins(i+1, j) * nofPalins(j+1, n) right?

      Wont this count some triplets multiple times?

      → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

I have pics for these questions. Drive Link

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

For question 2 ig the following code should work (comments to explain what i did) Let me know if there are any testcases on which my code fails.

Spoiler
→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think the following should work for the 1st one -

Spoiler
→ Reply