# CHSEG - Editorial

Tester: mridulahi
Editorialist: iceknight1093

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

\text{dp}[x] = \text{freq}[x] + \max_{i\gt 1}(\text{dp}[i\cdot x])

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);
}
};
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 = *(mx + 1)
for x in a: freq[x] += 1
dp = *(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)

2 Likes

Can anyone tell mistake in my code , i know it will give TLE ,but it is giving WA , i just want to flaw in my logic
Solution: 1023144006 - CodeChef

‘’’
int n;
cin>>n;
vectorvec(n);
map<int,int>mp;
sort(all(vec));
mx=vec[n-1];
for(auto x:vec)
{
mp++;
}
ll int ans=mxmp[mx];
for(auto x:mp)
{
ll int start=x.first;
for(int j=2;j<=start;j++)
{
if(start%j!=0)
{
continue;
}
ll int cnt=mp[start];
ll int k=j;
ans=max(ans,cnt
(start));
while(k<=start && start%k==0)
{
if(mp.find(start/k)!=mp.end())
{
cnt+=mp[start/k];
ans=max(ans,cnt*(start/k));
}
k=k*2;
}
}
}
cout<<ans<<endl;
‘’’

I unable to understand with a number x , why you have make chain of 2x , 3x ,4x and all , it is not necessary that 2x , 3x will divide each other ?

for x only we are checking for all its multiple like 2x, 3x …
after selecting next multiple we are repeating the same thing for next chosen number.
Hope you got it We are not actually taking all the multiples we are only taking the one which maximizes the answer for current chosen ‘X’ so ‘2X’, ‘3X’, … are all divisible by ‘X’.

Instead of taking all muliples like 2x,3x,4x,5x,6x, … , we can take only prime multiples like 2x,3x,5x,7x …
https://www.codechef.com/viewsolution/1023188922

Why is this true? what if we had something like X, 4X is the array?

because dp[2x] would have already evalutated dp[4x] , consider y=2x, then 2y=4x. Then their is no need for that.