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.
Here also my code gives output = 22.
I solved this question without DP, my approach is very different
So were the testcases weak?
Here’s my submission CodeChef: Practical coding for everyone
Firstly, the idea of the state is that if we consider up to some prefix i, we can get an optimal answer by asking the question of “if i start a new sequence at this point and continue onward, will my answer be improved”
This implies a state of: dp[i] = max( j <= i : dp[j] + (number of numbers which recur in a[j+1:i])).
(by number of numbers which recur, i mean that for example in the array (3,3,3,4,4), there are 5 repetitions, since 3 recurs 3 times and 4 recurs twice)
Of course, we could solve this with a brute force and simply find that value, but that will give TLE. Therefore, we optimize with some precomputation and use some 2 dimensional prefix sums to cache the values for us, giving a resultant O(N^2) complexity.
Sorry for late reply, also!
1 Like
mine is 9,
you can have only one table
incov = 4 +1+3+1
what should be the ans for this tc:
5 2
3 5 4 5 1
mine output is 3, all guest on one table
No the ans is not 3 but it’s 4 ( two 5 and one cost of table) -> (2 + 2) -> 4
OK, let us consider the test cases were not weak and gave wrong answer as per tester’s solution. But I don’t understand, is it out of policy to provide the test cases (in question/doubt) with their respective answers even after completion of the competition? I think not so. It will enable the learners to know their faults/mistakes. Isn’t it?
I had just wanted to know any one test case where my code fails, but nobody till now can provide me the same.
When two persons of a same family involved in argument, the total inefficiency increases by 2 and not by 1(as per given conditions).
Can anyone please tell me a test case which is failing my code.
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
void solve(ll *arr, ll n, ll k, ll maximum){
ll dp[maximum + 1], ans = k;
memset(dp, 0, sizeof(dp));
for(ll i = 0; i < n; i++){
if(dp[arr[i]] == 0){
dp[arr[i]]++;
continue;
}
else{
ll tempAns1 = dp[arr[i]] == 1 ? ans + 2 : ans + 1;
ll tempAns2 = ans + k;
if(tempAns1 < tempAns2){
dp[arr[i]]++;
ans = tempAns1;
}
else{
ans = tempAns2;
memset(dp, 0, sizeof(dp));
dp[arr[i]]++;
}
}
}
cout<<ans<<endl;
}
int main(){
ll t;
cin>>t;
while(t--){
ll n, k;
cin>>n>>k;
ll arr[n], maximum = INT_MIN;
for(ll i = 0; i < n; i++){
cin>>arr[i];
maximum = max(maximum, arr[i]);
}
solve(arr, n, k, maximum);
}
}
Thanks in advance 
No Check Once,You are calculating conflicts wrong.