Project Euler Forum

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.

CMD is invalid representantion of a roman numeral.

I thought so, but why.

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.

Yes, Thank you.

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

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

Is it "MMMMMMMMMMMMMMCMIII"???

Yes, I believe so.

Thank you Hot_Sauce.

LilStalker wrote: Sun Sep 24, 2017 1: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.

DJohn wrote: Wed Sep 27, 2017 12:05 pm 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.

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

RobertStanforth wrote: Wed Sep 27, 2017 7: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.

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.

Please read on to the last paragraph:

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"?

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: 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)

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

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

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

I think the "official" descriptions of Roman Numerals are pretty confusing and contradictory. Terms like "denomination", "numeral", etc are used ambiguously.

For example, the rules state that "Numerals must be arranged in descending order of size."

This only works if we interpret "numerals" as "lone numerals or subtractive combinations", or if we assume that the rule is just wrong and is superseded by the subtractive rules. "size" also is not well defined. But the description of subtractive combinations refers to the individual characters as "numerals", so we cannot interpret it this way and it is simply contradictory.

I would instead say something like "Roman Numerals consist of single characters and possibly subtractive combinations in decreasing order of value. Eg the the single characters and subtractive pairs must occur in the order M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I. The single characters M, C, X, and I may repeat. However, D, L, and V may only occur at most once each, and at mot one subtractive pair may appear with each subtractand, ie only one IX or IV is allowed, etc."

But even this is incomplete and confusing, since we still need to disallow Roman Numerals like "IIIIIIIIII", "IXI", and (this one isn't even really disallowed by the current rules afaik, it's just not minimal) "IVI".

The "greedy algorithm" description is likely the best we will find, haha