Problem B
Spatial estimation and separation

1 Introduction

In a wireless communication system, spatial separation and estimation are important for many scenarios such as interference suppression and channel estimation. In this problem, target signals and interference signals are combined together, and the former one need to be separated and estimated. The target signals and interference signals are classified based on different spatial features.

The main challenges of this problem are as follow:

1. The number of interference signals can be very high, which means the optimization problem of spatial estimation and separation is non-convex and complicated.

2. The power of target signals and interference signals is comparable, meaning interference significantly impacts target signals.

Compared with traditional optimization problems, this problem has the following two special difficulties:

• Subspace estimation and separation in full-rank space: Because the number of interference signals exceeds the spatial dimension, contestants need to separate target signals based on a full-rank space. In the current baseline solution, subspace separation solution is performed through beam scanning, but weak target signals (power is relatively low) in this full-rank space cannot be effectively separated.

• Subspace estimated precision: In this problem, the estimated precision of the weak target signals and the strong target signals is equally important. However, the estimation of weak target signals is easily affected by the existence of strong interference signals or other target signals. Therefore, High-precision weak target signal estimation is one of the main difficulties in this problem.

This is an interactive problem, and the input of this problem can be changed by the contestants. Contestants should design an optimization method to input different signals to a black box system which can provide corresponding output signals. The target signal subspace need to be separated and estimated by contestants’ algorithms through the processing and analyzing of the input and output data.

Notations: $(\cdot {)}^{\ast }$ denotes the conjugate operation; $(\cdot {)}^T$ denotes the transpose operation $(\cdot {)}^H$ denotes the conjugate transpose operation; ${\Vert \cdot \Vert }_F$ denotes Frobenius norm; ${\mathbb{C}}^{M\times N}$ represents the $M\times N$ dimension matrix spaces with complex entries. $\{1,...,X\}$ represents a set containing integers from 1 to $X$. Assume there is a matrix $\mathrm{V}$, $\mathrm{V}[1:X,:]$ denotes 1 to $X$ rows and all columns of matrix $\mathrm{V}$.

2 System Model

All signal systems, whether they are target signals or interference signals, have the same structure (linear-nonlinear-linear).The differences in linear layer characteristics of these signals distinguish the target signals from the interference signals. Therefore, the signal models described in 2.1 and 2.2 are applicable to both target and interference signals. 2.3 provides the description of differences between target signals and interference signals.

2.1 Single Signal System Model

System model of single signal is modelled as shown in Figure 1. It consists of input modules, linear system modules, generate data modules, nonlinear module, and output module. The linear system modules, generate data modules, and nonlinear system module are embedded in the Kattis platform as a black box system. Input modules and output module are visible to the contestants’ program.

Input modules: The input data weights ${\mathrm{W}}_1\in {\mathbb{C}}^{N_{Tx}\times N_{stream,1}}$ and ${\mathrm{W}}_2\in {\mathbb{C}}^{N_{Tx}\times N_{stream,2}}$ can be modified by contestants, $N_{stream,1}$, $N_{stream,2}\in \{1,...,N_{Tx}\}$. The elements of ${\mathrm{W}}_1$ and ${\mathrm{W}}_2$ and the values of $N_{stream,1}$ and $N_{stream,2}$ are all changeable for contestants.

Black box system: None of the modules in black box system are visible for the contestants.

When dealing with different numbers of $N_{stream,1}$ and $N_{stream,2}$, ${\mathrm{S}}_1\in {\mathbb{C}}^{N_{stream,1}\times N_{data}}$ and ${\mathrm{S}}_2\in {\mathbb{C}}^{N_{stream,2}\times N_{data}}$ are as follow:

$${\mathrm{S}}_1={\mathrm{S}}_1^{all}[1:N_{stream,1},:]$$$${\mathrm{S}}_2={\mathrm{S}}_2^{all}[1:N_{stream,2},:]$$

where ${\mathrm{S}}_1^{all}\in {\mathbb{C}}^{N_{Tx}\times N_{data}}$ and ${\mathrm{S}}_2^{all}\in {\mathbb{C}}^{N_{Tx}\times N_{data}}$ are fixed (but unknown) for all the contestants. The generated data matrices ${\mathrm{X}}_1$ and ${\mathrm{X}}_2$ can be written as

