PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: souradeep1999
Tester: mridulahi
Editorialist: iceknight1093
DIFFICULTY:
2453
PREREQUISITES:
Dynamic programming
PROBLEM:
An array is called beautiful if for every pair of elements in it, one of them divides the other.
The score of a beautiful array B equals \min(B)\cdot |B|.
You’re given an array A, which you can rearrange as you like.
What’s the maximum possible score of a beautiful subarray of the rearranged array?
EXPLANATION:
First, let’s analyze what a beautiful array B looks like.
For any two elements of B, one must divide the other.
The order of B doesn’t particularly matter, so let’s assume B_1 \leq B_2 \leq B_3\leq\ldots\leq B_k.
Then, notice that the condition essentially just means that B_i must divide B_j for every 1 \leq i\lt j\leq k.
In particular, this means that B_i must divide B_{i+1} for every i.
Conversely, if B had such a property, then it’s clearly a beautiful array.
That is, a beautiful array is one where (when seen in sorted order) each element divides the next.
Looking at it differently, we have a “chain” of integers that divide each other.
Going back to our original problem, we want to find the maximum possible score of a beautiful of A, after rearranging it.
Since we’re free to rearrange things, the only thing we really need to do is to decide which elements we want to keep in the subarray; then put them all together and order the rest however we like.
Recall that the score of B is \min(B)\cdot |B|. So, if \min(B) is fixed, then our best bet is to maximize the length of B - that is, have a chain as long as possible.
This can be computed using dynamic programming.
Let \text{dp}[x] be the length of the longest chain with x as the least element.
Then, by iterating across what the next element in the chain is, we have
where \text{freq}[x] is the number of occurrences of x in A (if we choose one x, we might as well choose all of them).
The final answer is simply the maximum of (x\cdot \text{dp}[x]) across all x.
Since we’re iterating over multiples of x, the overall time complexity is \mathcal{O}(M + \frac{M}{2} + \frac{M}{3} + \frac{M}{4} + \ldots + \frac{M}{M}) = \mathcal{O}(M\log M).
Here, M is the maximum element of A - we don’t need to consider any multiples beyond it.
The sum of M across all tests is bounded by 2\cdot 10^5 as per the constraints, so this is good enough.
TIME COMPLEXITY
\mathcal{O}(N + M\log M) per testcase, where M = \max(A).
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define ordered_set tree<int, nuint_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=100005;
#define M 1000000007
#define BINF 1e16
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 100005
#define deb(xx) cout << #xx << " " << xx << "\n";
const int LG = 22;
int n, dp[N], arr[N];
vector<int> v;
int foo(int i) {
if(i > v.back()) return 0;
if(dp[i] != -1) {
return dp[i];
}
int l = arr[i];
for(int j = 2 * i; j <= v.back(); j += i) {
l = max(l, arr[i] + foo(j));
}
return dp[i] = l;
}
void solve() {
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
for(int i = 0; i <= a[n - 1]; i++) {
dp[i] = -1;
arr[i] = 0;
}
v.clear();
for(auto i : a) {
arr[i] += 1;
}
for(int i = 1; i <= a[n - 1]; i++) {
if(arr[i] > 0) {
v.push_back(i);
}
}
for(int i = 1; i <= a[n - 1]; i++) {
if(arr[i] > 0) {
foo(i);
}
}
int c = 0;
for(int i = 1; i <= a[n - 1]; i++) {
c = max(c, i * dp[i]);
}
cout << c << endl;
}
#undef int
int main() {
#define int long long int
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("optput.txt", "w", stdout);
#endif
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++){
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Tester's code (C++)
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T rand(T a, T b){
return uniform_int_distribution<T>(a, b)(rng);
}
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < b; i++)
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long
const ll mod = 998244353;
const ll INF = 1e18;
/* ----------------------------------------------------- GO DOWN ---------------------------------------------------------------------- */
const int maxn = 1e5 + 1;
int c[maxn];
int prevn = 0;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
for (int i = 1; i <= prevn; i++) c[i] = 0;
prevn = 0;
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
prevn = max(prevn, a[i]);
c[a[i]]++;
}
int ans = 0;
for (int i = prevn; i > 0; i--) {
int x = c[i];
for (int j = i + i; j <= prevn; j += i) {
c[i] = max(c[i], x + c[j]);
}
ans = max(ans, c[i] * i);
}
cout << ans << "\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mx = max(a)
freq = [0]*(mx + 1)
for x in a: freq[x] += 1
dp = [0]*(mx + 1)
for i in reversed(range(1, mx+1)):
for j in range(2*i, mx+1, i):
dp[i] = max(dp[i], dp[j])
dp[i] += freq[i]
ans = 0
for x in range(mx+1):
ans = max(ans, x*dp[x])
print(ans)
