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

×

CHEFCBA - Editorial

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Karan Aggarwal
Editorialist: Pushkar Mishra

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given four numbers $a$, $b$, $c$, $d$, tell whether it is possible to pair them up such that $a:b$ is equal to $c:d$. We are allowed to shuffle the order of the numbers.

EXPLANATION:

We can simply try all the possible pairings. A way to model this is to cycle through all the permutations of the four numbers, pair up the first two together and the last two together. Then find the ratio of the first two and the last two; if they are equal, output "Possible", else "Impossible". Cycling through permutations can be done through functions like $next\_permutation$ in the C library or simply by recursion. Either way works since we just have 4 numbers.

A more intelligent solution is to sort the four numbers and pair up the first 2 together and the last 2 together and check their ratios. This works because ratios are symmetric.

For checking the ratio equality, we can use an simple property that if $a:b$ = $c:d$ then $a*d$ = $b*c$. This way, we can avoid dealing with floats.

Please see editorialist's/setter's program for implementation details.

COMPLEXITY:

$\mathcal{O}(1)$

SAMPLE SOLUTIONS:

Author
Tester
Editorialist
Admin

This question is marked "community wiki".

asked 23 Jul '16, 21:24

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 25 Jul '16, 00:05

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170


"Cycling through permutations can be done through functions like next_permutation in the C library or simply by recursion."

Or with 4 copypasted cycles + checking if they give a permutation (which can be done with just 4 conditions - three indices must be different and the sum of all 4 must be 0+1+2+3). In this case, it should be the simplest solution.

link

answered 25 Jul '16, 00:39

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

saikarthik12 Try this: 3 5 6 8 the answer should be impossible btw my answer was just an if condition the problem isn't that big of a deal :D

link

answered 25 Jul '16, 12:20

triplem5ds's gravatar image

5★triplem5ds
11
accept rate: 0%

can anyone plz tell the case this code fails

#include<iostream> using namespace std; #include<algorithm> #include<vector> main() { vector <int> v; for(int i=0;i<4;i++) { int temp; cin>>temp; v.push_back(temp); } sort(v.begin(),v.end()); int k1=v[1]/v[0]; int k2=v[3]/v[2]; int r1=v[1]%v[0]; int r2=v[3]%v[2]; if(k1==k2 && r1==r2) { cout << "Possible"; } else { cout<<"Impossible"; } }

link

answered 25 Jul '16, 10:24

saikarthik12's gravatar image

4★saikarthik12
1
accept rate: 0%

It will fail when a/b is a floating number.

eg - 1 2 1 4.

Answer should be impossible but your code will give possible as your ratios are 0 and 0 whereas they should be 0.2 and 0.25.

(25 Jul '16, 13:14) shubham992★

does these both a/b == c/d and a:b == c:d are equal in case of this question ?? because i was getting WA with a/b == c/d.

link

answered 25 Jul '16, 11:50

sarthak1494's gravatar image

2★sarthak1494
1
accept rate: 0%

Integer division. 10/4 and 10/5 are equal according to your submission.

(25 Jul '16, 11:55) dushsingh19954★

include<iostream>

using namespace std;

int main() { int a,b,c,d; cin>>a>>b>>c>>d; if((ab==cd) || (ac==bd) || (ad==bc)) { cout<<"Possible"<<endl;

}
else
cout<<"impossible";

} what is wrong in my code?

link

answered 27 Jul '16, 12:52

alok12345's gravatar image

0★alok12345
1
accept rate: 0%

@alok12345 "Impossible" not "impossible". Case is important though I assume this may already have been solved by you xD.

(27 Aug '18, 18:35) umangahuja14★
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:

×15,719
×1,173
×952
×59

question asked: 23 Jul '16, 21:24

question was seen: 3,195 times

last updated: 27 Jul '16, 12:52