$${\mathrm{X}}_1={\alpha }_1{\mathrm{W}}_1^{\ast }\times {\mathrm{S}}_1,{\mathrm{X}}_1\in {\mathbb{C}}^{N_{Tx}\times N_{data}}$$$${\mathrm{X}}_2={\alpha }_2{\mathrm{W}}_2^{\ast }\times {\mathrm{S}}_2,{\mathrm{X}}_2\in {\mathbb{C}}^{N_{Tx}\times N_{data}}$$

where ${\alpha }_i=\sqrt{\frac{N_{Tx}}{N_{stream,i}}},i\in \{1,2\}$. We call linear layer ${\mathrm{H}}_1\in {\mathbb{C}}^{1\times N_{Tx}}$ and linear layer ${\mathrm{H}}_2\in {\mathbb{C}}^{1\times N_{Tx}}$ as downlink channels, and linear layer ${\mathrm{H}}_3\in {\mathbb{C}}^{N_{Rx}\times 1}$ as uplink channel. Signals ${\mathrm{X}}_1$ and ${\mathrm{X}}_2$ pass through ${\mathrm{H}}_1$ and ${\mathrm{H}}_2$:

$${\mathrm{m}}_1={\mathrm{H}}_1\times {\mathrm{X}}_1,{\mathrm{m}}_1\in {\mathbb{C}}^{1\times N_{data}}$$$${\mathrm{m}}_2={\mathrm{H}}_2\times {\mathrm{X}}_2,{\mathrm{m}}_2\in {\mathbb{C}}^{1\times N_{data}}$$

The nonlinear system is defined by a third-order nonlinear function $f(.)$.

$$\mathrm{p}[1,n]=f({\mathrm{m}}_1[1,n],{\mathrm{m}}_2[1,n])={\mathrm{c}}_{\mathrm{nlin},n}{({\mathrm{m}}_1[1,n])}^2{({\mathrm{m}}_2[1,n])}^{\ast },n\in \{1,...,N_{data}\}$$

where ${\mathrm{c}}_{\mathrm{nlin},n}$ is the nonlinear coefficient. The output of nonlinear system module is $\mathrm{p}\in {\mathbb{C}}^{1\times N_{data}}$.

Output module:The nonlinear signal then propagates through uplink channel ${\mathrm{H}}_3\in {\mathbb{C}}^{N_{Rx}\times 1}$, and output signal $\mathrm{Y}$ is obtained.

$$\mathrm{Y}={\mathrm{H}}_3\times \mathrm{p},\mathrm{Y}\in {\mathbb{C}}^{N_{Rx}\times N_{data}}$$

Output signal $\mathrm{Y}$ is visible for the contestants’ program. None of other information in the box black system is visible.

2.2 Multiple Signals System Model

System model of multiple signals is shown in Figure 2. $N_i$ represents the total number of signals. The Input modules and the output module are the same as single signal system model. The differences are centered at the black box system.

Black box system (multiple signals): The generate data modules are the same as the single signal system model.

$${\mathrm{X}}_1={\alpha }_1{\mathrm{W}}_1^{\ast }\times {\mathrm{S}}_1,{\mathrm{X}}_1\in {\mathbb{C}}^{N_{Tx}\times N_{data}}$$$${\mathrm{X}}_2={\alpha }_2{\mathrm{W}}_2^{\ast }\times {\mathrm{S}}_2,{\mathrm{X}}_2\in {\mathbb{C}}^{N_{Tx}\times N_{data}}$$

The differences come in the latter modules. Multiple signals mean that the linear-nonlinear-linear system has many branches. $N_i$ represents the branch number. The generated data flows into different branches. Linear system $1,1$ to Linear system $1,N_i$ represent the downlink channels of signal 1 to $N_i$ for input1 signal. Linear system $2,1$ to Linear system $2,N_i$ represent the downlink channels of Signal 1 to $N_i$ for input2 signal.

Input1:

$$\begin{array}{cc}{\mathrm{m}}_{1,1}={\mathrm{H}}_{1,1}\times {\mathrm{X}}_1,& {\mathrm{m}}_{1,1}\in {\mathbb{C}}^{1\times N_{data}}\\ ⋮& \\ {\mathrm{m}}_{1,N_i}={\mathrm{H}}_{1,N_i}\times {\mathrm{X}}_1,& {\mathrm{m}}_{1,N_i}\in {\mathbb{C}}^{1\times N_{data}}\end{array}$$

