Problem 610

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
Hot_Sauce
Posts: 4
Joined: Sun Sep 24, 2017 11:51 am

Problem 610

Post by Hot_Sauce »

Are "CMD" and "MCD" both minimal, valid representations of 1400? Is only "MCD" valid?
I couldn't find anything disallowing something like "CMD" in the About page: https://projecteuler.net/about=roman_numerals.

LilStalker
Posts: 65
Joined: Thu Nov 03, 2016 4:32 pm

Re: Problem 610

Post by LilStalker »

CMD is invalid representantion of a roman numeral.
Image

Hot_Sauce
Posts: 4
Joined: Sun Sep 24, 2017 11:51 am

Re: Problem 610

Post by Hot_Sauce »

I thought so, but why.

LilStalker
Posts: 65
Joined: Thu Nov 03, 2016 4:32 pm

Re: Problem 610

Post by LilStalker »

To write a roman numeral you do so by using 'greedy' algorithm.

Let's say we want to express number 1400 as a roman numeral. With our greedy algorithm we will write it like this:

MCD -> 1000 + 400

If we check your example:

CMD -> 900 + 500

In the first step we did not use our best option, with CM we only add 900 to our number and not the maximum value 1000 posible using M.

I hope this helps.
Image

Hot_Sauce
Posts: 4
Joined: Sun Sep 24, 2017 11:51 am

Re: Problem 610

Post by Hot_Sauce »

Yes, Thank you.

This was the method I considered in my solution. Still couldn't get the right answer though

MuthuVeerappanR
Posts: 423
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 610

Post by MuthuVeerappanR »

What is the right way to write 14903 in Roman Numeral?

Is it "MMMMMMMMMMMMMMCMIII"???
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

Hot_Sauce
Posts: 4
Joined: Sun Sep 24, 2017 11:51 am

Re: Problem 610

Post by Hot_Sauce »

Yes, I believe so.

MuthuVeerappanR
Posts: 423
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Problem 610

Post by MuthuVeerappanR »

Thank you Hot_Sauce.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

DJohn
Posts: 57
Joined: Sat Oct 11, 2008 11:24 am

Re: Problem 610

Post by DJohn »

LilStalker wrote:
Sun Sep 24, 2017 12:16 pm
To write a roman numeral you do so by using 'greedy' algorithm.
The trouble is, neither the problem nor "About... Roman Numerals" mention a greedy algorithm. I agree that CMD is not a minimal representation of 1400 (I'd say it wasn't a valid representation at all), but that comes from external experience. Excluding it needs a bit of reading between the lines.

For problem 610, we've got a string of symbols, and we want to know if it is a minimal form. We start with CMD and ask which of the seven rules it violates. The only violation of the first rule is the M following C, but that's allowed for subtraction. We don't have enough smaller denominations to make up M, C, or X. D is only there once. C is used as the leading numeral in a subtractive pair, and it's before M. X and I don't appear, so the rules involving them don't apply.

No rules are broken (if the first is modified as subtraction requires), so surely CMD is a valid representation. And it's minimal, as there is no shorter representation of the same number.

The intended definition of minimality appears to be that a representation is minimal if and only if it is the result of applying the first set of rules to some number, followed by the second set, in two separate steps. If CMD was valid, it would have the value 1400. By the first three rules, that can only be written as MCCCC. Then we apply subtraction. We don't have enough Ms or Ds to do anything, but we can replace CCCC with CD giving MCD. This is not CMD, so CMD is not minimal.

(There's another rule that this example doesn't use: no symbol except M can appear five times. IIIII must be replaced with V, and so on.
This is a consequence of wanting to make a shorter representation).

I think a lot of people's confusion is because this definition is only implied. The rules as stated can be read as contradicting it. It only works if you read them not as conditions to be tested, but as an indirect way of specifying a process. The way it's written sort of implies that, but it's not very clear.

MHealy
Posts: 40
Joined: Sat Nov 17, 2012 11:32 pm

Re: Problem 610

Post by MHealy »

DJohn wrote:
Wed Sep 27, 2017 11:05 am
We don't have enough smaller denominations to make up M, C, or X
Forgive me if I've misunderstood the About page (I also relied on external information about Roman numerals rather than just this page), but is the interpretation of this rule when subtraction is included not to treat 'CM' as a lower denomination than 'M', and so 'CM' plus 'D' are being used to exceed 'M'? In the same way that we treat 'IX' as one number (9) to decide (using the first rule) that 19 is not IXX but XIX.
Image

User avatar
RobertStanforth
Administrator
Posts: 1239
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 610

Post by RobertStanforth »

