MergingNumbers
SRM 852 · 2024-01-23 · by misof
Problem Statement
Two positive integers can be merged if and only if the last three digits of the first integer match the first three digits of the second integer. If they do, you can merge them together into one bigger integer by overlapping those digits.
For example, you can merge 7890 and 890123 into 7890123. Merging 100147 with 147 into 100147 is also valid. You cannot merge 12345 with 543789, the order of digits matters: the end "345" is not the same as the beginning "543".
It is not allowed to add extra leading zeros before merging. E.g., you are not allowed to merge 4007 with 759 by pretending that the second number is 00759.
Note that if a number has fewer than three digits, it cannot be merged with anything. E.g., there is no x such that you can merge x and 47, and there is no y such that you can merge 47 and y.
Suppose you have a collection of (not necessarily distinct) positive integers. In each step you can select any two numbers that can be merged and merge them - i.e., discard both of them from the collection and add the number you produced by merging them into the collection instead.
For example, if you collection is 1234, 1234, 1234, 2345, you can merge one of the 1234s with the 2345. Your new collection will be 1234, 1234, 12345.
The collection is called nice if there is a sequence of zero or more such steps after which the collection will consist of a single number.
The
Constraints
- numbers will contain between 1 and 300 elements, inclusive.
- Each element of numbers will be between 1 and 10^9, inclusive.
{ 1234567 }
Returns: 0
We perform zero steps, as we already have a single number. Any single number clearly forms a nice collection.
{ 12345, 78901, 3456789 }
Returns: 0
We can first merge 3456789 and 78901 into 345678901, and then merge 12345 and 345678901 into 12345678901.
{ 22222, 22222, 22222, 22222, 22222, 22222, 22222 }
Returns: 0
The numbers in the collection are not necessarily distinct. We can merge these in any order and after six steps we will have a single number. That number will always be 22222222222222222.
{1, 2, 3, 11, 22, 3}
Returns: -1
No two of these six numbers can be merged.
{1234, 3456}
Returns: 2345
We cannot merge these two numbers, so the collection is not nice. If we add 2345 to the collection, we can then eventually merge everything into a single number, so 2345 is a valid return value. Other valid solutions include 234719345 and 45609123.
{1234, 5678, 3456}
Returns: -1
In order to turn this collection into a nice one we would need to add at least two new numbers.
{123123123, 1234, 1234, 1234, 1234, 1234, 234890123, 234890123}
Returns: -1
If the collection contains duplicates, their exact counts matter. The above collection is not nice and it cannot be made into a nice collection by adding any single number. However, adding two additional copies of 234890123 would make this collection nice.
Submissions are judged against all 91 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MergingNumbers with a public method int solve(vector<int> numbers) · 91 test cases · 2 s / 256 MB per case