CCC '23 S3 - Palindromic Poster - Olympiads Online Judge

CCC '23 S3 - Palindromic Poster

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 1G

Author:

Problem types

Canadian Computing Competition: 2023 Stage 1, Senior #3

Ryo and Kita are designing a new poster for Kessoku Band. After some furious brainstorming, they came to the conclusion that the poster should come in the form of a 2-D grid of lowercase English letters (i.e. a to z), with $N$ $N$ rows and $M$ $M$ columns.

Furthermore, it is known that Ryo and Kita both have peculiar tastes in palindromes. Ryo will only be satisfied with the poster if exactly $R$ $R$ of its rows are palindromes, and Kita will only be satisfied with the poster if exactly $C$ $C$ of its columns are palindromes. Can you design a poster that will satisfy both Ryo and Kita, or determine that it is impossible to do so?

Note: A string is considered a palindrome if it is the same when read forwards and backwards. For example, kayak and bb are palindromes, whereas guitar and live are not.

Input Specification

The first and only line of input consists of $4$ $4$ space-separated integers $N$ $N$ , $M$ $M$ , $R$ $R$ , and $C$ $C$ .

The following table shows how the available 15 marks are distributed:

Marks Awarded	Bounds on $N$ $N$	Bounds on $M$ $M$	Bounds on $R$ $R$	Bounds on $C$ $C$
2 marks	$2 \le N \le 2\,000$ $2 \leq N \leq 2 000$	$2 \le M \le 2\,000$ $2 \leq M \leq 2 000$	$R = 1$ $R = 1$	$C = 1$ $C = 1$
2 marks	$N = 2$ $N = 2$	$M = 2$ $M = 2$	$0 \le R \le N$ $0 \leq R \leq N$	$0 \le C \le M$ $0 \leq C \leq M$
4 marks	$N = 2$ $N = 2$	$2 \le M \le 2\,000$ $2 \leq M \leq 2 000$	$0 \le R \le N$ $0 \leq R \leq N$	$0 \le C \le M$ $0 \leq C \leq M$
7 marks	$2 \le N \le 2\,000$ $2 \leq N \leq 2 000$	$2 \le M \le 2\,000$ $2 \leq M \leq 2 000$	$0 \le R \le N$ $0 \leq R \leq N$	$0 \le C \le M$ $0 \leq C \leq M$

Output Specification

If it is impossible to design a poster that will satisfy both Ryo and Kita, output IMPOSSIBLE on a single line.

Otherwise, your output should contain $N$ $N$ lines, each consisting of $M$ $M$ lowercase English letters, representing your poster design. If there are multiple possible designs, output any of them.

Sample Input 1

Copy

4 5 1 2

Output for Sample Input 1

Copy

union
radar
badge
anime

Explanation of Output for Sample Input 1

In the given design, only the second row (namely radar) and the second and third columns (namely naan and iddi) are palindromes. Since exactly $R = 1$ $R = 1$ of the rows and $C = 2$ $C = 2$ of the columns are palindromes, this is an acceptable design.

Sample Input 2

Copy

2 2 2 1

Output for Sample Input 2

Copy

IMPOSSIBLE

Explanation of Output for Sample Input 2

In this case, it can be proven that it is impossible to satisfy both Ryo and Kita.

Comments

Comments are disabled on this page.

38

wleung_bvg commented on March 4, 2023, 6:16 a.m.

no way comments are locked on ccc

25

Kirito commented on March 5, 2023, 1:59 a.m.

no way bocchi the lock on comment rock

64

ThingExplainer commented on Feb. 18, 2023, 2:25 a.m.

no way bocchi the rock on ccc

16

yikk02 commented on Feb. 28, 2023, 3:03 a.m.

no way bocchi the rock on ccc

17

wdotmathree commented on Feb. 27, 2023, 3:31 p.m.

no way bocchi the rock on ccc

-135

badlol commented on Feb. 27, 2023, 1:20 a.m.

bocchi the rock sucks

This comment is hidden due to too much negative feedback. Show it anyway.

21

kujiyh commented on Feb. 22, 2023, 7:12 p.m.

no way bocchi the rock on ccc

22

SunnyLin commented on Feb. 22, 2023, 4:46 p.m.

no way bocchi the rock on ccc

23

Seal commented on Feb. 21, 2023, 8:37 p.m.

no way bocchi the rock on ccc

27

Bill_Skills commented on Feb. 18, 2023, 2:55 a.m.

no way bocchi the rock on ccc

28

Vertiqo commented on Feb. 18, 2023, 2:27 a.m.

no way bocchi the rock on ccc

29

multiapples commented on Feb. 18, 2023, 2:26 a.m.

no way bocchi the rock on ccc