I used matrix chain dp to solve this question-
my code:
CodeChef: Practical coding for everyone
But since matrix chain has time complexity of O(N^3) so it gives TLE for greater value of N so for N>650 ,I just used greedy and it got AC.
In Above solutions the ans for
1
26 2
5 1 3 4 3 4 3 4 5 1 3 3 3 3 4 4 4 4 5 1 3 4 3 4 3 4
is 24 (same as Editorialist’s Solution),
but the optimal solution would be 22 because, we split it as:
1 : {5 1 3 4 3 4 3 4} ======= further split into three tables {5 1 3 4 } {3 4} {3 4 } ===== efficiency is 2+2+2 = 6
2 : {5 1 3 3 3 3 4 4 4 4 } ======= efficiency is 2 + 8 =10
3 : {5 1 3 4 3 4 3 4} ======= further split into three tables {5 1 3 4 } {3 4} {3 4 } ===== efficiency is 2+2+2 = 6
So Total minimum efficiency would be 10 + 6 +6 = 22
2 Likes
That is what I wrote in my earlier remarks. The link is given below.
for _ in range(int(input())):
n,k=map(int,input().split())
f=list(map(int,input().split()))
dp=[]
dp.append(0)
for i in range(1, n + 1):
dp.append(k+dp[i-1])
dic={}
c=0
for j in range(i - 1, -1, -1):
if f[j] not in dic.keys():
dic[f[j]]=1
else:
dic[f[j]]+=1
if(dic[f[j]]==2):
c+=2
elif dic[f[j]]>2:
c+=1
dp[i]=min(dp[i], dp[j]+k+c)
print(dp[-1])My solution based on the video explanation:
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t, n, m, k, q, x, y;
string s;
bool flag;
cin >> t;
while (t--) {
cin >> n >> k;
vll v(n);
vin(v);
vll dp(n, 0);
dp[0] = k;
unordered_map<ll, ll> cnt;
FOR (i, 1, n) {
ll args = 0;
dp[i] = INT32_MAX;
FORD (j, i, 0) {
cnt[v[j]]++;
if (cnt[v[j]] == 2) args += 2;
else if (cnt[v[j]] > 2) args++;
dp[i] = min(dp[i], dp[j - 1] + args + k);
}
cnt[v[0]]++;
if (cnt[v[0]] == 2) args += 2;
else if (cnt[v[0]] > 2) args++;
dp[i] = min(dp[i], args + k);
cnt.clear();
}
cout << dp.back() << '\n';
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxN = 1005;
const ll inf = 1e16;
ll ar[maxN];
ll n, k;
ll dp[maxN];
int main() {
int t;
cin>> t;
while(t-- ) {
cin>> n>> k;
for(int i=0; i<n; i++) cin>> ar[i];
for(int i=0; i<maxN; i++) dp[i] = inf;
dp[n] = 0;
for(int i = n - 1; i >= 0; i--) {
// calculate fights in the people from i to n
// ans = fights + dp[i]
map<ll, ll> mp;
ll fights = 0, amin = inf;
for(int j = i; j < n; j++) {
if(mp[ar[j]]) {
if(mp[ar[j]] == 1) {
fights += 2;
}
else fights++;
mp[ar[j]] ++;
amin = min(amin, k + fights + dp[j + 1]);
}
else {
mp[ar[j]] = 1;
amin = min(amin, k + fights + dp[j + 1]);
}
}
dp[i] = amin;
}
cout<<dp[0]<<endl;
}
return 0;
}Can anyone explain me how is the time complexity O(n^2) . Wouldn’t it be O(2^n) ?
Can you explain me how is the time complexity O(n^2). Wouldn’t it be O(2^n) ?
Why does your input only have 24 spaced integers? I am new here but shouldn’t you input 26 numbers?
I used Logic similar to Matrix Chain Multiplication Problem of DP. It is an O(n^3) Time Algorithm. But with some common sense modification I was able to reduce down the Constant Factor. It got me All Clear for All Test Cases except for one where I got TLE.
My Solution : CodeChef: Practical coding for everyone
Yes, it is. It should be
1
24 2
5 1 3 4 3 4 3 4 3 3 3 3 4 4 4 4 5 1 3 4 3 4 3 4
Output : 22
I have solve this problem without using dp.
This is my solution
https://www.codechef.com/viewsolution/36481841
For all those who didn’t understand why their greedy is giving wrong output in 2 test cases, can try this test case
10 6
1 2 3 1 4 5 2 3 4 5
answer -> 14
here greedy doesn’t work.
My code gives 14 as output, but showed “WA” for subtask 2, first case. For other test cases it earned “AC”. Would you please tell me the reason. I had repeatedly asked for the test case (Sub-Task 2, Task# 2) with its answer but not received. That means something is wrong there (Dal me kuchh kala hai !!!).
I am, again, forwarding the link of my code. If anyone tell me where is the mistake in this code, it will be a great help for me.
My code gives 14 as output, but showed “WA” for subtask 2, first case. For other test cases it earned “AC”. Would you please tell me the reason. I had repeatedly asked for the test case (Sub-Task 2, Task# 2) with its answer but not received. That means something is wrong there (Dal me kuchh kala hai !!!).
I am, again, forwarding the link of my code. If anyone tell me where is the mistake in this code, it will be a great help for me.
why should the answer be 10 ??
how would you make them sit ??
any explanation
Oh sorry my bad. Edited the comment, now there are 26 integers.
My code does not show 10, it shows output as 14. Check it.
The arrangement is (1 2 3 1 4 5), (2 3 4 5)
Total inefficiency =(6+2) + (6) = 14.