E. The Swapping Game

Codeforces

IDCF10015E

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Last year you invented a game which can be played using a board and a die (singular of dice), this year you invented another new game which can be played using a single string of some letters. The game starts with a string of *N* lower case English letters ('a' to 'z'), and you can only swap two different characters in this string, and you can make this step zero or more times. Your goal is to reach the lexicographically smallest string after doing zero or more moves. But there are some constraints on the final string. For each position, it must be a letter of some given letters (the given letters are not necessary the same for each position). For example, the first letter must be 'a' or 'b', the second letter must be 'b' or 'c', and so on. Note that these constraints are on the final string only, which means you can make moves which cause invalid strings to reach a valid string after some more moves. Given the initial string and the constraints on each position, your task is to write a program to find the lexicographically smallest valid string after making zero or more moves. _Note: When comparing two different strings of the same length, the lexicographically smaller one is the one with a smaller letter on the first place where they differ._ The input starts with a line containing the initial string *S* which consists of *N* lower case English letters (1 ≤ *N* ≤ 100). Followed by *N* lines each line contains a string *Ci* which consists of *Li* distinct lower case English letters (1 ≤ *Li* ≤ 5) which are the valid letters for the *ith* position in the final string. Each letter in each *Ci* will appear at least once in *S*. Print on a single line the lexicographically smallest valid string you can get after zero or more moves. If there is no such valid string print "NO SOLUTION" (without the quotes). ## Input The input starts with a line containing the initial string *S* which consists of *N* lower case English letters (1 ≤ *N* ≤ 100). Followed by *N* lines each line contains a string *Ci* which consists of *Li* distinct lower case English letters (1 ≤ *Li* ≤ 5) which are the valid letters for the *ith* position in the final string. Each letter in each *Ci* will appear at least once in *S*. ## Output Print on a single line the lexicographically smallest valid string you can get after zero or more moves. If there is no such valid string print "NO SOLUTION" (without the quotes). [samples]

**Definitions** Let $ S = (s_1, s_2, \dots, s_N) $ be the initial string of $ N $ lowercase English letters. Let $ C_i \subseteq \{a, b, \dots, z\} $ be the set of valid letters for position $ i $, for $ i = 1, \dots, N $. Let $ \mathcal{M} $ be the multiset of characters in $ S $. **Constraints** 1. $ 1 \leq N \leq 100 $ 2. For each $ i \in \{1, \dots, N\} $, $ 1 \leq |C_i| \leq 5 $ 3. For each $ c \in \bigcup_{i=1}^N C_i $, the multiplicity of $ c $ in $ \mathcal{M} $ is at least the number of positions $ i $ for which $ c \in C_i $. **Objective** Find the lexicographically smallest string $ T = (t_1, t_2, \dots, t_N) $ such that: - $ t_i \in C_i $ for all $ i \in \{1, \dots, N\} $, - The multiset of characters in $ T $ equals $ \mathcal{M} $. If no such $ T $ exists, output "NO SOLUTION".

API Response (JSON)

{
  "problem": {
    "name": "E. The Swapping Game",
    "description": {
      "content": "Last year you invented a game which can be played using a board and a die (singular of dice), this year you invented another new game which can be played using a single string of some letters. The ga",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10015E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Last year you invented a game which can be played using a board and a die (singular of dice), this year you invented another new game which can be played using a single string of some letters.\n\nThe ga...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S = (s_1, s_2, \\dots, s_N) $ be the initial string of $ N $ lowercase English letters.  \nLet $ C_i \\subseteq \\{a, b, \\dots, z\\} $ be the set of valid letters for position $ i $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments