D. Three Activities | Codeforces Solution | Codeforces Round 916 (Div. 3)
Winter holidays are coming up. They are going to last for 𝑛 days. During the holidays, Monocarp wants to try all of these activities exactly once with his friends: go skiing; watch a movie in a cinema; play board games. Monocarp knows that, on the 𝑖 -th day, exactly 𝑎𝑖 friends will join him for skiing, 𝑏𝑖 friends will join him for a movie and 𝑐𝑖 friends will join him for board games.
memory limit per test: 256 megabytes
Winter holidays are coming up. They are going to last for n days.
During the holidays, Monocarp wants to try all of these activities exactly once with his friends:
- go skiing;
- watch a movie in a cinema;
- play board games.
Monocarp knows that, on the i-th day, exactly ai friends will join him for skiing, bi friends will join him for a movie and ci friends will join him for board games.
Monocarp also knows that he can't try more than one activity in a single day.
Thus, he asks you to help him choose three distinct days x, y, z in such a way that the total number of friends to join him for the activities (ax + by + cz) is maximized.
The first line contains a single integer t (1 ≤ t ≤ 104) — the number of testcases.
The first line of each testcase contains a single integer n (3 ≤ n ≤ 105) — the duration of the winter holidays in days.
The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 108) — the number of friends that will join Monocarp for skiing on the i-th day.
The third line contains n integers b1, b2, …, bn (1 ≤ bi ≤ 108) — the number of friends that will join Monocarp for a movie on the i-th day.
The fourth line contains n integers c1, c2, …, cn (1 ≤ ci ≤ 108) — the number of friends that will join Monocarp for board games on the i-th day.
The sum of n over all testcases doesn't exceed 105.
For each testcase, print a single integer — the maximum total number of friends that can join Monocarp for the activities on three distinct days.
4 3 1 10 1 10 1 1 1 1 10 4 30 20 10 1 30 5 15 20 30 25 10 10 10 5 19 12 3 18 18 6 17 10 13 15 17 19 11 16 3 11 17 17 17 1 17 18 10 15 8 17 3 13 12 10 17 5 4 18 12 4 11 2 16 16 8 4 14 19 3 12 6 7 5 16 3 4 8 11 10 8 10 2 20 3
30 75 55 56
In the first testcase, Monocarp can choose day 2 for skiing, day 1 for a movie and day 3 for board games. This way, a2 = 10 friends will join him for skiing, b1 = 10 friends will join him for a movie and c3 = 10 friends will join him for board games. The total number of friends is 30.
In the second testcase, Monocarp can choose day 1 for skiing, day 4 for a movie and day 2 for board games. 30 + 20 + 25 = 75 friends in total. Note that Monocarp can't choose day 1 for all activities, because he can't try more than one activity in a single day.
In the third testcase, Monocarp can choose day 2 for skiing, day 3 for a movie and day 7 for board games. 19 + 19 + 17 = 55 friends in total.
In the fourth testcase, Monocarp can choose day 1 for skiing, day 4 for a movie and day 9 for board games. 17 + 19 + 20 = 56 friends in total.
Solution
int helper(vpi &a, vpi &b, vpi &c)
{
pii x = a[0];
pii y = b[0];
pii z = c[0];
for (auto it : b)
if (it.second != x.second)
{
y = it;
break;
}
for (auto it : c)
if (it.second != x.second && it.second != y.second)
{
z = it;
break;
}
return x.first + y.first + z.first;
}
void solve()
{
int n;
cin >> n;
vpi a(n), b(n), c(n);
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
a.pb({x, i});
}
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
b.pb({x, i});
}
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
c.pb({x, i});
}
sort(a.rbegin(), a.rend());
sort(b.rbegin(), b.rend());
sort(c.rbegin(), c.rend());
cout << max({helper(a, b, c), helper(a, c, b), helper(b, a, c), helper(b, c, a), helper(c, a, b), helper(c, b, a)}) << endl;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define F first
#define S second
#define pb push_back
#define si set <int>
#define vi vector <int>
#define pii pair <int, int>
#define vpi vector <pii>
#define vpp vector <pair<int, pii>>
#define mii map <int, int>
#define mpi map <pii, int>
#define spi set <pii>
#define endl "\n"
#define sz(x) ((int) x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue <int>
#define que_min priority_queue <int, vi, greater<int>>
#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a) for(auto x : a) cout << x << " "; cout << endl
#define print1(a) for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y) for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
#define scanit(a,n) for(ll indexaa=0; indexaa<n; indexaa++) cin>>a[indexaa];
inline int power(int a, int b)
{
int x = 1;
while (b)
{
if (b & 1) x *= a;
a *= a;
b >>= 1;
}
return x;
}
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
const char* comma = strchr (names + 1, ',');
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}
const int N = 200005;
int helper(vpi &a,vpi &b,vpi &c){
pii x = a[0];
pii y = b[0];
pii z = c[0];
for(auto it:b)if(it.second!=x.second){y = it;break;}
for(auto it:c)if(it.second!=x.second && it.second!=y.second){z=it;break;}
return x.first+y.first+z.first;
}
void solve() {
int n;
cin>>n;
vpi a(n),b(n),c(n);
for (int i = 0; i < n ; i++){int x;cin>>x;a.pb({x,i});}
for (int i = 0; i < n ; i++){int x;cin>>x;b.pb({x,i});}
for (int i = 0; i < n ; i++){int x;cin>>x;c.pb({x,i});}
sort(a.rbegin(),a.rend());
sort(b.rbegin(),b.rend());
sort(c.rbegin(),c.rend());
cout<<max({helper(a,b,c),helper(a,c,b),helper(b,a,c),helper(b,c,a),helper(c,a,b),helper(c,b,a)})<<endl;
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
clock_t z = clock();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
Solution
The solution aims to maximize the total number of friends joining Monocarp for three distinct activities (skiing, movie, board games) on three different days. Here's how it works:
-
Helper Function:
- The
helper(vpi &a, vpi &b, vpi &c)function takes three sorted vectors and returns the sum of three values, ensuring they are from distinct days. - It picks:
- x = a[0]: The maximum value from the first array.
- y: The first value from b with a different index than x.
- z: The first value from c with an index different from both x and y.
- It returns
x.first + y.first + z.first(sum of the friend counts).
- The
-
Maximizing the Result:
- Since we need the maximum possible sum, we call
helperwith all six permutations of the arrays (a, b, c, a, c, b, etc.). - This ensures we consider cases where the maximum values from different activities might yield a better result when paired differently.
- The
maxfunction with an initializer list finds the largest sum among these permutations.
- Since we need the maximum possible sum, we call
-
Output:
- The maximum sum is printed for each test case.
Why It Works:
- Sorting ensures we start with the largest possible values.
- Checking all permutations accounts for scenarios where the largest values might conflict (same day) or where a slightly smaller value from one array pairs better with larger values from others.
- The time complexity is O(n log n) per test case due to sorting, and the helper function is O(n), making the overall solution efficient.
Example Walkthrough (First Test Case):
- Input:
a = {1, 10, 1}, b = {10, 1, 1}, c = {1, 1, 10} - After sorting:
a = {{10, 1}, {1, 0}, {1, 2}}, b = {{10, 0}, {1, 1}, {1, 2}}, c = {{10, 2}, {1, 0}, {1, 1}} helper(a, b, c): x = {10, 1}, y = {10, 0}, z = {10, 2} → Sum = 30- Other permutations are checked, but 30 is the maximum.
Raunit Verma
Technical Writer at CodingKaro
