isn’t the solution possible in O(N)??
Can someone comment on the Time Complexity of following dp solution?
https://www.codechef.com/viewsolution/36251028
Agreed, I am trying to solve a problem and those guys getting a better rank because they cheat, It’s not fair.
1 Like
Passed 9/10. Failing task 3 of subtask 2.
Check out Screencast Tutorial for this problem: Codechef - CHEFWED | Contest Screencast/Tutorial | August Challenge 2020 - YouTube
1 Like
Glad to help.
I have one question, instead of passing one index to getAns() function, I passed two indices, a start and an end and then did two recursive calls but that gives a TLE, why is it redundant to pass two indices. Can you explain?
here is my submission using greedy, as i dont know much about DP i tried solving it with greedy and got an AC.
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define mod 10000009
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
int table=0,table1=0;
cin>>n>>k;
int f[n];
for(int i=0;i<n;i++)\
cin>>f[i];
int c=1;
set<int> x;
for(int i=0;i<n;i++){
if(x.find(f[i])!=x.end()){
c++;
x.clear();
x.insert(f[i]);
}
x.insert(f[i]);
}
table=c*k;
map<int,int> m;
for(int i=0;i<n;i++)
m[f[i]]++;
for(auto it=m.begin();it!=m.end();it++){
if(it->second != 1){
table1 = table1 + it->second;
}
}
table1 = table1 + k;
for(int i=1;i<n;i++){
int first=0,second=0;
map<int,int>m1;
map<int,int>m2;
for(int j=0;j<i;j++){
m1[f[j]]++;
}
for(int j=i;j<n;j++){
m2[f[j]]++;
}
for(auto it=m1.begin();it!=m1.end();it++){
if(it->second != 1){
first = first + it->second;
}
}
first = first + k;
for(auto it1=m2.begin();it1!=m2.end();it1++){
if(it1->second != 1){
second = second + it1->second;
}
}
second = second + k;
table1 = min(table1,first+second);
m1.clear();
m2.clear();
}
cout<<min(table,table1)<<endl;
}
return 0;
}
1 Like
I did it using the concept of MCM initially then observed the Constraint after getting TLE.
I did it concept of Rod Cutting
Can someone provide test cases …I am getting tle on submission using dp …
Would you or anyone else please give me the Test Case for Sub-task 2, Task# 2 with the answer or please tell me where is the problem in my code as given in the following link:
I have one question, instead of passing one index to getAns() function, I passed two indices, a start and an end and then did two recursive calls but that gives a TLE, why is it redundant to pass two indices. Can you explain?
No not at all, unless you share your code😁
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):
dp.append(k+dp[i-1])
dic={}
c=0
for j in range(i,0,-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-1]+k+c)
print(dp[-1])
can someone tell me why my code is not giving the correct answer in all the test cases?its showing WA.
I found this one to be easier than the KMP problem, since I got a bunch of annoying WAs for a logical greedy.
#include <iostream>
#include <vector>
#include <cstdio>
#include <set>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>
using namespace std;
int dp[1001];
int a[1001];
int tot_sum[1001][101];
int tot_res[1001][1001];
int main(){
int T;
cin >> T;
while(T--){
int N, K;
cin >> N >> K;
int mx_fi = 0;
for(int i = 0; i < N; i++){
cin >> a[i];
mx_fi = max(mx_fi, a[i]);
}
for(int i = 0; i < N; i++){
dp[i] = 1000009;
}
for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){ tot_res[i][j]=0;}}
for(int i = 0; i < N; i++){for(int j = 1; j <= mx_fi; j++){tot_sum[i][j]=0;}}
for(int i = 1; i <= mx_fi; i++){
tot_sum[0][i] = (a[0] == i ? 1 : 0);
for(int j = 1; j < N; j++){
tot_sum[j][i] = tot_sum[j-1][i] + (a[j] == i);
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
for(int k = 1; k <= mx_fi; k++){
if(j<i){
continue;
}
int amt = 0;
if(i-1<0){
amt = tot_sum[j][k]==1?0:tot_sum[j][k];
} else {
amt = (tot_sum[j][k] - tot_sum[i-1][k]) == 1 ? 0 : (tot_sum[j][k] - tot_sum[i-1][k]);
}
tot_res[i][j] += amt;
}
}
}
dp[0] = K;
for(int i = 1; i < N; i++){
for(int j = 0; j < i; j++){
dp[i] = min(dp[i], dp[j] + K + tot_res[j+1][i]);
}
dp[i] = min(dp[i], K + tot_res[0][i]);
}
cout << dp[N-1] << endl;
}
}
taking sums along prefixes optimizes overall solution.
please!!explain your logic.
Try this test case:
1
6 4
1 2 3 4 5 1 2 2 3
Output Should be 10.
What’s Your Output?
It should be
1
9 4
1 2 3 4 5 1 2 2 3
Ans should be 10
assume 1 guest sits in one table(n guests on n tables) find the answer for it ,then assume 2 guests sit on one table(n guests on n/2 tables) find answer for it … keep doing this uptill n guests sit on one table and keep track of the minimum inefficiency you can do the same from back of the array.
1 Like