Could Someone tell the optimal approach

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
30:08:40
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

AJ__20's blog

Could Someone tell the optimal approach

By AJ__20, history, 18 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
18 months ago
11

Comments (8)

Show archived | Write comment?

vitosevskich

18 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

18 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

18 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

18 months ago, # ^ |

+11

thanks, my bad. Updated the code.

→ Reply

AJ__20

18 months ago, # ^ |

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

→ Reply

Prabhxs

18 months ago, # ^ |

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

→ Reply

AJ__20

18 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

18 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