RESCALC - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Andrii
Tester: Praveen Dhinwa
Editorialist: Ajay K. Verma

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc, Basic maths.

PROBLEM:

For a given list, the score is defined as the sum of size of the list and an additional number which could be 0, 1, 2, or 4 depending of whether the list has fewer than 4 unique elements, exactly 4 unique elements, exactly 5 elements or exactly 6 unique elements. Given a collection of lists, find the list with highest score, or indicate if there is a tie.

QUICK EXPLANATION:

Compute the score of each list, and return the one with the highest score, or indicate that there is a tie.

EXPLANATION:

In order to solve this problem, one only needs to compute the score of a list efficiently. If we can do so, then the rest of the problem is easy. Compute the score of all lists, and if there is a single list with the highest score, returns its id. On the other hand, if there are multiple lists with the highest score, then indicate that there is a tie.

The score of a list is the sum of its size and an additional number, which depends on the number of unique elements in the list. Since size of a list is easily computable, we only need to compute the number of unique elements in the list.

One could use a set to compute the number of unique elements in the list. However, since all the number are in the range [1, 6], we can use an integer to represent the set of elements in the list.

int CountUnique(vector v) {
  int signature = 0;
  for (int x : v) {
    signature |= (1 << x);
  }
  return __builtin_popcount(signature);
}

For the list we use an integer signature such that the i-th bit of signature is set iff the integer i is in the input list. In order to count the number of unique elements in the list, one only needs to count the number of bits in signature which are set to 1. This can be done using the __builtin_pop_count() function. One could also precompute these values, and use them because the in this problem the signature will always lie in the range [1, 127].

TIME COMPLEXITY:

O (N), where N is the sum of lengths of all lists.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

1 Like
2

This editorial is not good. It should explain it in an easy way.

4 Likes
3

solution

approach:

type is an array storing the count of 6 type of cookies. sort it.

points gained by that person will be 2*type[0]+type[1]+type[2]+number of cookies,c[i].

4

complex editorial!
I understand that this problem is above my level, but then this editorial is way way above. It doesnt explain the main part in depth.
can someone point to a better and understandable version?

5

Can anyone Help me! My solution is working for only 20pnts.
https://www.codechef.com/viewsolution/11459490

6

Simplest approach:

1.) Store the frequencies of the cookies.

2.) Sort it

3.) Take the smallest, subtract from all and multiply by 4. This will make all pairs of 6.

4.) Do the 3rd step for 2 more times changing the value as specified. (for pairs of 5 and 4)

5.) Just add the number of cookies to your final answer and you are done!

PS: Just check for a tie and Chef’s winning!

AC Solution with above approach:
https://www.codechef.com/viewsolution/11305714

1 Like
7

This editorial doesn’t explain the main part. It explains till the part where we have the number of unique elements in the list. But there are steps afterwards also like calculating the number of boxes possible of different types. That part isn’t explained in this editorial.

8

I did the same. https://www.codechef.com/viewsolution/11395816

9

@w_white could you pls explain how u are calculating the points gained?

10

got it now.

11

can anyone tell me what is wrong with my solution… https://www.codechef.com/viewsolution/11464797
i got only 20 points despite numerous attempts.

12

Hi, From the editorial I can understand the way to find the number of unique elements. Now I’ve a questions after that.

  1. How do I find the distinct number of sets out of it? As I need to remove those elements from the list whose calculations has been done using the function CountUnique(). Am I right? Suppose I’ve the following elements in the list 123456123456. So the function would return me 6 as unique elements but then I would need 6 twice so that I know there could be two sets of 6 elements each. So I need to remove the first 6 elements before passing the list again to CountUnique.

Please if someone can explain this part, I would be very thankful.

13

Hey guys,please help me. I am getting WA for 2nd subtask.
Here’s link to my solution >> https://www.codechef.com/viewsolution/11314437

1 Like
14

I made set …and use size() of set to calculate extra points and then add it to total no of cookies. but i am getting WA in subtask 2 can anyone tell me why?

15

actually you took the question in wrong way.there can be multiple boxes of 4,5,6
suppose there are 20 boxes
4 2 2 4 1 2 3 4 5 6 1 2 4 3 5 6 1 2 3 4
then there will be :
2 box of 6,1 box of 4
and rest 4 2 2 4 as extra of which we cannot make anymore boxes so in this case answer will be
20+24+41=29
hope this helps :slight_smile:

1 Like
16

@naksh9619 u have cleared my doubt thanks for that…

17

Thx… @naksh9619

18

#include<stdio.h>
int main()
{
int t,k,i,j,c,n,n1,c1,c2,b[6],m,max,f,index;
scanf("%d",&t);
for(i=0;i<t;i++)
{
c2=f=0;
scanf("%d",&n);
for(k=0;k<n;k++)
{
c=0;
scanf("%d",&n1);
int a[n1];
c1=n1;
for(j=0;j<n1;j++)
scanf("%d", &a[j]);
for(j=1;j<=6;j++)
{
for(m=0;m<n1;m++)
{
if(a[m]==j)
{
c++;
break;
}
}
}
if(c<=3)
c=c;
else if(c==4)
c1++;
else if(c==5)
c1+=2;
if(c==6)
c1+=4;
b[c2]=c1;
c2++;
}

    max=b[0];
    for(m=0;m<c2;m++)
    {
        if(f==1)
            break;
        for(k=m+1;k<c2;k++)
        {
                if(b[m]==b[k])
                {
                    printf("tie\n");
                    f=1;
                    break;
                }
        }
    }
    index=0;
    if(f==0)
    {
        for(m=1;m<c2;m++)
        {
            if(max<b[m])
            {
                index=m+1;
            }
        }
         if(index==0)
                printf("chef\n");
         else
            printf("%d\n",index);
    }
}
return 0;

}

//Can someone tell me the issue with this code.

19

@admin the xml file have some errors, which prevents from seeing author and tester’s solutions.