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

×

CATSDOGS - Editorial

0
1

Practice
Contest

Author: Praveen Dhinwa
Tester: Istvan Nagy
Editorialist: Misha Chorniy

Difficulty:

Cakewalk

Pre-Requisites:

None

Problem Statement

There are $C$ cats and $D$ dogs, and $L$ legs touching the ground. Some of the cats can ride on dogs, but every dog can't have more than 2 cats on his back. Can this be true?

Explanation

Let's make some obvious observations:

  • Every cat has 4 legs.
  • Every dog has 4 legs.

If we have $X$ cats and $Y$ dogs staying on the ground then, the number of legs in the barn equal $4 * (X+Y)$. Therefore if $L$ not divisible by 4, the answer is "no".

Subtask 1 and 2

Constraints are chosen in such way that solutions with complexity $O(D+C)$ per test case can pass.

Iterate over possible numbers of the cats on Chef's dogs back $G$($G$ must be in the range between $0$ and $2*D$ due to the condition of the dog and 2 cats on his back, and not more than the total number of cats). Hence in the barn $4*(C-G+D)$ legs on the ground, if $4*(C-G+D) = L$ for some $G$, then the answer is "yes", and "no" otherwise.

Subtask 3

There is possible to solve problem with $O(1)$ solution per test case. Let $G$ number of the cats on the backs of the dogs, $0 ≤ G ≤ min(C,2*D)$

$4*(C-G)+4*D = L $, there are $C-G$ cats on the ground, therefore total number of legs = $4*(C-G)$+$4*D$

$C-G+D = L/4 $, divide both parts of the equation by $4$

$C+D-L/4 = G $, add $G-L/4$ to both parts of the equation

if $G$ will be in the range between $0$ and $2*D$ answer is "yes", and "no" otherwise.

The overall time complexity of this approach is $O(1)$ per test case.

Solution:

Setter's solution can be found here
Tester's solution can be found here

Please feel free to post comments if anything is not clear to you.

This question is marked "community wiki".

asked 18 Jan '17, 04:02

mgch's gravatar image

6★mgch
3001021
accept rate: 21%

edited 18 Jan '17, 15:02

admin's gravatar image

0★admin ♦♦
19.0k348495533


« previous123next »

include<stdio.h>

int main() { long unsigned c,d,l,t,max,min,flag,i; scanf("%lu",&t); while(t>0) { flag=0; scanf("%lu %lu %lu",&c,&d,&l); max=4c+4d; min=4*d; for(i=min;i<=max;i+=4) { if (l==i) { flag=1; } } if(flag==1) { printf("yes"); printf("\n"); } else { printf("no"); printf("\n"); } t--; }

return 0;

} 1. List item

want to know what is wrong with this code ...just it is passing only subtask 2. IS it related with time complexity...

link

answered 19 Feb '17, 12:17

alphajazz's gravatar image

3★alphajazz
1
accept rate: 0%

include<stdio.h>

int main() { long unsigned c,d,l,t,max,min,flag,i; scanf("%lu",&t); while(t>0) { flag=0; scanf("%lu %lu %lu",&c,&d,&l); max=4c+4d; min=4*d; for(i=min;i<=max;i+=4) { if (l==i) { flag=1; } } if(flag==1) { printf("yes"); printf("\n"); } else { printf("no"); printf("\n"); } t--; }

return 0;

} 1. List item

want to know what is wrong with this code ...just it is passing only subtask 2. IS it related with time complexity...

link

answered 19 Feb '17, 12:18

alphajazz's gravatar image

3★alphajazz
1
accept rate: 0%

@alpha

You are calculating min wrong. Here, have a look at my code and figure out for yourself!

my code

link

answered 19 Feb '17, 12:44

vijju123's gravatar image

5★vijju123 ♦
13.9k11240
accept rate: 19%

please can some one of you tell me where is the bug because it works for me but when I subbmit the answer is wrong. the code is in C:

typedef struct TEST test;
struct TEST{
    int c;
    int d;
    int l;
};
int stats(test te){
int i,k;
if(te.c <= te.d){
    for(i=0;i<=te.c;i++){
        k=4*(te.d) + 4*i;
        if((te.l)==k){
        printf("Yes\n");
        return 1;
        }
    }
    printf("No\n");
}else if(te.c >= 2*te.d){
    for(i=0;i<=(te.c-(te.c-2 * te.d));i++){
    k=4*(te.d) + 4*((te.c) -i);
    if((te.l)==k){
        printf("Yes\n");
        return 1;
    }
}
printf("No\n");
}else if((te.c > te.d) && (te.c < 2* te.d)){
    for(i=0;i<=te.c;i++){
        k=4*(te.d) + 4*i;
        if((te.l)==k){
            printf("Yes\n");
            return 1;
        }
    }
    printf("No\n");
}
return 0;

} main(){ int i; int T; test * t; scanf("%d",&T); t= (test )malloc(Tsizeof(test)); for(i=0;i<T;i++){ scanf("%d %d %d",&t[i].c,&t[i].d,&t[i].l); } for(i=0;i<T;i++){ stats(t[i]); } } int i; int T; test * t; scanf("%d",&T); t= (test )malloc(Tsizeof(test)); for(i=0;i<T;i++){ scanf("%d %d %d",&t[i].c,&t[i].d,&t[i].l); } for(i=0;i<T;i++){ stats(t[i]); }

}

