CHEFWED - Editorial

editorial
, , , , , ,
25

You were so close :open_mouth:

26

https://www.codechef.com/viewsolution/36308363

This is my solution (JAVA). I didn’t use DP, but more of a brute force approach. Got AC✔ (100 pts) .

@rishup_nitdgp Can you review my approach?

2 Likes
27

But i don’t know what is wrong.

28

Without use of dp, i did it by hashing only
https://www.codechef.com/viewsolution/36753378

3 Likes
29

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.

30

https://www.codechef.com/viewsolution/36772778

I am also getting same let me know if u r getting test case

31

https://www.codechef.com/viewsolution/36472193

Its n^3 complexity code, the best I could muster but understandable (at least for me) nonetheless.

33

me too

34

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???

35

This code is giving Segmentation fault on my computer.

1 Like
36

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

37

No test case. It directly crashed.

38

it cannot happen !! i just submit this code on codechef for this problem submission…
fyi it is cpp code

39

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.

40

thanks :grin: i found where i went wrong

41

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
42

Naive approach here

1 Like
43

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);
}
}
}

44

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.

45

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