Could Someone tell the optimal approach

→ Pay attention

Before contest
Educational Codeforces Round 173 (Rated for Div. 2)
37:46:35
Register now »

→ Streams

By aryanc403

Before stream 39:56:35

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

View all →

→ Find user

→ Recent actions

Detailed →

AJ__20's blog

Could Someone tell the optimal approach

By AJ__20, history, 19 months ago, In English

You are given an array of strings A of size N. You need to pick two strings Ai and Aj such that len(Ai)* len(Aj) is maximized. Thanks in advance. Edit : Sry, forgot to add the constraints : there was a condition stating those two strings should have no common characters, then what would be the optimal solution ?

-6

AJ__20
19 months ago
11

Comments (8)

Show archived | Write comment?

vitosevskich

19 months ago, # |

+17

You can't do that in less than O($$$\text{total length of all strings}$$$) since you need to read the strings.

→ Reply

Prabhxs

19 months ago, # |

← Rev. 2 →

+11

I don't think there is any more optimal way than this?

Spoiler

//can use long long depending on the constraints

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

int main(){
    int n;
    cin >> n;
    int mxValOne = -1, mxValTwo = -1;
    for(int i = 0; i < n; i++){
        //reading the strings
        string s;
        cin >> s;
        int len = s.size();
        if( len >= mxValOne ){
            //inserting the max value in the secondMax
            mxValTwo = mxValOne;
            //jupdating the max Len with the currLen
            mxValOne = len;
        }
        else if( len > mxValTwo )
            mxValTwo = len;
    }
    //maxLen * secondMaxLen;
    cout << mxValOne * mxValTwo;
}

→ Reply

vgtcross

19 months ago, # ^ |

← Rev. 2 →

Correct idea, but the code is wrong. You forgot to test if the length of a given string is smaller than the largest but larger than the second largest.

Input:
3
a
abc
ab

Correct Output:
6

Your Output:
3

Corrected code

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

int main(){
    int n;
    cin >> n;
    int mxValOne = -1, mxValTwo = -1;
    for(int i = 0; i < n; i++){
        //reading the strings
        string s;
        cin >> s;
        int len = s.size();
        if(len >= mxValOne){
            //inserting the max value in the secondMax
            mxValTwo = mxValOne;
            //jupdating the max Len with the currLen
            mxValOne = len;
        } else if(len >= mxValTwo){
            //jupdating the secondMax Len with the currLen
            mxValTwo = len;
        }
    }
    //maxLen * secondMaxLen;
    cout << mxValOne * mxValTwo;
}

// it would be embarrassing if this was still incorrect

→ Reply

Prabhxs

19 months ago, # ^ |

+11

thanks, my bad. Updated the code.

→ Reply

AJ__20

19 months ago, # ^ |

Could you please tell the optimal approach for the modified question?

→ Reply

Prabhxs

19 months ago, # ^ |

can you please tell what are the constraints on the length of the array of strings?

→ Reply

AJ__20

19 months ago, # ^ |

That was was asked in test, i forgot the constraints but i tried brute force solution and got tle. My solution is n*n*n, so i was thinking what would be the optimized approach

→ Reply

Prabhxs

19 months ago, # ^ |

I guess, you can use bitmasking for this approach, wait lemme write it with the code.

Time Complexity Analysis

code

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

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

    vector<pair<int, int>> pr;

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        int len = s.size();
        int mask = 0;
        for(auto &a : s)
            mask |= 1 << (a - 'a');
        pr.emplace_back(mask, len);
    }

    int mxProd = 0;

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if( (pr[i].first & pr[j].first) == 0 ){
                mxProd = max(mxProd, pr[i].second * pr[j].second);
            }
        }
    }

    cout << mxProd;
    
    return 0;
}

→ Reply