Could Someone tell the optimal approach

Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

До соревнования
Codeforces Round (Div. 2)
2 дня
Зарегистрироваться »

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

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

№	Пользователь	Рейтинг
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

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

Всё →

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

№	Пользователь	Вклад
1	awoo	161
2	maomao90	160
3	adamant	157
4	maroonrk	154
5	-is-this-fft-	148
5	atcoder_official	148
5	SecondThread	148
8	Petr	147
9	TheScrasse	145
9	nor	145

Всё →

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

→ Прямой эфир

Детальнее →

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

Could Someone tell the optimal approach

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

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

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

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

vitosevskich

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

+17

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

→ Ответить

Prabhxs

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

← Rev. 2 →

+11

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

Спойлер

//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

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

← 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

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

+11

thanks, my bad. Updated the code.

→ Ответить

AJ__20

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

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

→ Ответить

Prabhxs

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

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

→ Ответить

AJ__20

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

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

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

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

Время на сервере: 21.07.2024 15:13:00 (l3).

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

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