Input2:

$$\begin{array}{cc}{\mathrm{m}}_{2,1}={\mathrm{H}}_{2,1}\times {\mathrm{X}}_2,& {\mathrm{m}}_{2,1}\in {\mathbb{C}}^{1\times N_{data}}\\ ⋮& \\ {\mathrm{m}}_{2,N_i}={\mathrm{H}}_{2,N_i}\times {\mathrm{X}}_2,& {\mathrm{m}}_{2,N_i}\in {\mathbb{C}}^{1\times N_{data}}\end{array}$$

Signals ${\mathrm{m}}_{1,a}$ and ${\mathrm{m}}_{2,a},a\in \{1,...,N_i\}$ pass through the corresponding nonlinear system which can be also indicated as a third-order nonlinear function $f_a(.)$. Each signal $a$ has its own nonlinear process and corresponding ${\mathrm{p}}_a$.

$${\mathrm{p}}_a[1,n]=f_a({\mathrm{m}}_{1,a}[1,n],{\mathrm{m}}_{2,a}[1,n])[1,n]={\mathrm{c}}_{\mathrm{nlin},a,n}{({\mathrm{m}}_{1,a}[1,n])}^2{({\mathrm{m}}_{2,a}[1,n])}^{\ast },\mathrm{n}\in \{1,...,N_{data}\}]$$

where ${\mathrm{c}}_{\mathrm{nlin},a,n}$ is the nonlinear coefficient of signal $a$. Different signals have different values of nonlinear coefficients. Nonlinear signals go through corresponding uplink channels ${\mathrm{H}}_{3,1}\in {\mathbb{C}}^{N_{Rx}\times 1}$ to ${\mathrm{H}}_{3,N_i}\in {\mathbb{C}}^{N_{Rx}\times 1}$ afterwards.

$$\begin{array}{cc}{\mathrm{Y}}_1={\mathrm{H}}_{3,1}\times {\mathrm{p}}_1,& {\mathrm{Y}}_1\in {\mathbb{C}}^{N_{Rx}\times N_{data}}\\ ⋮& \\ {\mathrm{Y}}_{N_i}={\mathrm{H}}_{3,N_i}\times {\mathrm{p}}_{N_i},& {\mathrm{Y}}_{N_i}\in {\mathbb{C}}^{N_{Rx}\times N_{data}}\end{array}$$

The output $\mathrm{Y}$ is the sum of ${\mathrm{Y}}_1$ to ${\mathrm{Y}}_{N_i}$.

$$\mathrm{Y}={\mathrm{Y}}_1+{\mathrm{Y}}_2+\cdots +{\mathrm{Y}}_{N_i},\mathrm{Y}\in {\mathbb{C}}^{N_{Rx}\times N_{data}}$$

The contestants’ program can choose the input data weights ${\mathrm{W}}_1$ and ${\mathrm{W}}_2$,and observe the resulting received signal Y. All other information is hidden in the platform.

In summary, the entirety of the system modeling can be represented by the following formula

$$\mathrm{Y}=\left[\begin{array}{lll}{\mathrm{H}}_{3,1}& \dots & {\mathrm{H}}_{3,N_{\mathrm{i}}}\end{array}\right]\times f(\left[\begin{array}{c}{\mathrm{H}}_{1,1}\\ \dots \\ {\mathrm{H}}_{1,N_{\mathrm{i}}}\end{array}\right]\times {\mathrm{X}}_1,\left[\begin{array}{c}{\mathrm{H}}_{2,1}\\ \dots \\ {\mathrm{H}}_{2,N_{\mathrm{i}}}\end{array}\right]\times {\mathrm{X}}_2)$$

The total $N_i$ signals can be divided into $N_{tar}$ target signals and $N_{intf}$ interference signals ($N_i=N_{tar}+N_{intf}$). For convenience, the first $N_{tar}$ number of branches are set as the target signals’ branches, which means ${\mathrm{H}}_{\{1,2,3\},\{1,...,N_{tar}\}}$ are all corresponding to the $N_{tar}$number of target signal,

2.3 Signal categories

Signals can be divided into two categories (target and interference) according to different spatial characteristics (different linear system characteristics).

