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

×

# CATSDOGS - Editorial

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

Cakewalk

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.

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

6★mgch
210616
accept rate: 12%

18.2k347492525

 1 can somebody upvote my answer I need to ask a question and needed atleast 3 karma for that? help is appreciated.thanks answered 21 Feb '17, 17:02 32●1 accept rate: 0%
 0 import java.util.Scanner; / * @author Ashutosh / class CATSDOGS { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int i, cats=0, dogs=0, legs=0, min=0, max=0; int nTestCases = Integer.parseInt(sc.nextLine()); String[] answer = new String[nTestCases]; sc.reset(); for (i = 0; i < nTestCases; i++) { String values[] = sc.nextLine().split(" "); cats = Integer.parseInt(values[0]); dogs = Integer.parseInt(values[1]); legs = Integer.parseInt(values[2]); min = cats - (dogs * 2) < 0 ? 0 : cats - (dogs * 2); max = dogs + cats; if (validate(min, max, legs)) { answer[i] = "yes"; } else { answer[i] = "no"; } } for (String o : answer) { System.out.println(o); } } public static boolean validate(int min, int max, int legs) { return ((legs % 4 == 0) && (legs >= min * 4 && legs <= max * 4)); }  } Can anyone please check what's wrong in this code. I got 0 marks, but i am not getting where I am wrong. Can anyone please guide me. answered 25 Jan '17, 13:22 1 accept rate: 0% You've calculated wrong min, learn to debug your code. ll mnl=d4; if(c>d2) mnl=(ll)((ll)(c-(ll)(d2))4 + mnl); (25 Jan '17, 19:06)
 0 Please try to insert comments as such to tell what exactly you are doing in the code. Here, check my code in C https://www.codechef.com/viewsolution/12439335  #include int main(void) { int t,a0; scanf("%d",&t); for( a0=0;a0=c) min=4*d; else if (2*d= min && l<=4*(d+c) && l%4==0) printf ("yes\n"); else printf ("no\n");   } return 0; }  I am unable to get why you used "String[] answer = new String[nTestCases];" Was it to store and print answer? Here is the quick algo I used. First we check the number of cats and dogs. Now we need to find which is less. If number of cats is less than number of dogs, situations may vary from all cats on top of dogs to none of the cats on top of dogs. In this case, the counting is true if the number of legs is between 4number of dogs and 4number of (Dogs+Cats) AND is divisible by 4. In case number of cats is more than dogs, we should observe two things- If number of cats is less than 2number of dogs (i.e. all cats can still ride on top of dogs) we Follow as in step 1. However, if cats are more than 2dogs, we find minimum number of cats which will remain on ground first (assuming all dogs carry 2 cats[we are finding minimum]). This is clearly cats-2 dogs. Eg- Dogs -4, Cats =10. Then Dogs can carry 8 cats, and 10-8=2 will remain. Now the MINIMUM number of legs is 4number of Dogs + minimum number of cats, the maximum again is number of cats+dogs. The number L should be divisible by 4. NOW THE TRICKY PART- The number of C, L and D in final subtast are REALLY LARGE. DO NOT...I REPEAT DO NOT USE INT TO STORE THESE. YOU WILL GET AN OVERFLOW!!! I used long long int in C. Feel free to ask doubts/get back to me. :) answered 25 Jan '17, 13:42 12.1k●1●3●19 accept rate: 18%
 0 @vijju123 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int nTestCases = Integer.parseInt(sc.nextLine()); while (--nTestCases != 0) { Long cats, dogs, legs, min; String values[] = sc.nextLine().split(" "); cats = Long.parseLong(values[0]); dogs = Long.parseLong(values[1]); legs = Long.parseLong(values[2]); min = cats - (dogs * 2) > 0 ? ((cats - (dogs * 2)) + dogs) * 4 : dogs * 4; if (legs < min) { System.out.println("no"); } else if (legs % 4 != 0) { System.out.println("no"); } else if (legs >= min && legs % 4 == 0 && legs <= 4 * (dogs + cats)) { System.out.println("yes"); } else { System.out.println("no"); } } }  } See this is also, giving error. answered 25 Jan '17, 16:12 1 accept rate: 0%
 0 Firstly, I want to ask that did you try running it in "Code, Cmpile and Run" Feature of codechef? If not, then I strongly advise you to! Cause online IDEs are very much different in handling exceptions and etc. Also, I run your code, and the first glaring error found was that "while (--nTestCases != 0)" PS, its NOT same as doing it in for loop. Here it first REDUCES the value and THEN compares. So if the number of test cases are 3, then it will execute loop as- (--3) !=0 ==> 2!=0 Then 1!=0 in next iteration Then in final iteration 0!=0 will be false. Note that your program iterated only twice, instead of 3 as required by the test cases. Suggested fixes : 1. Use a for loop. OR 2. try (t-- !=0) or simply (t--) since when it reaches 0, loop assumes false. Secondly, check for large numbers. In Code, Compile and Run feature, check by inputting the max input (10^9 ) and CHECK the values of C, L and D by asking program to print. In my case, due to overflow I got some weird negative value like -168734 &etc. That's the second catch in this problem. Edit- Thirdly, if as I suspect, your code suffers from - "Exception in thread "main" java.util.NoSuchElementException: No line found at java.util.Scanner.nextLine(Scanner.java:1540) at Main.main(Main.java:9) " Then do check here- http://stackoverflow.com/questions/7209110/java-util-nosuchelementexception-no-line-found The error is due to, (as quoted by them),- You're calling nextLine() and it's throwing an exception when there's no line, exactly as the javadoc describes. It will never return null My suggestion- I always used int a=sc.nextInt(); etc. Try this one, I am sure it will work ^^ Try the three of these and let me know. If error still occurs, we will have a closer look. :) Cheers, have a nice day ^^ answered 25 Jan '17, 16:27 12.1k●1●3●19 accept rate: 18%
 0 enter code here#include  void getInput (void); void runtests (long long int Cats, long long int Dogs, long long int Legs); int main (void) { getInput(); return 0; } void getInput (void) { long long int Tests; long long int Cats; long long int Dogs; long long int Legs; scanf ("%lld", &Tests); while (Tests--) { scanf("%lld", &Cats); scanf("%lld", &Dogs); scanf("%lld", &Legs); runtests(Cats, Dogs, Legs); } return;  } void runtests (long long int Cats, long long int Dogs, long long int Legs) { long long int catsOnDogs = 0; if ((Legs % 4) != 0) { printf ("no\n"); return; } else { while ((catsOnDogs <= Cats) && (catsOnDogs <= (2 * Dogs))) { if ((4 * (Cats - catsOnDogs) + (4 * Dogs)) == Legs) { printf("yes\n"); return; } else { catsOnDogs++; } } printf ("no\n"); return; } return;  } this code is failing parts 1 and 3 of subtest three and I can't for the life of me figure out why. Can anyone help? It's probably something stupid I'm just not seeing. answered 27 Jan '17, 10:59 0★oddant1 1 accept rate: 0% Not sure why it posted in such a weird format sorry about that (27 Jan '17, 11:00) oddant10★ nevermind I got it (27 Jan '17, 11:17) oddant10★
 0 @oddant1 its in this weird way because you pasted it beside "enter your code" . What you have to do is, copy your code, select "enter your code" and then paste (overwriting "enter your code" with your code) and it'd be properly formatted. As for your code- Why its failing- Firstly, please give a submission link if possible, or give more details. You are NOT suffering from wrong answer, you are suffering from TIME OUT (program is taking TOO long) and its obvious why. Look dear, test cases can vary from 1 to 10,000. And number of cats and dogs till 10^9. Problem with your code is that, while it accurately tells about number of cats on dogs etc, its not required. You simply need to tell if the counting of legs is possible or not, and NOT the configuration (like, how many dogs were on cats and stuff). Analyse your while loop which calculates cats on dogs. lets say, cats are 25000, and dogs are 10,000. Now, until you get ((4 * (Cats - catsOnDogs) + (4 * Dogs)) == Legs) true, (which in worst case, will be false), your loop will execute. In worse case, it will execute 20,000 times. If numbers are bigger, it may have to execute 10, 100 or thousand times more!! Now repeat this for all 10,000 test cases. Automatically, number of loop executions increase so much, that the program takes more than allotted time to run. How to fix? The problem is possible by direct computation. First, find minimum number of legs possible (assume 2 cats on dog) and maximum (4*(cats+dogs)) Minimum Legs might get tricky if cats are more than dogs. Eg- cats=10, dogs=2, legs =36 4 cats may climb on dog. ==>cats=6, dogs=2, total 8. Minimum Legs=8*4=32. Now if 1 cat is NOT on dog, we get 36. If 2 cats and 2 dogs, minimum is obviously 2 (number of dogs- assuming all cats on dogs). Minimum legs = 2*4=8 Now we have maximum and minimum. Now see, for EVERY CAT NOT ON DOG, we can add 4 to minimum and get new count of legs. What I mean to say is that, by this statement we can clearly see that legs = minimum +4*k (where k is an integer) [incase you still didn't understand. In minimum we assumed all cats on dogs. Lets say 1 cat is not on dog, leg count increases by 4. If 2 cats not on 4, leg count increases by 8 and so on. Meaning, there is a gap of 4 between successive valid leg counts. Also, since min and max legs are divisible by 4, the leg count is divisible by 4) Now, how to determine if leg count is correct or not? Firstly, it must lie between minimum and maximum (BOTH INCLUSIVE) Then, it MUST be divisible by 4. (eg, min-32 and max =56. Then all leg counts like 32,36,40,44..56 are valid.) In case you face any problem, do get back to me! Hope it helps! Cheers ^_^ answered 27 Jan '17, 11:27 12.1k●1●3●19 accept rate: 18%
 0 int main() { long long int c,d,l,max,min; int t,i;  scanf("%d",&t); for(i=1;i<=t;i++) { scanf("%Ld%Ld%Ld",&c,&d,&l); max=4*c+4*d; if(c<=2*d) { min=4*d; } else min=4*d+4*(c%(2*d)); if(l<=max && l>=min && (l%4==0)) { printf("Yes\n"); } else printf("No\n");  } } answered 27 Jan '17, 19:45 1 accept rate: 0%
 0 @gursheesh_sing Pls check your print statements. The question asked to print "yes" or "no" and your program is printing "Yes" and "No" (Y and N in capital!!). It will result in the answer being marked wrong by the online judge. I hope it helped! ^_^ answered 27 Jan '17, 19:54 12.1k●1●3●19 accept rate: 18%

