ColorfulGarden
SRM 689 · 2016-04-01 · by cgy4ever
SRM 689 · 2016-04-01 · by cgy4ever · Greedy
Problem Statement
Problem Statement
We have a garden that contains some flowers.
The flowers are arranged into a rectangle with 2 rows and n columns.
You are given a String[] garden that describes our garden.
The String[] garden has two elements, each with n characters.
Each character in garden represents one flower.
Different characters in garden represent different colors.
Two flowers are considered adjacent if they are in the same column, or if they are next to each other in the same row. Your goal is to produce a garden in which no pair of adjacent flowers shares the same color. You may rearrange the flowers in your garden arbitrarily (without changing its shape). More precisely, you may swap any two flowers in your garden, and you may do so arbitrarily many times.
If the goal can be reached, return aString[] that will encode the resulting garden in the same format as was used for garden.
If there are multiple solutions, you may return any of them.
If there is no solution, return an empty String[] .
Two flowers are considered adjacent if they are in the same column, or if they are next to each other in the same row. Your goal is to produce a garden in which no pair of adjacent flowers shares the same color. You may rearrange the flowers in your garden arbitrarily (without changing its shape). More precisely, you may swap any two flowers in your garden, and you may do so arbitrarily many times.
If the goal can be reached, return a
Constraints
- garden will contain exactly 2 elements, inclusive.
- Each element in garden will contain between 1 and 50 characters, inclusive.
- Each element in garden will contain the same number of characters.
- Each character in garden will be a lowercase letter ('a'-'z').
Examples
0)
{"aa",
"bb"}
Returns: {"ba", "ab" }
Swapping garden[0][1] and garden[1][1] produces a valid garden.
1)
{"xxxx",
"xxxx"}
Returns: { }
No matter what we do, we will end up with the same result, and that is not a valid solution.
2)
{"abcd",
"abcd"}
Returns: {"abcd", "dcba" }
3)
{"abcdefghijklm",
"nopqrstuvwxyz"}
Returns: {"abcdefghijklm", "nopqrstuvwxyz" }
4)
{"aaa",
"aab"}
Returns: { }
Submissions are judged against all 133 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ColorfulGarden with a public method vector<string> rearrange(vector<string> garden) · 133 test cases · 2 s / 256 MB per case