Introduction

This problem was shared by a skilled programmer from BUAA.

When I first saw this graphical problem, I was drawn to the way its pattern evolved, so much like a fractal. It looked like a straightforward drawing simulation, but as the number of operations n increased, the pattern’s size and complexity grew explosively. That made me realize that simply drawing everything by brute force could not be the right approach. This post reviews the whole process of discovering and implementing an elegant recurrence amid those complicated transformations, and ultimately solving the problem neatly.

The Problem

Background

A lilac flower usually has four petals. Their relative positions can be represented by the basic pattern below.

Four squares alone clearly cannot convey a lilac’s charm, so we perform one operation on the pattern, consisting of these two steps:

  1. Repeat the pattern 4 times, arranged as in the repetition diagram below.
  2. Rotate the pattern 45 degrees, as in the diagram showing the result of one operation.

We call these two steps together one operation. Repeating one more operation on the resulting pattern gives the pattern shown below after two operations.
Figure 1 Figure 2 Figure 3 Figure 4
Basic pattern The basic pattern repeated four times After one operation After two operations

Description

Write a program to draw the pattern after n operations. Note that the basic pattern is the result of 0 operations.

When printing, output the character o wherever the pattern contains a square and a space wherever it does not. Trailing spaces on a line may be ignored.

For example, the basic pattern (n=0) should be printed as:

1
2
3
  o
o   o
  o

The pattern after two operations (n=2) should be printed as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
            o     o
          o   o o   o
            o     o
            o     o
          o   o o   o
  o     o   o     o   o     o
o   o o   o         o   o o   o
  o     o             o     o
  o     o             o     o
o   o o   o         o   o o   o
  o     o   o     o   o     o
          o   o o   o
            o     o
            o     o
          o   o o   o
            o     o

Input

Input a nonnegative integer n, the number of operations.

The data guarantees 0 <= n <= 6.

Output

Print the pattern after n operations.

Special note: To make console output easier, when the number of operations n is odd, rotate the pattern 45 degrees before printing.

Sample Input

1
1

Sample Output

1
2
3
4
5
6
  o     o
o   o o   o
  o     o
  o     o
o   o o   o
  o     o

Analysis

Once we understand the statement, we can break one operation into two basic steps:

  1. Expansion: Treat the current pattern as a unit and tile it without overlap into a larger 2x2 pattern.
  2. Rearrangement: Rearrange the four expanded quadrants with overlap to create a visual effect similar to a 45-degree rotation.

The difficulty in simulating this directly lies in the second step, rearrangement. What is the side length of the new pattern after each rearrangement? At exactly which coordinates should the four quadrants be placed? These parameters do not change linearly; without finding a pattern, there is no clear way to proceed. So the heart of the problem shifts from how to draw the pattern to how to calculate the canvas size and placement coordinates at each step.

My solution takes an iterative approach: start from the basic pattern at n=0, then loop n times, generating the next stage on each iteration. These iterations do not all behave the same way. They use two quite different generation rules depending on whether the iteration number is odd or even.

Algorithm Design and Implementation

My algorithm makes the statement’s abstract “one operation” concrete by alternating expansion on odd-numbered steps with rearrangement on even-numbered steps. A for loop simulates n of these alternating transformations to produce the target pattern.

The Core Idea: Iterative Generation Alternating by Parity

We iterate from i=1 to n in a for loop, where i is the current transformation number.

  1. When i is odd: the expansion stage

    • Task: Simply copy and enlarge.
    • Implementation: Treat the entire pattern from the previous step (i-1), called temp, as a “tile.” On a new canvas called pic, of size a_temp * 2, tile it into the four quadrants of pic without overlap. This step is intuitive: the pattern’s structure stays the same, while its dimensions double.

  2. When i is even: the rearrangement stage

    • Task: Carry out the more complicated overlap and contraction.
    • Implementation: This step works with the expanded pattern of four quadrants generated at the odd-numbered stage. Rearrange these four “tiles,” placing them at the top, bottom, left, and right of a new canvas to form a cross with overlap in the center.
    • The challenge: The new canvas size a_pic and the exact coordinates for the four “tiles” are the key. Through observation and working through the patterns, I found a crucial recurrence.

The Key Discovery: The b[i-3] Recurrence

The parameters in the rearrangement stage are not arbitrary. I found that for transformation i (where i is even and i >= 4), both the new canvas size and the depth of the overlap have a definite mathematical relationship with the canvas side length b[i-3] after transformation i-3.

Here is a hand-drawn diagram from my working notes to make this easier to see:

My working sketch

Diagram guide: The sketch shows successive stages labeled n=1 through n=5. Dashed outlines mark the canvases; the small highlighted squares mark overlap regions used when working out the side-length recurrence.

  • Calculating the new canvas size a_pic (the update_a function):
    a_pic(i) = a_pic(i-1) + (a_pic(i-1) - b[i-3]) * 2
    Here, a_pic(i-1) is the side length from the preceding odd-numbered expansion stage. The formula describes how the new canvas expands from the previous stage according to the historical state at step i-3.

  • Calculating the placement coordinates (the draw function):
    In draw, the starting-coordinate offsets for placing the “tiles” are also determined by b[i-3]. For example, both the y coordinate of the left tile and the x coordinate of the top tile involve the key offset a_temp - (b[i - 3] - 1), where a_temp is a_pic(i-1).

