IOI '16 - Kazan, Russia

Paint By Numbers

Paint by Numbers is a well-known puzzle game. We consider a simple one-dimensional version of this puzzle. In this puzzle, the player is given a row of n cells. The cells are numbered 0 through n − 1 from the left to the right. The player has to paint each cell black or white. We use 'X' to denote black cells and '_' to denote white cells.

The player is given a sequence c = [c₀, …, c_k−1] of k positive integers: the clues. He has to paint the cells in a way such that the black cells in the row form exactly k blocks of consecutive cells. Moreover, the number of black cells in the i-th block (0-based) from the left should be equal to c_i. For example, if the clues are c = [3, 4], the solved puzzle must have exactly two blocks of consecutive black cells: one of length 3 and then another of length 4. Hence, if n = 10 and c = [3, 4], one solution satisfying the clues is "_XXX__XXXX". Note that "XXXX_XXX__" does not satisfy the clues because the blocks of black cells are not in the correct order. Also, "__XXXXXXX_" does not satisfy the clues because there is a single block of black cells, not two separate blocks.

You are given a partially solved Paint By Numbers puzzle. That is, you know n and c, and additionally you know that some cells must be black and some cells must be white. Your task is to deduce additional information about the cells.

Specifically, a valid solution is one that satisfies the clues, and also agrees with the colors of the known cells. Your program should find cells that are painted black in every valid solution, and cells that are painted white in every valid solution.

You may assume that the input is such that there is at least one valid solution.

You should implement one operation solve_puzzle:

• solve_puzzle(n, s, k, c[])
  • n: length of the string s (number of cells).
  • s: string of length n. For each i (0 ≤ i ≤ n − 1) character i is:
    • 'X', if cell i must be black,
    • '_', if cell i must be white,
    • '.', if there is no information about cell i.
  • k: length of the array c (number of clues).
  • c: array of length k containing clues, as defined above,
  • the program should output a string of length n. For each i (0 ≤ i ≤ n − 1) character i of the output string should be:
    • 'X', if cell i is black in every valid solution,
    • '_', if cell i is white in every valid solution,,
    • '?', otherwise (i.e., if there exist two valid solutions such that cell i is black in one of them and white in the other one).

Input Format

The input will be given in the following format:

• Line 1: string s of length n
• Line 2: integer k, followed by a space, followed by k space-separated integers c₀, …, c_{k − 1}

Output Format

Your output should be in the following format:

• Line 1: a string of length n

Sample Input 1

..........
2 3 4

Sample Output 1

??X???XX??

Explanation 1

These are all possible valid solutions of the puzzle:

• "XXX_XXXX__"
• "XXX__XXXX_"
• "XXX___XXXX"
• "_XXX_XXXX_"
• "_XXX__XXXX"
• "__XXX_XXXX"

One can observe that the cells with (0-based) indices 2, 6, and 7 are black in each valid solution. Each of the other cells can be, but does not have to be black. Hence, the correct answer is "??X???XX??".

Sample Input 2

........
2 3 4

Sample Output 2

XXX_XXXX

Explanation 2

In this example the entire solution is uniquely determined and the correct answer is "XXX_XXXX".

Sample Input 3

..._._....
1 3

Sample Output 3

???___????

Explanation 3

In this example we can deduce that cell 4 must be white as well – there is no way to fit three consecutive black cells between the white cells at indices 3 and 5. Hence, the correct answer is "???___????".

Sample Input 4

.X.........
1 3

Sample Output 4

?XX?______

Explanation 4

There are only two valid solutions that match the above description:

• “XXX_______”,
• “_XXX______”.

Thus, the correct answer is "?XX?______".

Subtasks

In all subtasks: 1 ≤ k ≤ n, and 1 ≤ c_i ≤ n for each 0 ≤ i ≤ k − 1.

1. (7% of points) n ≤ 20, k = 1, s contains only '.' (empty puzzle),
2. (3% of points) n ≤ 20, s contains only '.',
3. (22% of points) n ≤ 100, s contains only '.',
4. (27% of points) n ≤ 100, s contains only '.' and '.' (information only about white cells),
5. (21% of points) n ≤ 100,
6. (10% of points) n ≤ 5000 k ≤ 100,
7. (10% of points) n ≤ 200 000 k ≤ 100.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 2048M
Added: Aug 10, 2017

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

In subtask 4 description, it says: "s contains only '.' and '.'", but it must say: "s contains only '.' and '_'". Please fix that if I am right.