ogfemboy's blog

google oa 2024
By ogfemboy, history, 6 months 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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you have the constraints for both problems?

→ Reply
»
6 months ago, # |
  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
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, it's mentioned in the problem that you can only change a number to 0.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, didn't notice. Then shouldn't answer be 2? i.e. say two partitions: [0,5] and [0,0,5,0] having equal sums of 5

      → Reply
»
6 months ago, # |
  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
  • »
    »
    6 months ago, # ^ |
      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
  • »
    »
    5 months ago, # ^ |
      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
    • »
      »
      »
      5 months ago, # ^ |
      ← 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
      • »
        »
        »
        »
        5 months ago, # ^ |
          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
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            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
»
6 months ago, # |
  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
»
6 months ago, # |
← 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
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wont this approach count some triplets multiple times. Can you please prove that this works ?

    → Reply
»
6 months ago, # |
← 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
  • »
    »
    5 months ago, # ^ |
      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
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

whats the approach for second one?

→ Reply
  • »
    »
    6 months ago, # ^ |
      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
    • »
      »
      »
      6 months ago, # ^ |
        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
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        nah

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It will count multiple time ig for some strings eg ababab no of palindrome from 0 to 1 is 2 and from 0 to 2 is 4 but when you multiply contribution of 0 to 1 occurred again

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

I have pics for these questions. Drive Link

→ Reply
»
5 months ago, # |
← 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
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Spoiler
→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This should work for q2

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Function to find all palindromic substrings
void findPalindromicSubstrings(const string& S, vector<pair<int, int>>& palindromic_pairs) {
    int n = S.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    
    // Single characters are palindromes
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
        palindromic_pairs.emplace_back(i, i);
    }
    
    // Check for palindromes of length 2
    for (int i = 0; i < n - 1; ++i) {
        if (S[i] == S[i + 1]) {
            dp[i][i + 1] = true;
            palindromic_pairs.emplace_back(i, i + 1);
        }
    }
    
    // Check for palindromes of length greater than 2
    for (int length = 3; length <= n; ++length) {
        for (int i = 0; i <= n - length; ++i) {
            int j = i + length - 1;
            if (S[i] == S[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                palindromic_pairs.emplace_back(i, j);
            }
        }
    }
}

// Function to count good triplets
int countGoodTriplets(const string& S) {
    vector<pair<int, int>> palindromic_pairs;
    findPalindromicSubstrings(S, palindromic_pairs);
    
    int count = 0;
    int m = palindromic_pairs.size();
    
    for (int a = 0; a < m; ++a) {
        for (int b = a + 1; b < m; ++b) {
            for (int c = b + 1; c < m; ++c) {
                if (palindromic_pairs[a].second < palindromic_pairs[b].first && 
                    palindromic_pairs[b].second < palindromic_pairs[c].first) {
                    ++count;
                }
            }
        }
    }
    
    return count;
}

// Example usage
int main() {
    string S = "ababa";
    cout << countGoodTriplets(S) << endl;  // Output: number of good triplets
    return 0;
}
→ Reply