Problem B
High-speed Signal Equalization

This contest consists of two problems. This problem is about recovering a digital signal.

High-speed interface, as the key part of communication between chips, plays a crucial role in computing, network, wireless, terminal and other fields. Due to the non-ideal characteristics of analog devices and transmission channels in communication links, the received signals of high-speed interfaces are often accompanied by specific impairments. With the continuous evolution of communication rates, in addition to linear impairments, end-to-end communication signals also contain strong nonlinearity and noise. The increasingly complex damage components make the system analysis and algorithm design more complex.

A typical digital signal processing (DSP) assisted PAM4 communication system is shown in Fig. 1. A digital pattern sequence is coded in PAM4 pattern with the symbols [-3,-1,1,3] to represent the 4 levels of a PAM4 signal. After TX DSP, the digital signal is converted to analog waveform using a digital to analog converter (DAC). After transmission by a high speed channel, the analog signal is then received by a receiver. The analog to digital converter (ADC) converts the analog signal to a digital signal. After equalizing and slicing by the RX DSP, the original digital signal from the transmitter is recovered at the receiver.

Figure 1: Modern communication system

The main challenges of this problem are as follow:

1. The damage in the channel is diverse and coupled, which stems from analog/optical device, passive link and active amplification, including noise, insertion loss, nonlinearity, etc. The nonlinearity and noise are amplified in the band-limited channel when the transmission rate is increased.

2. The energy efficiency per bit is reduced with the rapid growth of transmission speed. The architecture faces a severe challenge of power.

In view of the above background, you should perform damage decomposition on the signal, and accurately model and analyze the signal. Under the given input data, the signal waveform is modeled and fitted, and the original data is restored from the analog waveform through the algorithm. In order to match the requirements of low power consumption, delay, and bit error rate in the actual communication system, this contest must be completed within the specified complexity and accuracy.

Task

You are given an analog waveform that comes from a PAM4 signal in a real channel. The waveform is represented as a sequence of double values. Each digital symbol is a unit interval UI. The osr (over sample rate) means the number of samples per UI for the analog waveform. It is always 4 in this task. This means that each UI has 4 samples in the analog waveform. For example, if the waveform length is 4029972 samples, then the number of UIs is $\frac{4029972}{4} = 1007493$.

Your task is to use signal equalization to recover the transmitted symbols from the waveform, then slice them into one of the four possible PAM4 levels: $[3,1,-1,-3]$.

Input

Your program should read input using standard input (stdin).

The first line of input contains the integer $N$, the number of samples in the analog wave.

The next line contains $N$ space-separated real numbers $a_1, a_2, \dots , a_N$, the contents of the analog wave. It is guaranteed that $N$ is divisble by $4$, and that $-1 \leq a_i \leq 1$ for each $1 \leq i \leq N$.

Note that there is a large amount of input data, so you should use an efficient input method to read the data. Documentation on how to do this in your language of choice can be found in https://open.kattis.com/languages.

Your solution will be tested on 8 testcases, whose characteristics are described in the following table. Note that some testcases are worth more points than others, as indicated by the score multiplier. Every testcase is scored the same, and the score is then multiplied by the score multiplier for that testcase.

Output

Your program should write output to standard output (stdout).

First, you should write an integer $L$, the number of samples in your digital signal. This number must be equal to $\frac{N}{4}$, or you will receive the verdict Wrong Answer. The fact that you should output $\frac{N}{4}$ numbers is derived from te fact that the over sampling rate is always 4 in this task.

Then, on the next line, print $L$ space-separated integers, your reconstruction of the digital signal. Each number must be one of $[3,1,-1,-3]$.

Scoring

Your solution will be tested and scored on 8 testcases, which are described above. To prevent overfitting, these testcases are kept hidden.

To receive a score, you must output a digital signal within the time limit. For each testcase, the bit error rate (BER) is computed as follows:

Each testcase is then assigned a score between 0 and 20, with more points awarded for lower BER. This score is then multiplied by the score multiplier for that testcase, as described in the table above. The total score for the problem is the sum of the score for each testcase. If you make multiple submissions, the one with highest total score is the one counted on the scoreboard.

Sample

A sample input and output is shown below. You will not receive a score on it, and it is only meant to illustrate the input and output format. In particular, no inferences about the characteristics of the channel should be made from it, as the analog numbers are chosen uniformly at random in the interval $[-1,1]$. The sample will be run on every submission, and is thus a good way to test that your program works correctly.

8
-0.17512 -0.07281 0.17902 0.38865 -0.84274 0.26491 0.37742 -0.53483

2
3 1