Could Someone tell the optimal approach

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
24:33:19
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
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

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
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

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя AJ__20

Could Someone tell the optimal approach

Автор AJ__20, история, 18 месяцев назад, По-английски

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 месяцев назад
11

Комментарии (8)

Показать архивные | Написать комментарий?

vitosevskich

18 месяцев назад, # |

+17

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

→ Ответить

Prabhxs

18 месяцев назад, # |

← 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;
}

→ Ответить

vgtcross

18 месяцев назад, # ^ |

← 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

→ Ответить

Prabhxs

18 месяцев назад, # ^ |

+11

thanks, my bad. Updated the code.

→ Ответить

AJ__20

18 месяцев назад, # ^ |

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

→ Ответить

Prabhxs

18 месяцев назад, # ^ |

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

→ Ответить

AJ__20

18 месяцев назад, # ^ |

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

→ Ответить

Prabhxs

18 месяцев назад, # ^ |

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;
}

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 17:01:42 (i2).

Десктопная версия, переключиться на мобильную.

При поддержке