PROBLEM LINK:
Setter: Gaurish Baliga
Tester: Rohit Tawde
Editorialist: Gaurish Baliga
DIFFICULTY
Easy-Medium
PREREQUISITES:
Dynamic Programming.
PROBLEM
Abdusatarov was given a task by his discrete mathematics teacher. Being a smart kid, he was able to solve this task very fast and he wants to test if you can do the same.
Given an array, partition it into some arbitrary number of disjoint subarrays such that sum of LCM of all subarrays is maximum.
EXPLANATION
This problem can be solved using Dynamic Programming. We could use a single state i which represents the most optimal answer when we start from index i.
So the transition of our DP would be:
dp_i = \max_{k=i}^{n} (LCM(i...k) + dp_{k+1})
TIME COMPLEXITY:
O(N^2).
SOLUTION
Setter's Solution
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2222;
int a[MAXN], dp[MAXN], n;
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int f(int index)
{
if(index == n) return 0;
if(dp[index] != -1) return dp[index];
int answer = 0, lcm = 1;
for(int i = index; i < n; i++)
{
lcm /= gcd(a[i], lcm); lcm *= a[i];
answer = max(answer, lcm + f(i + 1));
}
return dp[index] = answer;
}
int32_t main()
{
memset(dp, -1, sizeof(dp));
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << f(0) << "\n";
}
Tester's Solution
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
int main() {
fast_io;
int t;
t=1;
while(t--){
ll n;
cin>>n;
vector<ll>a(n);
for(int i =0; i <n;i++){
cin>>a[i];
}
vector<ll>dp(n,0);
for(int i =0;i<n; i++){
ll k =a[i];
ll ans=a[i];
for(int j =i-1;j>=0;j--){
ans=max(ans,dp[j]+k);
ll g1=__gcd(k,a[j]);
ll g2=__gcd(k,g1);
k/=g2;
g1/=g2;
ll k1=a[j]/g1;
k=(k*k1);
}
ans=max(ans,k);
dp[i]=ans;
}
cout<<dp[n-1]<<endl;
}
return 0;
}