Thanks brother…it was helpful.
I have done this using greedy and I got 100 marks,maybe the test cases were weak.
Here’s my approach:-
–> initially use 1 table for each person(i.e N tables for N persons) and I stored this information in a vector called ‘table’ and table.size() represents the number of table I have been using.
–> now run a loop while(table.size()>=1)
–> in each while loop iteration check whether we can merge 2 table or not, In a single loop iteration check all the possibility of merging two adjacent table and choose one which results in minimum total cost.
–> doing this we will be decreasing number of table used by one(merging 2 table into 1) in each iteration.
–> our ans will be the minimum of all the iteration.
NOTE: this version of my solution was not working when the optimal ans will consist of using exactly 2 table So i handled that separately(just dividing the whole array into two segment in all possible manner first try to divide at index 1 then 2 then 3 and so on… and choose the optimal out of those O(n) possibility).
1 Like
Can we solve this question without using dp ???
I tried but 2 testcase of subtask 2 are failed !!
Please tell me where it’s going wrong!!
https://www.codechef.com/viewsolution/36585127
1 Like
plz, anyone helps me out to find my mistake.
only one test case not passing.
https://www.codechef.com/viewsolution/36727202
Hello everyone!
I got 8 of 10 subtasks correct. Got wrong on test case 2 and 3.
So my approach was to calculate first inefficiency for one table with all members and also the overall frequency of members from each family.
Then I iterated through the list of members, adding one to a variable say NOS whenever I encountered the first member from a family which would have an argument. I iterated till i encountered the second member from a family, at which i checked whether NOS would be greater or equal than cost of a table (since its feasible to split only when no. of arguments are less than cost of adding a table). If it was less than cost of table, i continued until another such condition took place. Then whenever i found a member which is second last, i added one to NOS. And when i encountered the last member from a family, i checked whether NOS was greater than or equal to cost of table.
Any good soul could spend some time to help out?
#include <bits/stdc++.h>
using namespace std;
int main() {
long long int t,n,k,f[1000],i,fam[101],che[101],ans,no,j,flag=0;
cin>>t;
while(t--)
{
flag=0;
memset(fam,0,sizeof(fam));
memset(che,0,sizeof(che));
cin>>n>>k;
ans=k;
no=0;
for(i=0;i<n;i++)
cin>>f[i];
reverse(f,f+n);
for(i=0;i<n;i++)
fam[f[i]]++;
for(i=1;i<=100;i++)
if (fam[i]>1) ans+=fam[i];
for(i=0;i<n;i++)
{
che[f[i]]++;//cout<<no<<" "<<che[f[i]]<<" "<<fam[f[i]]<<"\n";
if (che[f[i]]==1)
{
if (fam[f[i]]==che[f[i]]+1)
no+=2;
else if (fam[f[i]]==che[f[i]])
;
else
no++;
}
else if (che[f[i]]==2)
{
if (flag==2)
{
if (fam[f[i]]==che[f[i]])
no-=2;
if (fam[f[i]]==che[f[i]]+1)
;
else no--;
flag=0; }
else if (flag==0) flag=1;
}
else if (che[f[i]]>2)
{
if (fam[f[i]]==che[f[i]]+1)
no++;
if (che[f[i]]==fam[f[i]])
{
if (flag==0) flag=1;
else if (flag==2)
{
no--;
flag=0;
}
}
}
//if (flag!=1) cout<<f[i]<<" ";
if (no>=k)
{
if (flag==1)
{for(j=1;j<=100;j++)
{fam[j]-=che[j];
if (f[i]==j) fam[j]+=1;
}
memset(che,0,sizeof(che));
ans-=no;
ans+=k;
no=0;
flag=0;
i--;
//cout<<" | ";
//cout<<i<<" "<<ans<<"\n";
}
else;
}
else
{
if (flag==1)
{flag=2;che[f[i]]--;i--;}
}
}
//cout<<che[5]<<che[1]<<che[3]<<"\n";
cout<<ans<<"\n";
}
return 0;
}
I solved it without DP and just with maps. It passed every test cases except two(2 AND 3). Can anyone help me with this? CodeChef: Practical coding for everyone
i have solved this question without using dp…just greedy approach
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
set s;
vector vect;
int count=0,ans=0;
if(k==1){
for(int i=0;i<n;i++){
count++;
s.insert(a[i]);
if(s.size()!=count){
ans++;
s.clear();
count=1;
s.insert(a[i]);
}
}
cout<<ans+1<<endl;
}
else{
map<int,int> m;
map<int,int> m1;
map<int,int> m2;
map<int,int> m3;
for(int i=0;i<n;i++){
count++;
s.insert(a[i]);
if(s.size()!=count){
ans++;
s.clear();
count=1;
s.insert(a[i]);
int hello1=k;
for(int j=0;j<i;j++){
m1[a[j]]++;
}
for(auto x:m1){
if(x.second>1)
hello1=hello1+x.second;
}
for(int j=0;j<=i;j++){
m2[a[j]]++;
}
int hello2=k,hello3=k;
for(auto x:m2){
if(x.second>1)
hello2=hello2+x.second;
}
for(int j=i+1;j<=n;j++){
m3[a[j]]++;
}
for(auto x:m3){
if(x.second>1)
hello3=hello3+x.second;
}
for(int j=i;j<n;j++){
m[a[j]]++;
}
int hello=k;
for(auto x:m){
if(x.second>1)
hello=hello+x.second;
}
vect.push_back(ans*k+hello);
vect.push_back(hello1+hello);
vect.push_back(hello2+hello3);
m.clear();
m1.clear();
m2.clear();
m3.clear();
}
}
vect.push_back((ans+1)*k);
int temp=k;
for(int i=0;i<n;i++) m[a[i]]++;
for(auto x:m){
if(x.second>1){
temp=temp+x.second;
}
}
vect.push_back(temp);
cout<<*min_element(vect.begin(),vect.end())<<endl;
}
}
return 0;
}
Happy to help!
But as testcase is weak you can solve uisng this trick;
I found that answer can be found from two calculation
- Try to arrange in one table
- Try to arrange in two table with all possibilities .
and min(1,2) will be answer.
This is my code
…
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?
Can you explain a little bit please…
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.