'CM' is indeed considered a lower denomination than 'M', which is how 'CMD' is excluded by the second rule in the About page.
Using a symbol (other than 'M') five times will also violate that rule as it will equal or exceed the next greater symbol.

DJohn
Posts: 57
Joined: Sat Oct 11, 2008 11:24 am

Re: Problem 610

Post by DJohn »

RobertStanforth wrote:
Wed Sep 27, 2017 6:12 pm
'CM' is indeed considered a lower denomination than 'M'
That's what I was missing. I wasn't clear what a 'denomination' was.

blajer
Posts: 1
Joined: Wed Nov 15, 2017 2:37 pm

Re: Problem 610

Post by blajer »

What happens if the symbol "#" is selected as the first one? It passes the "what we have written down must always (when non-empty) be a valid Roman numeral representation in minimal form" rule by virtue of being empty, but I am not sure an empty string should indeed be accepted (it would probably map to 0 if accepted)?

Thanks for the clarification.

User avatar
hk
Administrator
Posts: 10706
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 610

Post by hk »

Please read on to the last paragraph:
Find the expected value of the number represented by what we have written down when we stop. (If nothing is written down then count that as zero. Give your answer rounded to 8 places after the decimal point.
Image

2rf
Posts: 1
Joined: Thu Dec 21, 2017 4:36 pm

Re: Problem 610

Post by 2rf »

What does "minimal form" mean?(there is no definition on problem page or on "About... Roman Numerals" page) Does every positive integer number has exactly one "valid Roman numeral representation in minimal form"?

User avatar
hk
Administrator
Posts: 10706
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 610

Post by hk »

2rf wrote:
Thu Dec 21, 2017 4:40 pm
What does "minimal form" mean?(there is no definition on problem page or on "About... Roman Numerals" page) Does every positive integer number has exactly one "valid Roman numeral representation in minimal form"?
From the "About...Roman Numerals" page:
Which means that IL would be considered to be an invalid way of writing forty-nine, and whereas XXXXIIIIIIIII, XXXXVIIII, XXXXIX, XLIIIIIIIII, XLVIIII, and XLIX are all quite legitimate, the latter is the preferred (minimal) form.
XLIX is the minimal form of 49.
The minimal form is the valid form that requires the least number of characters.
(You can read that too in the wording of Problem 89 (View Problem)
Image

User avatar
yourmaths
Posts: 27
Joined: Mon Aug 25, 2014 10:00 am

Re: Problem 610

Post by yourmaths »

Hello. I solved 610 last night, and DJohn's post was helpful in formulating my solution.

To be clear, in answering the problem, CMD is indeed considered invalid, as well as many of the other examples in the thread for problem 89. However, I'm not sure that this is definitively ruled out by the About Roman Numerals page.
RobertStanforth wrote:
Wed Sep 27, 2017 6:12 pm
'CM' is indeed considered a lower denomination than 'M', which is how 'CMD' is excluded by the second rule in the About page.
This implies that since CM=900 and D=500, CM+D>M, which is correctly ruled out by the second rule.

However, if we interpret CMD as C(MD), then C(MD)=(1000+500)-100=1400 and as D does not exceed M, MD is valid so that the second rule is not broken by this. Since C appears before M, rule iv. is fine as well. (Arguably though, C appears before MD in this interpretation.) Thus, interpreted in this way CMD does not appear to break any of the rules.

Given that problem 89 appeared over 14 years ago, I'm not suggesting any alterations to either problem formulation or the About page, but it seems that DJohn's sequential procedure or the greedy algorithm is needed to definitively define the minimal representation. I provide another interpretation in the solution forum, but I don't want to mention it here as it could provide hints on how to solve this problem.
level = lambda number_solved: number_solved // 25
Image

pjt33
Posts: 28
Joined: Mon Oct 06, 2008 5:14 pm

Re: Problem 610

Post by pjt33 »

The question states
The rules do not place any restriction on the number of occurrences of M, so all integers have a valid representation.
but doesn't explain how to get negative integers, and I got the tick with an answer which assumes that negative integers don't have a valid representation. I think that the question should be edited to say either "all positive integers" or "all non-negative integers".

User avatar
RobertStanforth
Administrator
Posts: 1239
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 610

Post by RobertStanforth »

pjt33 wrote:
Tue Feb 11, 2020 9:18 pm
The question states
The rules do not place any restriction on the number of occurrences of M, so all integers have a valid representation.
but doesn't explain how to get negative integers, and I got the tick with an answer which assumes that negative integers don't have a valid representation. I think that the question should be edited to say either "all positive integers" or "all non-negative integers".
Thank you for flagging this - you are correct. I have corrected the wording to "all positive integers".

Post Reply