This recurrence is the key to the pattern’s evolution. It turns a complicated geometry problem into a mathematical calculation that can be performed precisely using historical data. The case i=2 needs separate handling, since i-3 is not meaningful then.

Feasibility Analysis

  • Time complexity:

    • The outer loop runs n times. Within each iteration, the core operation is draw, which essentially copies an array and takes O(a_temp^2).
    • The canvas side length a_pic grows roughly like a geometric sequence with common ratio 2*sqrt(2) (*2 on odd steps and around *sqrt(2) on even steps). For small n, the growth of a_pic remains manageable, and the total amount of computation is acceptable within the problem’s constraints.

  • Space complexity:

    • We need two two-dimensional arrays, pic and temp, to store the patterns. Their size is determined by the final a_pic, so space complexity is O(a_pic^2).

  • Conclusion:
    The algorithm turns complicated pattern generation into iterative calculation. Finding the recurrence avoids complicated geometric derivations. The approach is feasible.

Implementation

I built the final accepted code from these ideas. It uses the two arrays pic and temp as a double buffer, alternating between generating and temporarily storing the pattern. The update_a and draw functions implement the odd/even transformation rules precisely.

Expand/collapse the final accepted code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e3 + 5;

int n, a_pic = 3, a_temp = 3, b[10];
char pic[maxn][maxn];
char temp[maxn][maxn];

bool isEven(int num){
	return !(num & 1);
}

void draw(int x, int y){
	for(int i = 1; i <= a_temp; ++i){
		for(int j = 1; j <= a_temp; ++j){
			if(pic[x + i - 1][y + j - 1] != 'o'){
				pic[x + i - 1][y + j - 1] = temp[i][j];
			}
		}
	}
}

void update_a(int x){
	if(!isEven(x)){
		a_pic *= 2;
		b[x] = a_pic;
	}
	else{
		if(x == 2){
			a_pic = a_temp * 3 - 2;
		}
		else{
			a_pic = a_pic + (a_pic - b[x - 3]) * 2;
		}
	}
}

void update_temp(){
	for(int i = 1; i <= a_pic; ++i){
		for(int j = 1; j <= a_pic; ++j){
			if (pic[i][j] == 0) {
				pic[i][j] = ' ';
			}
			temp[i][j] = pic[i][j];
		}	
	}
	a_temp = a_pic;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	temp[1][1] = ' ', temp[1][2] = 'o', temp[1][3] = ' ', temp[2][1] = 'o', temp[2][2] = ' ', temp[2][3] = 'o', temp[3][1] = ' ', temp[3][2] = 'o', temp[3][3] = ' ';
	cin >> n;
	if(n == 0){
		for(int i = 1; i <= 3; ++i){
			for(int j = 1; j <= 3; ++j){
				cout << " " << temp[i][j];
			}
			cout << '\n';
		}
		return 0;
	} 
	for(int i = 1; i <= n; ++i){
		update_a(i);
		for (int j = 1; j <= a_temp; ++j) {
			memset(pic[j], 0, sizeof pic[j]);
		}
		if(!isEven(i)){
			draw(1, 1);
			draw(1, 1 + a_temp);
			draw(1 + a_temp, 1);
			draw(1 + a_temp, 1 + a_temp);
		}
		else{
			if(i == 2){
				draw(1, a_temp);
				draw(a_temp, 1);
				draw(a_temp, 2 * a_temp - 1);
				draw(2 * a_temp - 1, a_temp);
			}
			else{
				draw(1, a_temp - (b[i - 3] - 1));
				draw(a_temp - (b[i - 3] - 1), 1);
				draw(a_temp - (b[i - 3] - 1), 2 * a_temp - (2 * b[i - 3] - 1));
				draw(2 * a_temp - (2 * b[i - 3] - 1), a_temp - (b[i - 3] - 1));
			}
		}
		update_temp();
	}
	for(int i = 1; i <= a_pic; ++i){
		for(int j = 1; j <= a_pic; ++j){
			cout << " " << pic[i][j];
		}
		cout << '\n';
	}
	return 0;
}

The Pattern at Each Stage

To show the final results of the algorithm and the beauty of the pattern’s evolution, here are the complete outputs from n=0 through n=6.

Expand/collapse the output for n=0 Output for n=0
Expand/collapse the output for n=1 Output for n=1
Expand/collapse the output for n=2 Output for n=2
Expand/collapse the output for n=3 Output for n=3
Expand/collapse the output for n=4 Output for n=4
Expand/collapse the output for n=5 Output for n=5
Expand/collapse the output for n=6 Output for n=6

Takeaways

  1. Break the operation into steps: The first step in solving this problem is to break the statement’s single complicated operation into two alternating steps with clearer logic that is easier to implement: expansion on odd steps and rearrangement on even steps.
  2. Look for a recurrence: In complicated simulation problems, deriving a closed-form expression directly is often difficult. The breakthrough here was observing and discovering the recurrence that controls pattern size and coordinates—the b[i-3] relationship—which is much more direct than a purely geometric analysis.
  3. Iteration and double buffering: Building the final pattern step by step from the initial state is a dependable way to solve this type of problem. Using pic and temp as a double buffer makes it easy to generate the next stage from the previous one, avoiding conflicts from modifying the data in place.