${\mathrm{H}}_{\mathrm{downlink},1}$ and ${\mathrm{H}}_{\mathrm{downlink},2}$ represents the characteristics of ${\mathrm{H}}_{1,\mathrm{i}}$ and ${\mathrm{H}}_{2,\mathrm{i}}$ respectively, where $\mathrm{i}\in \{1,...,N_{\mathrm{i}}\}$. ${\mathrm{H}}_{\mathrm{uplink}}$ represents the characteristics of ${\mathrm{H}}_{3,\mathrm{i}}$ , where $\mathrm{i}\in \{1,...,N_{\mathrm{i}}\}$.

Target Signal: For each target signal (so the ${\mathrm{H}}_{\mathrm{downlink},1},{\mathrm{H}}_{\mathrm{downlink},2}\in {\mathbb{C}}^{1\times N_{Tx}}$, ${\mathrm{H}}_{\mathrm{uplink}}\in {\mathbb{C}}^{N_{Rx}\times 1}$), the downlink channels and the uplink channel are characterized by the following features.

$$\begin{array}{rlrl}{\mathrm{H}}_{\mathrm{downlink},1}[1,t]& ={\mathrm{x}}_{t,1},& & t\in \{1,...,N_{Tx}\}\\ {\mathrm{H}}_{\mathrm{downlink},2}[1,t]& ={\mathrm{x}}_{t,2},& & t\in \{1,...,N_{Tx}\}\\ {\mathrm{H}}_{\mathrm{uplink}}[r,1]& ={\mathrm{x}}_r,& & r\in \{1,...,N_{Rx}\}\end{array}$$

${\mathrm{x}}_{t,1}$,${\mathrm{x}}_{t,2}$ and ${\mathrm{x}}_r$ are different complex values, which are all nonzero (The squared norm of some values are order of ${10}^{-1}$, and square norm of others are in the range of ${10}^{-5}$ to ${10}^{-2}$). This can be called as ’mult-connection’ features which is shown in Figure 3. We call this category of signal “nTnR target signal”.

Interference category: The downlink channels and the uplink channel for one of this category of interference signals are characterized by the following features.

$$\begin{array}{rlrl}{\mathrm{H}}_{\text{downlink,1 }}[1,j]& =h,& & {\mathrm{H}}_{\text{downlink,1 }}[1,i]=k,i\in \{1,...,N_{Tx}\}\mathrm{\setminus }j\\ {\mathrm{H}}_{\text{downlink,2 }}[1,j]& =h,& & {\mathrm{H}}_{\text{downlink,2 }}[1,i]=k,i\in \{1,...,N_{Tx}\}\mathrm{\setminus }j\\ {\mathrm{H}}_{\mathrm{uplink}}[j,1]& =h,& & {\mathrm{H}}_{\mathrm{uplink}}[i,1]=k,i\in \{1,...,N_{Rx}\}]\mathrm{\setminus }j\end{array}$$

where $j\in \{1,...,N_{Tx}\}$,${\left|h\right|}^2\to 1$,${\left|k\right|}^2\to 0$(order of ${10}^{-9}$), and $\mathrm{\setminus }j$ means except $j$. No two interference signals have the same $j$. The downlink channels and the uplink channel of one interference signal must have the same index $j$. All of the downlink and uplink channels for interference signals have the single-connection features as shown in Figure 4. We call this category of interference signal“1T1R interference signal”.

Contestants are supposed to utilize the connection features of these target and interference signals to reach the goal of this challenge, which is high-accuracy target signal subspace separation and estimation.

More precisely, contestants need to accurately separate and estimate the subspace of downlink channels ${\mathrm{H}}_{1,1}$ to ${\mathrm{H}}_{1,N_{tar}}$ (where $N_{tar}$ presents the number of target signals) corresponding to signal ${\mathrm{X}}_1$ of each target signal. The final accuracy is judged by the null space projection residual which is described in section 5.

3 Constraint

