Page 2 of 3

Posted: Wed Oct 01, 2003 10:36 pm
by abc
I don't get it!

Posted: Thu Oct 02, 2003 12:36 am
by Per
Farid Ahmadov wrote:There was said nothing about the length of repeating part or the length of the string.
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).


A general comment on problem statements (this is getting somewhat off-topic): 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?

Posted: Thu Oct 02, 2003 1:01 am
by Larry
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..

Posted: Thu Oct 02, 2003 2:33 am
by gvcormac
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..
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:

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

Posted: Thu Oct 02, 2003 2:49 am
by ditrix
thanks a lot for help, I have got accepted finally - my programme had an error that was not reproduced in my tests, so it was dificult to fix it.

Posted: Thu Oct 02, 2003 2:55 am
by gvcormac
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).
Suppose you want to add two fractions: a/b + c/d. The naive way to do this is to cross-multiply:

(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

Posted: Thu Oct 02, 2003 7:56 am
by Gatis
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:

Code: Select all

   A                B 
-------  + ------------------- 
  10^x      (10^y - 1) * 10^x
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!

Posted: Thu Oct 02, 2003 8:14 am
by little joey
Per wrote:
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?
Your solution considers this case automatically because 0.xy(zy) = 0.x(yz) for x,y,z being any string of digits!

Posted: Thu Oct 02, 2003 10:44 am
by Farid Ahmadov
Can anyone accepted give inputs and outputs? I am stucked. My program must be correct (only if I don't miss something that was not in statement) or can anyone check for the correctness of outputs that I wrote.

Thanks in advance.

Posted: Thu Oct 02, 2003 10:58 am
by Per
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.
Sorry, I was just being stupid here (my brain told that a 9-digit number could be as large as 9 billions). It's pretty obvious it will work with ints.
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!
Yes you're absolutely right.

Sorry again, my mind was somewhere else when I wrote that post.

Posted: Thu Oct 02, 2003 11:06 am
by Per
Farid: your output is correct.

You could try this:

Input:

Code: Select all

0.000000000...
0.000000001...
0.999929998...
0.999999997...
0.999999998...
0.999999999...
0.0...
0
Output:

Code: Select all

0/1
1/900000000
499915003/499950000
449999999/450000000
899999999/900000000
1/1
0/1

Posted: Thu Oct 02, 2003 11:13 am
by Farid Ahmadov
Hi people. I am very happy to get accepted this problem and I must say that my program is the best program written on Pascal.

Per there can't be input like 0.00000... Thanx for checking I/O.

Sorry for my boastfulness. Bye.

EPP Issue

Posted: Thu Oct 02, 2003 12:53 pm
by shahriar_manzoor
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 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.

Re: EPP Issue

Posted: Thu Oct 02, 2003 7:06 pm
by little joey
shahriar_manzoor wrote:
little joey wrote:Right Per,
A case for the EPP, I would guess. Some form of quality assurance wouldn't be misplaced...

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

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

Posted: Thu Oct 02, 2003 7:45 pm
by Farid Ahmadov
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.