But i don’t know what is wrong.
My solution is giving me WA in 2nd subtask’s first and second cases.
CodeChef: Practical coding for everyone, I haven’t used DP
Could you please give me an example of a test case for this category.
https://www.codechef.com/viewsolution/36772778
I am also getting same let me know if u r getting test case
https://www.codechef.com/viewsolution/36472193
Its n^3 complexity code, the best I could muster but understandable (at least for me) nonetheless.
me too
time complexity should be 100 x (n^2) x (log100 for using map) = 6 x 10^8, now can anyone explain this to me that why is this dp solution is passing in 1 sec???
This code is giving Segmentation fault on my computer.
1 Like
test case please ?
maybe that is what i will have to think about
coz u can also see that it is passing all except 3 test cases
No test case. It directly crashed.
it cannot happen !! i just submit this code on codechef for this problem submission…
fyi it is cpp code
I made this in java for subtask of k=1; CodeChef: Practical coding for everyone
can someone help with test cases or logic that is wrong.
thanks 
i found where i went wrong
yeah,I was able to do it using recursion merely…Though it was exponential but I was able to realise the suitable length of array to apply recursion
1 Like
can anyone help me with this solution …it passed all the cases of subtask 1 and #5 of subtask 2
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner (System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++)
{
int n=sc.nextInt();
int k=sc.nextInt();
int ar[]=new int[n];
for(int j=0;j<n;j++)
ar[j]=sc.nextInt();
int counter[]=new int[100];
int tolerance=0;
int ineff=k;
for(int j=0;j<n;j++)
{
counter[ar[j]-1]=counter[ar[j]-1]+1;
if(counter[ar[j]-1]>1)
{
if(counter[ar[j]-1]==2)
{
tolerance+=2;
ineff+= 2;
}
else
{
tolerance++;
ineff++;
}
}
if(tolerance>=k)
{
ineff=ineff+k-tolerance;
tolerance=0;
for(int p=0;p<100;p++)
counter[p]=0;
j–;
}
}
System.out.println(ineff);
}
}
}
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.
Please help. Thanks.
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;
GOT 80% though not full percentage
https://www.codechef.com/viewsolution/36820045
2 Likes
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.
1 Like
#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.