$$\begin{array}{c}{N}_{Tx}=N_{Rx}=32\\ N_{\text{data }}=300\\ 0\le N_i\le 42\\ N_{\text{stream }1}\le N_{Tx}\\ N_{\text{stream }2}\le N_{Tx}\\ 0\le N_{tar}\le 10\\ {\mathrm{c}}_{a,\text{ nlin }}\in \mathbb{C}\\ {\Vert {\mathrm{S}}_1[i,j]\Vert }^2=1,i\in \{1,...,N_{stream,1}\},j\in \{1,...,N_{data}\}\\ {\Vert {\mathrm{S}}_2[i,j]\Vert }^2=1,i\in \{1,...,N_{stream,2}\},j\in \{1,...,N_{data}\}\\ {\Vert {\mathrm{W}}_1\Vert }_F^2=1\\ {\Vert {\mathrm{W}}_2\Vert }_F^2=1\\ {\Vert {\mathrm{H}}_{a,b}\Vert }_F^2=1,a\in \{1,2,3\},b\in \{1,...,N_{\mathrm{i}}\}\end{array}$$

Any value of the square of Norm can bear error between ±0.001.

Your program can make at most 2000 queries to the black box system per case.

Hint: all the constraints are validated, so please adhere to all of them. Violating the constraints will result in a verdict of Wrong Answer.

4 Optimization Objective

Based on the foregoing system model, contestants are expected to solve the following cases:

$$\overline{)\begin{array}{ccc}& 1\mathrm{T}1\mathrm{R}\text{ interference }& \text{ nTnR target signal }\\ \text{ CASE1 }& 0\le N_{intf}\le 10& 0\le N_{tar}\le 10\\ \text{ CASE2 }& 0\le N_{intf}\le 10& 0\le N_{tar}\le 10\\ \text{ CASE3 }& N_{intf}=32& 0\le N_{tar}\le 10\\ \text{ CASE4 }& N_{intf}=32& 0\le N_{tar}\le 10\end{array}}$$

Spatial separation and estimation problems of above four cases should be solved universally by contestants’ algorithm. Different cases have different number of signals (system branches): $N_i=N_{intf}+N_{tar}$.

The ideal channel matrices are defined as below. Some channels are correlated, with some being highly correlated.

$$\begin{array}{c}{\mathrm{H}}_{1,\text{ideal}}=\left[\begin{array}{c}{\mathrm{H}}_{1,1}\\ \dots \\ {\mathrm{H}}_{1,N_{tar}}\end{array}\right]\end{array}$$

The estimated downlink channel subspace for all target signals should be written as below.

$$\begin{array}{c}{\mathrm{L}}_{\text{est }}=\left[\begin{array}{c}{\mathrm{L}}_{\mathrm{e},1}\\ \dots \\ {\mathrm{L}}_{\mathrm{e},N_{tar}}\end{array}\right],{\mathrm{L}}_{\text{est }}\in {\mathbb{C}}^{N_{tar}\times N_{Tx}}\end{array}$$

The constraints of ${\mathrm{L}}_{\text{est }}$ are

$$\begin{array}{c}{\Vert {\mathrm{L}}_{\text{e,i }}\Vert }_F^2=1,\text{i}\in \{1,...,N_{tar}\}\\ rank({\mathrm{L}}_{\text{est }})=N_{tar}\end{array}$$

Violating the constraints will result in a verdict of Wrong Answer.

Because for each case, the $N_{tar}$ is different. The contestants’ program should estimate the exact value of $N_{tar}$ first. Otherwise, the dimension of ${\mathrm{L}}_{\text{est }}$ will not match the dimension of ${\mathrm{H}}_{\text{ideal,downlink,1 }}$.

5 Score calculation

To evaluate the accuracy of the estimated subspace, first obtain the null space projection matrix ${\mathrm{D}}_{\text{null }}$ of estimated subspace ${\mathrm{L}}_{\text{est }}$.

$$\begin{array}{c}{\mathrm{L}}_{\text{est,t }}={\mathrm{L}}_{\text{est }}^T\\ {\mathrm{D}}_{\text{null }}=\mathrm{I}-{\mathrm{L}}_{\text{est,t }}{\left({\mathrm{L}}_{\text{est,t }}^H{\mathrm{L}}_{\text{est,t }}\right)}^{-1}{\mathrm{L}}_{\text{est,t }}^H\end{array}$$

Then compute the projection residual of the ideal subspace

$${\mathrm{L}}_{proj,resid}={\mathrm{D}}_{\text{null }}{\mathrm{H}}_{\text{ideal,downlink,1 }}^T$$

The average projection residual power can be written as

$${\mathrm{P}}_{resi}=\frac{{\Vert {\mathrm{L}}_{proj,resid}\Vert }_F^2}{N_{tar}}$$

