10555  Dead Fraction
Moderator: Board moderators
Actually, the statement clearly says "dddd is a string of 1 to 9 digits, not all zero.". Looking at the formulas, this implies that the result will fit well within a long long (and though I think it should be possible to get overflow with an int, I think the Waterloo sample solutions used it, so that should be ok too).Farid Ahmadov wrote:There was said nothing about the length of repeating part or the length of the string.
A general comment on problem statements (this is getting somewhat offtopic): I agree with little joey that there's often a tendency to make problems hard by obscurity. However, I neither think this is a new problem, nor do I think it has gotten worse  on the contrary, I think things are generally getting better (though there are of course exceptions). Just look at old world finals/regionals from the late 80's/early 90's!
IMO, the Waterloo contests almost always have good problems, and I don't think this specific problem was too vaguely worded. But there seems to be many who misinterpreted it or just didn't understand it, so I might be wrong.
There is a problem though (which I hadn't thought about before): it is not at all obvious whether the repeating part of "0.xyzy" could be "yz"; my solution assumes that it can't. Or am I too missing some part of the problem statement?

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Well, if a problem's difficulty depends not on algorithm but your ability to guess the intention correctly, then doesn't that reduce it to luck?
The programming, while not trivial, wasn't the hardest part of the problem, and it's one of those things, either you get it or you don't. Unforunately, I fell in the latter until reading this forum.
Of course, Waterloo's problems are usually really good and clear, and it does happen once in awhile..
The programming, while not trivial, wasn't the hardest part of the problem, and it's one of those things, either you get it or you don't. Unforunately, I fell in the latter until reading this forum.
Of course, Waterloo's problems are usually really good and clear, and it does happen once in awhile..
I am sorry to belabour this, but deriving a precise mathematical interpretation of a word problem is part of the game. I categorically reject the notion that you have to guess in order to do this. The problem statement says:Larry wrote:Well, if a problem's difficulty depends not on algorithm but your ability to guess the intention correctly, then doesn't that reduce it to luck?
The programming, while not trivial, wasn't the hardest part of the problem, and it's one of those things, either you get it or you don't. Unforunately, I fell in the latter until reading this forum.
awhile..
 Whenever a repeating fraction was displayed, Mike simply recorded the first few digits followed by "...".
 no digit from the repeating portion of the decimal expansion was left unrecorded
 the original fraction is always the simplest one that produces the given sequence of digits
 by simplest, he means the the one with smallest denominator
 For each case, output the original fraction.
I acknowledge that interpretating word problems might not be everyone's forte, or to everyone's taste. But I believe that all necessary information to solve the problem is present in the problem statement.
Suppose you want to add two fractions: a/b + c/d. The naive way to do this is to crossmultiply:Per wrote: Looking at the formulas, this implies that the result will fit well within a long long (and though I think it should be possible to get overflow with an int, I think the Waterloo sample solutions used it, so that should be ok too).
(ad + bc)/bd.
This can cause unecessary overflow. Suppose we know that b=jx and d=kx. Then the answer is of course
(akx + bjx)/jkx^2.
You can simplify in advance and compute
(ak + bj)/jkx
which is the same fraction.
Solving that
Hi,
I've just solved it. I was reading messages posted here and I aggree that problem should be better explained. I'm sure about that because it's an easy problem and there was too few accepted answers. I think it could be better exemplifieded.
My solution:
The input is '0.dddddd...', let L be the length of 'dddddd'.
I've divided the 'dddddd' in two parts, say A and B, where A is the not periodic part and B is the periodic part.
The fracation could me written like this:
where x is the length of A and y is the length of B.
(note '10^y  1' produces the '9' sequence)
Now we test all x and y such that x + y = L. It will produce all interpretations.
Of course you have to find the GCD and divide the numerator and the denominator to achieve the smallest fraction representation.
The simplest fraction will be that one who has the smallset denominator in all tested interpretations.
That's it!
I've just solved it. I was reading messages posted here and I aggree that problem should be better explained. I'm sure about that because it's an easy problem and there was too few accepted answers. I think it could be better exemplifieded.
My solution:
The input is '0.dddddd...', let L be the length of 'dddddd'.
I've divided the 'dddddd' in two parts, say A and B, where A is the not periodic part and B is the periodic part.
The fracation could me written like this:
Code: Select all
A B
 + 
10^x (10^y  1) * 10^x
(note '10^y  1' produces the '9' sequence)
Now we test all x and y such that x + y = L. It will produce all interpretations.
Of course you have to find the GCD and divide the numerator and the denominator to achieve the smallest fraction representation.
The simplest fraction will be that one who has the smallset denominator in all tested interpretations.
That's it!

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Per wrote:
Your solution considers this case automatically because 0.xy(zy) = 0.x(yz) for x,y,z being any string of digits!There is a problem though (which I hadn't thought about before): it is not at all obvious whether the repeating part of "0.xyzy" could be "yz"; my solution assumes that it can't. Or am I too missing some part of the problem statement?

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan
Sorry, I was just being stupid here (my brain told that a 9digit number could be as large as 9 billions). It's pretty obvious it will work with ints.gvcormac wrote:<...>Per wrote:Looking at the formulas, this implies that the result will fit well within a long long (and though I think it should be possible to get overflow with an int, I think the Waterloo sample solutions used it, so that should be ok too).
You can simplify in advance and compute
(ak + bj)/jkx
which is the same fraction.
Yes you're absolutely right.little joey wrote:Your solution considers this case automatically because 0.xy(zy) = 0.x(yz) for x,y,z being any string of digits!
Sorry again, my mind was somewhere else when I wrote that post.
Farid: your output is correct.
You could try this:
Input:
Output:
You could try this:
Input:
Code: Select all
0.000000000...
0.000000001...
0.999929998...
0.999999997...
0.999999998...
0.999999999...
0.0...
0
Code: Select all
0/1
1/900000000
499915003/499950000
449999999/450000000
899999999/900000000
1/1
0/1

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
EPP Issue
I will not comment on this problem as I have not solved it. But EPP has been set up to ensure quality. So if you think quality is not being assured by EPP you must you must set specific examples from contests arranged by EPP. Generally, it is quite ok for a contest to have a problem not so well described. Because in real regional contests (Other than great regions like ECNA, and some european regions and also some other. I just hope that the organizers considers themselves in the good ones and don't become angry on me) you won't find very good problem description always. Often ranges are not specified (In Kanpur contests). If you see problemset of Dhaka regional 1998 you will start getting temparature. Ranges of data are often not specified in many european regionals. So the world is not perfect and I think sometimes it is good to have some problems which are not very easy to understand.little joey wrote:Right Per,
A case for the EPP, I would guess. Some form of quality assurance wouldn't be misplaced...
little joey

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Re: EPP Issue
I'm sorry, but that's not what I meant. What I meant was that EPP could be the body that checks wether problems could enter the UVA problem set or not, by applying certain quality standards. But I don't know (and don't want to know) the inner workings of UVA, EPP or any contest organising or problem setting organisation. It was just a loose idea on how to maintain or improve the quality of the problems in general.shahriar_manzoor wrote:... But EPP has been set up to ensure quality. So if you think quality is not being assured by EPP you must you must set specific examples from contests arranged by EPP. ...little joey wrote:Right Per,
A case for the EPP, I would guess. Some form of quality assurance wouldn't be misplaced...
little joey
I don't want to be offensive to anybody, I just want to expres my opinion and give (what I think is) positive criticism. Surely the world isn't perfect, which makes it an interesting place to live in, but one can always try to improve the little part of it in which one (temporarily) dwells.
little joey

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan
What does EPP do? It sets problems or just check quality of a problems? And what are criterions to problem? To my mind these criterions are:
1. readability  Not too difficult to read.
2. clear statement  I mean a statement where everything is said about problem and everything else can be found logically.
3. difficulty  As EPP is an elite orgranisation, problems must be not too easy. I mean problem must have more than 1 or 2 logical and algorithmic steps.
(4). This must be a result of previous criterions: A problem that has passed quality ensure must not be criticized. If problem has passed EPP quality ensure then it is a good problem and can take place in problemset. There is no need to criticize it.
EPP is working well and everyone can make mistake. So I wish EPP good luck.
1. readability  Not too difficult to read.
2. clear statement  I mean a statement where everything is said about problem and everything else can be found logically.
3. difficulty  As EPP is an elite orgranisation, problems must be not too easy. I mean problem must have more than 1 or 2 logical and algorithmic steps.
(4). This must be a result of previous criterions: A problem that has passed quality ensure must not be criticized. If problem has passed EPP quality ensure then it is a good problem and can take place in problemset. There is no need to criticize it.
EPP is working well and everyone can make mistake. So I wish EPP good luck.
_____________
NO sigNature
NO sigNature