# 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...

answered 19 Feb '17, 12:17

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

answered 19 Feb '17, 12:18

1
accept rate: 0%

 0 @alpha You are calculating min wrong. Here, have a look at my code and figure out for yourself! my code answered 19 Feb '17, 12:44 12.1k●1●3●19 accept rate: 18%
 0 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
 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) answered 21 Feb '17, 18:06 12.1k●1●3●19 accept rate: 18%
 0 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;icnt[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
 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. answered 21 Mar '17, 17:51 12.1k●1●3●19 accept rate: 18%
 0 What I'm doing is this: Calculate maximum value of legs possible which is max = 4*(c+d) when all cats and dogs are on the floor. Calculate minimum value of legs possible which is min = 4*(c-d) when max cats are on top of dogs. Number of legs should be positive multiples of 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! answered 08 Apr '17, 17:43 1★mr_nair 1●1 accept rate: 0%
 0 @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. answered 08 Apr '17, 18:34 12.1k●1●3●19 accept rate: 18%
 0 https://ideone.com/VWl7gD Can someone tell why i am failing my testcases answered 08 Nov '17, 13:24 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×13,349
×1,270
×818
×124
×3

question asked: 18 Jan '17, 04:02

question was seen: 3,158 times

last updated: 08 Apr '17, 18:34