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

×

SEBIHWY - Editorial

PROBLEM LINK:

Contest
Practice

Author: Istvan Nagy
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Cakewalk

PREREQUISITES:

Ad hoc

PROBLEM:

Sebi and his father are in a car, and they want to guess the speed of another car. Both cars travel at a constant speed, and the second is faster than the first car. There are markers on the highway every 50 meters.

They start a timer at the instant at which their car and the other car are parallel to each other. After $T$ seconds, they observe that both the cars are next to some markers and the number of markers between them is $D - 1$. The speed of Sebi's father's car is $S$.

Sebi and his father guess that the speed is $SG$ and $FG$, respectively. Determine who has the better guess.

QUICK EXPLANATION:

The correct speed of the other car is $S_{\text{other}} := S + \frac{180D}{T}$, in the right units. (Be careful: This speed isn't necessarily an integer.) Thus:

  • If $|SG - S_{\text{other}}| < |FG - S_{\text{other}}|$, the answer is SEBI.
  • If $|SG - S_{\text{other}}| > |FG - S_{\text{other}}|$, the answer is FATHER.
  • If $|SG - S_{\text{other}}| = |FG - S_{\text{other}}|$, the answer is DRAW.

EXPLANATION:

To answer the problem, we need to compute the speed of the other car exactly. Let's denote that speed by $S_{\text{other}}$, in kph. If we can do this, then answering the problem boils down to computing which one has the "better guess": we compute the "error" of Sebi's and his father's guess as:

  • $S_{\text{err}} = |SG - S_{\text{other}}|$
  • $F_{\text{err}} = |FG - S_{\text{other}}|$

Then:

  • If $S_{\text{err}} < F_{\text{err}}$, the answer is SEBI.
  • If $S_{\text{err}} > F_{\text{err}}$, the answer is FATHER.
  • If $S_{\text{err}} = F_{\text{err}}$, the answer is DRAW.

Computing $S_{\text{other}}$

We know how fast the first car travels, and that the second car is faster. Thus, we only need to know exactly how much faster the second car is than the first.

They start out in the same place, and then after $T$ seconds, they end up next to some markers. Since there are $D - 1$ markers between them, it means that after $T$ seconds, the cars are $50D$ meters away from each other. But the speeds of the cars are constant, which means this completely determines how much faster the second one is. Specifically, the second one is exactly $\frac{50D}{T}$ meters per second faster than the first!

Using this, and the fact that the first car has speed $S$ kph, we can simply add them to compute the speed of the second car, $S_{\text{other}}$. But we can't simply add them, because they are in different units! In order to add them properly and compare with $SG$ and $FG$, we need to convert $\frac{50D}{T}$ meters per second into kph. This can be done as follows:

$$\frac{\text{$50D$ m}}{\text{$T$ sec}} = \frac{\text{$50D$ m}}{\text{$T$ sec}} \frac{\text{$60$ sec}}{\text{$1$ min}} \frac{\text{$60$ min}}{\text{$1$ hr}} \frac{\text{$1$ km}}{\text{$1000$ m}} = \frac{\text{$180D$ km}}{\text{$T$ hr}}$$

This means that the second car is exactly $S_{\text{other}} := S + \frac{180D}{T}$ kph.

Here's an implementation: (in Python 3)

from fractions import Fraction as F
def solve():
    s, sg, fg, d, t = map(int, input().strip().split())
    actual = s + F(d*50*60*60, t*1000)
    sdist = abs(sg - actual)
    fdist = abs(fg - actual)
    return 'SEBI' if sdist < fdist else 'FATHER' if sdist > fdist else 'DRAW'


for cas in range(int(input())):
    print(solve())

Other possible problems

Here are a few possible bugs:

  • We need to divide $\frac{180D}{T}$ exactly. This means the data type for $S_{\text{other}}$ should not be an integer. You could use, for example, float or double. (The solution above uses fractions.) An alternative is to scale the speeds by $T$, so that they all become integers.
  • Even if you use a double, you might still get an issue if you write your code as follows: double S_other = 180*D / T; This is because even though S_other is a double, D and T might not be, so 180 * D / T might round off unexpectedly. To avoid this, you can

    • declare D and T to be doubles, or
    • use casting ((double) 180 * D / T), or
    • simply write it as 180.0 * D / T. Note that D / T * 180.0 might still fail. (Why?)

Time Complexity:

$O(1)$

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 20 Nov '16, 21:44

kevinsogo's gravatar image

7★kevinsogo
1.7k583142
accept rate: 11%

edited 21 Nov '16, 00:01

admin's gravatar image

0★admin ♦♦
19.6k349497539

Can someone tell me why I'm getting a WA? :( :(

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

(21 Nov '16, 00:12) codedecode01115★

using std::abs might help see my ans below for detail.

https://discuss.codechef.com/questions/87910/sebihwy-editorial/87954

(21 Nov '16, 12:48) diveshuttam3★

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

what was wrong with this solution then???

Simple roundoff to this easy qn killed my 1 n half hour.

link

answered 21 Nov '16, 00:13

kanha95's gravatar image

1★kanha95
1
accept rate: 0%

Please have a look and tell me where I am going wrong. https://www.codechef.com/viewsolution/12127928

link

answered 21 Nov '16, 01:05

qruiger_116's gravatar image

3★qruiger_116
1918
accept rate: 7%

try using the expression given in the editorial.for details my ans below.

(21 Nov '16, 13:06) diveshuttam3★

but, it's the same thing, the expression given in the editorial is just more simplified than what I've written, it should give AC in both the cases. Still can't figure out where I went wrong...

(21 Nov '16, 14:25) qruiger_1163★

please read the ans below when you divide first you lose precision as there are only say 19 digits after the decimal. Moreover expression d/1000/tx50x3600 yields wrong ans but dx3600x50/t/1000 yields right answer. You should check the links in my answer. I tried almost 40 diff. solutions to check this out.

(21 Nov '16, 14:50) diveshuttam3★
2

So lets look this sample with your code

1 7 213 221 7 6

int this case the other car sped is 217, your solution calculates with floats

the other car speed is in your code oc = 216.99998

diff1 : 3.9999847 diff2 : 4.0000153

if I change the floats to double in your code : oc will be = 216.99999999999997

diff1: 3.9999999999999716 diff2 : 4.0000000000000284

so you can see it also contains precision error.

Of course you can correct your solution if ABS(diff1 - diff2) < epsilon it should be consider equal. For your solution e.g. epsilon=1e-7 would be a sufficient.

(21 Nov '16, 15:33) iscsi6★

Ohkay. Thank you @diveshuttam and @iscsi for your explanations. Much Appreciated.

(22 Nov '16, 15:08) qruiger_1163★

@all Alright the question is really interesting a cakewalk that makes you realize that there is difference between real life and computer world;In real world we have infinite precision of floats. But not so in computer I had seen a cs50 video which talks about this 2 months back i didn't know that it would come this handy though i was not able to find the video you can check this link and this link.The editorial also mentions this part when they say (Be careful: This speed isn't necessarily an integer). Though the question mentions of converting to double carefully will give AC but i don't think so moreover the setter's solution compares distances(integers) rather than speed.Now interesting part about integers is that they are precise.
I hope that this is only the reason ; still trying to get it work the old way as some solutions of others in c work that way.will update this answer soon.

UPDATE: So i was partially correct. check my answer on this question for details. Summary:
Two of the possible mistakes:
1)using division first instead of multiplication and loosing precision.
2)using abs instead of std::abs.(Unintentionally you may end up in using abs defined only for integers; there are two abs() functions check here) using namespace std is important for solutions in c++.ESP if you use <bits/stdc++.h>.

In c one should use fabs() for this to work.

Best way is to compare distances as in setters solution which are integers and precise.

link

answered 21 Nov '16, 01:54

diveshuttam's gravatar image

3★diveshuttam
53718
accept rate: 27%

edited 22 Nov '16, 14:35

Please anyone help me out to find the error, it was showing WA https://www.codechef.com/viewsolution/12126045

link

answered 21 Nov '16, 02:22

utkarshdeepak's gravatar image

3★utkarshdeepak
1
accept rate: 0%

can anyone please say why is it showing WA :( https://www.codechef.com/viewsolution/12126773

link

answered 21 Nov '16, 02:46

jaideeppyne's gravatar image

5★jaideeppyne
2616
accept rate: 3%

try using fabs. and simplifying the expression

(21 Nov '16, 13:09) diveshuttam3★

I hope this will answer a some of you getting wrong answer. I had the same problem as most of the guys here. Getting wrong answer when I checked it like a thousand times. Finally during the last half an hour I tried something without any hope of it working but it fetched me AC. What I did was to first check for "DRAW" that is the equals condition rather than "FATHER" or "SEBI" and that is it.

link

answered 21 Nov '16, 02:54

g123's gravatar image

4★g123
112
accept rate: 0%

edited 21 Nov '16, 03:05

adding a point the answer of @iscsi it is not the matter of float here. As below is @qruiger_116 's solution with using float. Got ac by just changing the expression .so in general float and double are the cause of such problems; it is not so here. Check this out https://www.codechef.com/viewsolution/12129700
here the point is that you may lose precisision by dividing first as no. of decimal points is fixed. For more details check the links in my answer below

link

answered 21 Nov '16, 16:54

diveshuttam's gravatar image

3★diveshuttam
53718
accept rate: 27%

https://www.codechef.com/viewsolution/12247224 kindly tell me what is wrong in this ans

link
This answer is marked "community wiki".

answered 10 Dec '16, 20:47

hs_123's gravatar image

3★hs_123
1
accept rate: 0%

@hs_123 the distance between the two cars in km can be in decimal, example: 1500 metres=1.5 km. Please read the editorial, it is explicitly mentioned to use typecasting or declare as float or double.Anyway, I changed the datatype to float and used fabs instead of abs in your code and got AC. This is the link to your updated code. https://www.codechef.com/viewsolution/12272086

link

answered 14 Dec '16, 10:40

qruiger_116's gravatar image

3★qruiger_116
1918
accept rate: 7%

whats wrong in this

`#include <iostream>

include<stdlib.h>

using namespace std;

int main() {

double t1,s1,s2,d,t,s; double a; std::cin>>t1; t1--; do{ std::cin>>s>>s1>>s2>>d>>t;

  a=d*3.6*50/t;
  a=a+s;
  if(abs(a-s1)<abs(a-s2))
  std::cout<<"SEBI"<<endl;
  if(abs(a-s1)>abs(a-s2))
  std::cout<<"FATHER"<<endl;
  if(abs(a-s1)==abs(a-s2))
  std::cout<<"DRAW"<<endl;

}while(t1--);

// your code goes here
return 0;

} `

link

answered 24 Dec '16, 00:31

p_k_priyanka's gravatar image

2★p_k_priyanka
1
accept rate: 0%

include <iostream>

include <bits stdc++.h="">

using namespace std;

int main() { double tc,s,sg,fg,d,t; double sp=0.00,d1=0.00,t1=0.00; cin>>tc; while(tc--) { cin>>s>>sg>>fg>>d>>t; d1=(double)(d50/1000); //distance in km t1=(double)(t/60); //time in min sp=(double)(d160/t1); //actual speed of other car

    sp=(double)(sp+s);
  if((abs)(sg-sp)==(abs)(fg-sp))
  cout<<"DRAW"<<endl;
    else if((abs)(sg-sp)<(abs)(fg-sp))
    cout<<"SEBI"<<endl;
    else 
    cout<<"FATHER"<<endl;
}
return 0;

} please tell me what is wrong in this code?.....Its giving me wrong answer

link

answered 25 Dec '16, 14:45

piyush_97's gravatar image

3★piyush_97
11
accept rate: 0%

//here is simple C++ code

include<bits stdc++.h="">

using namespace std; int main() { int t; cin>>t; while(t--) { int s,sg,fg,d,T; cin>>s>>sg>>fg>>d>>T; if(sg==fg) cout<<"DRAW"<<endl; else="" {="" float="" dis="50*d;" float="" v="(dis*60*60)/(1000*T);" v+="s;" if(fabs(v-sg)<fabs(v-fg))="" cout<<"sebi"<<endl;="" else="" if(fabs(v-sg)="">fabs(v-fg)) cout<<"FATHER"<<endl; else cout<<"DRAW"<<endl; } } return 0; }

link

answered 14 Jan '17, 00:17

salman_1's gravatar image

3★salman_1
1
accept rate: 0%

Can someone please tell me what is wrong. Tried many test cases and works for all but still getting wrong answer https://www.codechef.com/viewsolution/12641292

link

answered 26 Jan '17, 11:07

rchandu18's gravatar image

0★rchandu18
1
accept rate: 0%

@rchandu

I had a look at your code and found this

         "System.out.println(speed);"

The output CLEARLY says to print only "SEBI" or "FATHER" or "DRAW"

If you print out ANYTHING ELSE, like speed etc. Then the online judge (which is NOT a human) will flag your answer as wrong result. Follow output format closely, as even an extra blank space or full stop or comma will get you a wrong answer

Hope it helps :)

link

answered 26 Jan '17, 12:31

vijju123's gravatar image

5★vijju123 ♦
14.9k11856
accept rate: 18%

Can someone help me here? What is missing in my code? I am getting a WA. https://www.codechef.com/viewsolution/15176177

link

answered 31 Aug '17, 19:49

tusharggrwl's gravatar image

4★tusharggrwl
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:

×15,125
×1,554
×921
×60
×11

question asked: 20 Nov '16, 21:44

question was seen: 4,215 times

last updated: 31 Aug '17, 19:49