What i have done is that i made everyone sit in such a way that nobody gets into an argument and calculated the total cost according to this arrangement.
Then I iterated through these tables and checked if merging current table into previous one will decrease the cost or not.
Thanks dude 
If somebody knows the example of 2nd sub task’s first and second cases then please post here, I really want to make my code work without DP.
The editorialist code is so simple and short. Loved it!
I’m a beginner and I knew this problem is similar to Matrix chain multiplication, yet not able to write the code.
I would like to share my code which I can bet is the weirdest code that passed all the subtasks.
https://www.codechef.com/viewsolution/36509790
It is mix of randomness with recursion and greedy! xD
I am new to this platform and also beginner in CP , so actually i didn’t know much about DP yet i tried this approach and its not fully like already discussed DP approach …but yet give some review…
- I 1st counted the inefficiency at pos i from 0 to i and i to N-1 then add them and take min among those additions for all i from 0 to N-1.
- Then I calculated the inefficiency with single table.
- Then I calculated the inefficiency with tables no for which there will be no argument at all.
- At last take minimum among 1 2 3
Give a review about my approach please
O(N) solution
2 Likes
My code also failed in SubTask2 1st & 2nd TC…
My code gave wrong output in these 2 cases may be TC s are like them…
9 3
1 2 3 1 2 3 4 5 6
12 3
1 2 3 4 5 6 7 8 5 6 7 8
1 Like
It seems that the Tester as well as the Editor do not want to response any query or help sought from them. Does it mean that the test cases were weak and did not reflect the correct answers. If so, we should demand for re-calculation of Ranklist and Ratings should also be updated accordingly.
Thanks.
But my code is giving correct answers for these examples.
1 Like
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) ?