I would very grateful if somebody points out my mistake. Here’s my solution - my solution
Well, my approach is a bit different and would like to know why this would not work.
I’m maintaining a last - table for any index. Let say, I have an element at index, I will pass both the last table(for sitting in the same table) and a new table(for new table) with the current element at index and see which of these give me the minimum solution and return this.
The code is a bit different in which I have used variables like the same table and different table values of the index+1 t help me prune the tree.
I used hashing…basically maps to store the frequency of the elments
1.Firstly I deleted the elements having 1 frequency.
2.Now we have only those elements which are capable of fighting along themselves.
3.Now I made a vector where each element represents the no of people which will be fighting less when we make a division in the main array to the right of that index.
4.Thus we have the vector of size one less than the main array (the one we got after deleting the elements having one frequency).
5.Then by simply looking at the K value we can see which index to attack…and after attacking the index we delete the elements in the main array .
6.Unless no elements left or the value of K is larger than the value of the largest element in the vector , we keep on doing that.
7.ans=k+no.of elements in the main array.then ans-=x; ans+=k;
I was looking just for this solution. Had written the code but could not figure out how to reduce the calculation of finding common family members within a given range. Thanks for your code, will help me a lot.
#include <iostream>
#include <vector>
#include <algorithm >
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
void print(vector<int> a){
for(int i = 0; i < a.size(); i++){
cout << a[i] << " ";
}
cout << endl;
}
// This function calculated the no. of tables without any conflicts
int count_separation(vector<int> guests){
unordered_map<int, int> a;
int separation = 0;
for(int i = 0; i < guests.size(); i++){
a[guests[i]]++;
if(a[guests[i+1]] > 0 || i == (guests.size() - 1)){
separation++;
a.clear();
}
}
return separation;
}
// This function counts the no. of same elements
int countFreq(vector<int> arr)
{
int num_conflicts = 0;
unordered_map<int, int> mp;
for (int i = 0; i < arr.size(); i++)
mp[arr[i]]++;
for (auto x : mp){
//cout << x.first << " " << x.second << endl;
if(x.second > 1){
num_conflicts += x.second;
}
}
cout << num_conflicts << endl;
return num_conflicts;
}
int main()
{
int test = 0;
cin >> test;
int result[test] = {0};
int c = 0;
while(test){
int n, k;
cin >> n >> k;
vector<int> guests(n);
for(int i = 0; i < n; i++){
cin >> guests[i];
}
int num_separation = count_separation(guests);
//cout << "no. of separation : " << num_separation << endl;
int no_conflicts = 0, with_conflicts = 0;
no_conflicts = num_separation * k;
with_conflicts = k + countFreq(guests);
//cout << "With conflicts : " << with_conflicts << " -- Without conflicts : " << no_conflicts << endl;
if(no_conflicts < with_conflicts){
result[c] = no_conflicts;
}
else{
result[c] = with_conflicts;
}
c++;
test--;
}
for(int i = 0; i < c; i++){
cout << result[i] <<endl;
}
return 0;
}
I tried it without dp but failed in 2 tests on subtask 2.
I did by the following logic -
1. In the count_separation function, I calculated the no. of tables needed so that there will be no disputes. I went linearly from the first element and kept the no. of times the elements came in map. And when the next element came which already had a greater than 0 frequency in the map, I increased the no. of tables needed.
2. In the other case, I put all the guests in a single table and calculated the no. of the same elements.
3. Then I calculated the total inefficiency in both cases.
This code worked for 8/10 cases.
I think that I didn’t consider the possibility of – table where there are conflicts + the table where there are no conflicts, such that these both combine to give the optimal solution. But if this is so, then the tests should have been more towards the idea of a table with conflicts + a table without conflict, both combined together to give the solution.
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;
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?