link

answered 21 Feb '17, 16:22

magmine's gravatar image

2★magmine
1
accept rate: 0%

@magime

The constraints must be stored in long long int. In int, they will overflow and you will fail in final sub task.

Check your minimm calculation, I wasn't able to check it thoroughly in that code you posted , so please do a self check and see if its equal to what is given in editorial

(PS- min and overflow were 2 main culprits behind this problem having low accuracy rate despite easy nature)

link

answered 21 Feb '17, 18:06

vijju123's gravatar image

5★vijju123 ♦
13.9k11240
accept rate: 19%

import java.util.*; class Catsdogs{

 public static void main(String []args){

int tcase,i,j;

 Scanner sc= new Scanner(System.in);
 tcase=sc.nextInt();
 long cnt[][]=new long[tcase+1][tcase+1]; 
 String res[] = new String[tcase+1];
 for(i=0;i<tcase;i++)
 {
    for(j=0;j<3;j++)
    {
        cnt[i][j]=sc.nextLong();
    }
 }
 for(i=0;i<tcase;i++)
 {
    if((cnt[i][0]+cnt[i][1])*4==cnt[i][2])
    {
        res[i]="yes";
     }
    else if(cnt[i][1]>cnt[i][0])
    {
        res[i]="no";
    }  
    else if(cnt[i][0]>2*cnt[i][1])
    {
        res[i]="no";
    }
    else if ((cnt[i][0]+cnt[i][1])*4>cnt[i][2] && cnt[i][2]%4==0)
    {
        res[i]="yes";
    }
    else
    {
        res[i]="no";
    }
 }
 for(i=0;i<res.length-1;i++)
 {
     System.out.println(res[i]);
 }

} } This code works fine on other compiler giving required output but code chef is giving error. Please help !!

link

answered 21 Mar '17, 13:40

mihir1440's gravatar image

0★mihir1440
1
accept rate: 0%

@mihir1440 Your code throws out of index error whenever T=1

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
    at Catsdogs.main(Main.java:14)

I strongly suspect that it is due to wrong allocation of memory to cnt[][]. Please have a look at it.

link

answered 21 Mar '17, 17:51

vijju123's gravatar image

5★vijju123 ♦
13.9k11240
accept rate: 19%

What I'm doing is this:

  1. Calculate maximum value of legs possible which is max = 4*(c+d) when all cats and dogs are on the floor.
  2. Calculate minimum value of legs possible which is min = 4*(c-d) when max cats are on top of dogs.
  3. Number of legs should be positive multiples of 4.
  4. Number of legs should be between max and min.

To my surprise, it doesn't work. It gives a straight WA.

Where did I go wrong?

long long int t;
scanf("%lld", &t);

while(t--)
{
    long long int c, d, l;
    scanf("%lld %lld %lld", &c, &d, &l);

    long long int max = (c+d)*4;
    long long int min = (c-d)*4;

    if(l >= min && l <= max && l%4 == 0 && l >= 4)
        printf("yes\n");
    else
        printf("no\n");
}
return 0;

}

Any help?

PS: It works fine with the given test case!

link

answered 08 Apr '17, 17:43

mr_nair's gravatar image

1★mr_nair
21
accept rate: 0%

edited 08 Apr '17, 17:47

@mr_nair

Your calculation of min is only partially correct.

Its correct if number of cats are way more than number of dogs, but what if number of cats are less than number of dogs?

In a scenario when all cats can be on top of dogs, the min is not 4x(c-d), but its simply 4xd. Visualise it, when all cats on top of dogs, minimum legs is equal to number legs of dogs.

Your case fails at this test case-

Input
1
1 3 4
Output
yes
Expected output
no

Your min here is 4x(1-3) = -8. While practically we can see that min should be 4*3=12.

link

answered 08 Apr '17, 18:34

vijju123's gravatar image

5★vijju123 ♦
13.9k11240
accept rate: 19%

https://ideone.com/VWl7gD Can someone tell why i am failing my testcases

link

answered 08 Nov '17, 13:24

abhishek_0097's gravatar image

2★abhishek_0097
11
accept rate: 0%

toggle preview
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

Question tags:

×14,474
×1,434
×866
×126
×3

question asked: 18 Jan '17, 04:02

question was seen: 3,727 times

last updated: 29 May, 12:46