You are not logged in. Please login at www.codechef.com to post your questions!

×

DISHLIFE - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

simple

PREREQUISITES

general programming skills

PROBLEM

There are $n$ islands, and $k$ ingredients numbered from $1$ to $k$. Each island contains some ingredients, let ${ingredient}_i$ denotes the list of ingredients in $i$-th island. Chef wants to collect these ingredients from these islands. He wants to check following cases.

  • Whether it is even possible to collect the $k$ required ingredients.
    • If yes, then he wants to know whether he will need to visit all the $n$ islands for collecting these ingredients, or he can do it by visiting less than $n$ islands.

You have to identify which of these scenarios is there.


Checking whether Chef can even collect the desired $k$ ingredients or not. This is same as checking whether is there some ingredient which is not present in any island.

For each ingredient, we can maintain the number of islands it is present in. let $cnt[i]$ denote the number of islands in which the ingredient $i$ is present.

We can check whether there is some ingredient whose $cnt$ value is zero or not.

int cnt[K + 1]
for i = 1 to n:
    for j = 0 to ingredients[i].size():
        x = ingredients[i][j]
        cnt[x] += 1;
for i = 1 to k:
    if (cnt[i] == 0):
        // It means that ingredient i is not present in any of the islands.

Now, we know that it is possible to collect the $k$ ingredient. Now we should find whether Chef will need to visit all the $n$ islands for collecting these ingredients or not. If there is a ingredient $i$ which is present only in a single island, i.e. $cnt[i] = 1$, then you will have to definitely need to visit this island. Otherwise, you can skip this island, and collect the ingredients from remaining $n - 1$ islands.

// For each island, check if Chef doesn't visit this island, can he still visit collect all the ingredients from the remaining islands?
need_to_visit_all = true;
for i = 1 to n:
    can_collect_all_ingredient_without_this_island = true;
    for j = 0 to ingredients[i].size():
        x = ingredients[i][j]
        if (cnt[x] == 1):
            can_collect_all_ingredient_without_this_island = false
    if (can_collect_all_ingredient_without_this_island):
        need_to_visit_all = false;

Time complexity of this algorithm will be equal to $\text{ingredient}1.\text{size}() \, + \, \text{ingredient}2.\text{size}() + \dots +\text{ingredient}[n].\text{size}()$. For solving the final subtask, we have the constraints over sum that it will not exceed $10^6$. Hence, it will take around $10^6$ operations for answering each test case.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 15 Apr, 22:09

dpraveen's gravatar image

4★dpraveen ♦♦
2.1k52116154
accept rate: 19%

edited 19 Apr, 22:28


for all the newbies , this one solution of mine will certainly help , follow it line by line .... https://www.codechef.com/viewsolution/13277031

link

answered 20 Apr, 21:29

marshal_roxx's gravatar image

3★marshal_roxx
3756
accept rate: 4%

I request your scrutiny on this code https://www.codechef.com/viewsolution/13350172 . I would like to know areas it could be optimized in order for it to run faster and also to rid off SIGSEGV. The code runs well with the provided test cases but it fails the online judge test cases.

link

answered 18 Apr, 00:56

henrykibiwott's gravatar image

2★henrykibiwott
111
accept rate: 0%

i solved this question simply by using set. my solution https://www.codechef.com/viewsolution/13233163

link

answered 20 Apr, 20:54

pk201996's gravatar image

2★pk201996
111
accept rate: 0%

Hi, Can anyone please explain why I'm getting the last 2 cases wrong?

I implemented the same logic as in the editorial.

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

link

answered 17 Apr, 16:52

sharpcoderr's gravatar image

0★sharpcoderr
1
accept rate: 0%

While checking; if (cnt[islands[i][j]] == 1), add a break condition inside the if condition. Your solution woundn't work for this test case; n = 3, k = 4, {1,4}, {2,3}, {4}. In your case, answer would be "all" since v=3 (v==n). But, clearly it should be "some".

(17 Apr, 18:53) pratik_gadhiya4★

Here's, my very similar solution: https://www.codechef.com/viewsolution/13218833

(17 Apr, 18:55) pratik_gadhiya4★

Great, I understood. Thank you for your help!

(17 Apr, 20:23) sharpcoderr0★

Plz see my code as ...all the public cases are correct and getting wrong ans.. plz tell where you are wrong.... Link

link

answered 17 Apr, 18:47

palash7563's gravatar image

2★palash7563
153
accept rate: 0%

Links to setter's solution and tester's solution are not working, please fix this.

link

answered 17 Apr, 21:20

only4's gravatar image

3★only4
1.1k19
accept rate: 16%

there is something wrong in the last statement I see "Time complexity of this algorithm will be equal to $\text{ingredient}....." Also the setters solution and testers solution are not working, please fix it

link

answered 18 Apr, 09:34

amveg's gravatar image

2★amveg
21114
accept rate: 0%

If the input is-

1
3 3
2 1 2
1 3
2 1 3

or if it is

1
3 3
2 1 3
1 3
2 1 2

The answer in both the cases should be "some". Because for the 1st case we can skip 2nd or 3rd island and for the 2nd case we can skip 1st or 2nd island. But the judge is accepting solutions in which for the first case o/p is "some" and for the second case o/p is "all". This is the case if someone is starting from the first island and iterating over all the island one by one and checking if at any island(not the last one) all the ingredients are covered or not. But this is the wrong approach.

link

answered 18 Apr, 20:50

sajalagrawal's gravatar image

3★sajalagrawal
1
accept rate: 0%

include <stdio.h>

int main() {

int t,n,k,i,j,a[100000],b[100000][5],ch;

scanf("%d",&t);

while(t--)

{

    scanf("%d%d",&n,&k);

    for(i=0;i<k;i++)

    a[i]=0;

    ch=0;

    for(i=0;i<n;i++)

    {

        scanf("%d",&b[i][0]);

        for(j=1;j<=b[i][0];j++)

        {

            scanf("%d",&b[i][j]);

            a[b[i][j]-1]++;

        }

    }

    for(i=0;i<k;i++)

    if(a[i]==0)

    {
        ch=1;break;//impossible

    }

    if(ch==1)

    printf("sad\n");

    else//possible

    {
        for(i=0;i<n;i++)

        {
            ch=0;

            for(j=1;j<=b[i][0];j++)

          {

            if(a[b[i][j]-1]==1)//its contri matters

            {
                ch=1;break;

            }

          }

        if(ch==0)//its contri doesn't matter

        {

            printf("some\n");

            break;
        }

        }

        if(ch==1)

        printf("all\n");

    }

}
return 0;

} I dont understand why this code works(100 marks) bcoz no. of columns in array b[100000][5] which is used to

store ingredients of a particular island is of size 5 only still code works for original constraints?Why plz

explain.

link

answered 19 Apr, 12:30

code_man's gravatar image

2★code_man
1
accept rate: 0%

In my solution 2nd test case getting failed because of TLE. https://www.codechef.com/viewsolution/13274266 Please anyone let me know, how I can improve. Thanks

link

answered 20 Apr, 18:37

mahinlman's gravatar image

2★mahinlman
1
accept rate: 0%

edited 20 Apr, 18:39

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×9,879
×86
×5

Asked: 15 Apr, 22:09

Seen: 737 times

Last updated: 20 Apr, 21:29