The full score is 100, and four cases’ score need to be summed up to obtain the final score. Each case’s sorce can be written as

$${\mathrm{Score}}_s=M_s\times (1-{\mathrm{P}}_{resi}),s\in \{\mathrm{CASE}1,...,\mathrm{CASE}4\}$$

where $M_{\mathrm{CASE}1}=15,M_{\mathrm{CASE}2}=20,M_{\mathrm{CASE}3}=30,M_{\mathrm{CASE}4}=35$.The full score is written as

$$M_{fullScore}=M_{\mathrm{CASE}1}+M_{\mathrm{CASE}2}+M_{\mathrm{CASE}3}+M_{\mathrm{CASE}4}=100$$

6 Program Structure

The main interaction program structure is shown in Figure 5. The detailed steps are described in this section. A simple demo code about this whole process is in the attachment (at the end of this statement).

The / means no input or output in this step.

Hint: Please don’t forget to flush the output. This will result in a Time Limit Exceeded.

Step 0: The black box system (The kattis platform starts from here, so this step is necessary.):

[input: / ]
[output: ’Start’]

Step 1: Contestant program(Interaction Start):

[input: ’Start’ ]
[output: ${\mathrm{W}}_1\in {\mathbb{C}}^{N_{Tx}\times N_{stream,1}}$, ${\mathrm{W}}_2\in {\mathbb{C}}^{N_{Tx}\times N_{stream,2}}$]

$N_{Tx}$ is a constant of 32. $N_{stream,1}$ and $N_{stream,2}$ can be chosen from $\{1,...,N_{Tx}\}$ (These two values can be changed between each iteration). Size of output matrices is $32\times N_{stream,1}$ and $32\times N_{stream,2}$.

The interaction data has to be a string. Hence ${\mathrm{W}}_1$ and ${\mathrm{W}}_2$ both need to be converted to a string. (See detail in the demo code!)

Step 2: The black box system (Interaction continue):

[input:${\mathrm{W}}_1\in {\mathbb{C}}^{N_{Tx}\times N_{stream,1}}$, ${\mathrm{W}}_2\in {\mathbb{C}}^{N_{Tx}\times N_{stream,2}}$]
[output: $\mathrm{Y}\in {\mathbb{C}}^{N_{Rx}\times N_{data}}$]

$N_{Rx}$ is a constant of 32 and $N_{data}$ is a constant of 300. Size of output matrix is $32\times 300$. Same as Step 1, the output Y is a string when fed into the contestants’ program.

Step 3: Contestant program(Whether interaction end?):

the input Y must be read from a string and be converted to a matrix.

[input: $\mathrm{Y}\in {\mathbb{C}}^{N_{Rx}\times N_{data}}$]

If the interaction continue, ${\mathrm{W}}_1$ and ${\mathrm{W}}_2$ need to be output again. Go back to Step 2.

[output: ${\mathrm{W}}_1\in {\mathbb{C}}^{N_{Tx}\times N_{stream,1}}$, ${\mathrm{W}}_2\in {\mathbb{C}}^{N_{Tx}\times N_{stream,2}}$]

If the interaction end, contestants need to output a sign to tell black box system. Continue to Step 4.

[output:’END’]

Step 4: The black box system(Interaction end):

[input:’END’]
[output:’Roger that’]

Step 5: Contestant program (Interaction end) :

[input:’Roger that’]
[output: ${\mathrm{L}}_{\text{est }}\in {\mathbb{C}}^{N_{tar}\times N_{Tx}}$]

${\mathrm{L}}_{\text{est }}$ is the estimated downlink channel subspace. $N_{tar}$ can be $\{1,...,10\}$. Size of output matrix is $N_{tar}\times 32$. This output matrix also need to be converted to a string.

Step 6: The black box system (Calculate the score) :

[input: ${\mathrm{L}}_{\text{est }}\in {\mathbb{C}}^{N_{tar}\times N_{Tx}}$]
[output: Display Score ]

The accuracy of the estimated downlink channel can be evaluated in this step. The score should be shown to the contestants.

7 Evaluation Criteria

The solutions of contestants are evaluated as follows:

1. The estimation accuracy of downlink channels of each target signals.

2. The complexity of the solution is an evaluation criteria in Round 2. Please minimize the complexity of the algorithm as much as possible.