## IOI '21 P6 - Bit Shift Registers

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
C++

Christopher the engineer is working on a new type of computer processor.

The processor has access to different -bit memory cells (where and ), which are called registers, and are numbered from to . We denote the registers by . Each register is an array of bits, numbered from (the rightmost bit) to (the leftmost bit). For each and each , we denote the -th bit of register by .

For any sequence of bits (of arbitrary length ), the integer value of the sequence is equal to . We say that the integer value stored in a register is the integer value of the sequence of its bits, i.e., it is .

The processor has types of instructions that can be used to modify the bits in the registers. Each instruction operates on one or more registers and stores the output in one of the registers. In the following, we use to denote an operation of changing the value of such that it becomes equal to . The operations performed by each type of instruction are described below.

Instruction Description
Copy the array of bits in register to register . For each , set
Set register to be equal to , where is an array of bits. For each , set
Take the bitwise-AND of registers and , and store the result in register . For each , set if both and are , and set otherwise.
Take the bitwise-OR of registers and , and store the result in register . For each , set if at least one of and are , and set otherwise.
Take the bitwise-XOR of registers and , and store the result in register . For each , set if exactly one of and is , and set otherwise.
Take the bitwise-NOT of register , and store the result in register . For each , set .
Shift all bits in register to the left by , and store the result in register . The result of shifting the bits in register to the left by is an array consisting of bits. For each , if , and otherwise. For each , set .
Shift all bits in register to the right by , and store the result in register . The result of shifting the bits in register to the right by is an array consisting of bits. For each , if , and otherwise. For each , set .
Add the integer values stored in register and register , and store the result in register . The addition is carried out modulo . Formally, let be the integer value stored in register , and be the integer value stored in register before the operation. Let be the integer value stored in register after the operation. If , set the bits of , such that . Otherwise, set the bits of , such that .

Christopher would like you to solve two types of tasks using the new processor. The type of a task is denoted by an integer . For both types of tasks, you need to produce a program, that is a sequence of instructions defined above.

The input to the program consists of integers , each having bits, i.e., . Before the program is executed, all of the input numbers are stored sequentially in register , such that for each the integer value of the sequence of bits is equal to . Note that . All other bits in register (i.e., those with indices between and , inclusive) and all bits in all other registers are initialized to .

Running a program consists in executing its instructions in order. After the last instruction is executed, the output of the program is computed based on the final value of bits in register . Specifically, the output is a sequence of integers , where for each , is the integer value of a sequence consisting of bits to of register . Note that after running the program the remaining bits of register (with indices at least ) and all bits of all other registers can be arbitrary.

• The first task is to find the smallest integer among the input integers . Specifically, must be the minimum of . The values of can be arbitrary.
• The second task is to sort the input integers in nondecreasing order. Specifically, for each , should be equal to the -th smallest integer among (i.e., is the smallest integer among the input integers).

Provide Christopher with programs, consisting of at most instructions each, that can solve these tasks.

#### Implementation Details

You should implement the following procedure:

void construct_instructions(int s, int n, int k, int q)

• : type of task.
• : number of integers in the input.
• : number of bits in each input integer.
• : maximum number of instructions allowed.
• This procedure is called exactly once and should construct a sequence of instructions to perform the required task.

This procedure should call one or more of the following procedures to construct a sequence of instructions:

void append_move(int t, int y)
void append_store(int t, bool[] v)
void append_and(int t, int x, int y)
void append_or(int t, int x, int y)
void append_xor(int t, int x, int y)
void append_not(int t, int x)
void append_left(int t, int x, int p)
void append_right(int t, int x, int p)
void append_add(int t, int x, int y)

• Each procedure appends a , , , , , , , or instruction to the program, respectively.
• For all relevant instructions, , , must be at least and at most .
• For all relevant instructions, , , are not necessarily pairwise distinct.
• For and instructions, must be at least and at most .
• For instructions, the length of must be .

You may also call the following procedure to help you in testing your solution:

void append_print(int t)

• Any call to this procedure will be ignored during the grading of your solution.
• In the sample grader, this procedure appends a operation to the program.
• When the sample grader encounters a operation during the execution of a program, it prints -bit integers formed by the first bits of register (see "Sample Grader" section for details).
• must satisfy .
• Any call to this procedure does not add to the number of constructed instructions.

After appending the last instruction, construct_instructions should return. The program is then evaluated on some number of test cases, each specifying an input consisting of -bit integers . Your solution passes a given test case if the output of the program for the provided input satisfies the following conditions:

• If , should be the smallest value among .
• If , for each , should be the -th smallest integer among .

The grading of your solution may result in one of the following error messages:

• Invalid index: an incorrect (possibly negative) register index was provided as parameter , or for some call of one of the procedures.
• Value to store is not b bits long: the length of given to append_store is not equal to .
• Invalid shift value: the value of given to append_left or append_right is not between and inclusive.
• Too many instructions: your procedure attempted to append more than instructions.

#### Examples

##### Example 1

Suppose . There are two input integers and , each having bit. Before the program is executed, and . All other bits in the processor are set to . After all the instructions in the program are executed, we need to have , which is the minimum of and .

There are only possible inputs to the program:

• Case : ,
• Case : ,
• Case : ,
• Case : ,

We can notice that for all cases, is equal to the bitwise-AND of and . Therefore, a possible solution is to construct a program by making the following calls:

1. append_move(1, 0), which appends an instruction to copy to .
2. append_right(1, 1, 1), which appends an instruction that takes all bits in , shifts them to the right by bit, and then stores the result back in . Since each integer is -bit long, this results in being equal to .
3. append_and(0, 0, 1), which appends an instruction to take the bitwise-AND of and , then store the result in . After this instruction is executed, is set to the bitwise-AND of and , which is equal to the bitwise-AND of and , as desired.
##### Example 2

Suppose . As with the earlier example, there are only possible inputs to the program. For all cases, is the bitwise-AND of and , and is the bitwise-OR of and . A possible solution is to make the following calls:

1. append_move(1,0)
2. append_right(1,1,1)
3. append_and(2,0,1)
4. append_or(3,0,1)
5. append_left(3,3,1)
6. append_or(0,2,3)

After executing these instructions, contains , and contains , which sorts the input.

#### Constraints

• for all

1. ( points)
2. ( points)
3. ( points)
4. ( points)
5. ( points)
6. ( points)

The sample grader reads the input in the following format:

• line :

This is followed by some number of lines, each describing a single test case. Each test case is provided in the following format:

and describes a test case whose input consists of integers . The description of all test cases is followed by a single line containing solely .

The sample grader first calls construct_instructions(s, n, k, q). If this call violates some constraint described in the problem statement, the sample grader prints one of the error messages listed at the end of the "Implementation Details" section and exits. Otherwise, the sample grader first prints each instruction appended by construct_instructions(s, n, k, q) in order. For instructions, is printed from index to index .

Then, the sample grader processes test cases in order. For each test case, it runs the constructed program on the input of the test case.

For each operation, let be a sequence of integers, such that for each , is the integer value of the sequence of bits to of register (when the operation is executed). The grader prints this sequence in the following format:

register :

Once all instructions have been executed, the sample grader prints the output of the program.

If , the output of the sample grader for each test case is in the following format:

• .

If , the output of the sample grader for each test case is in the following format:

After executing all test cases, the grader prints number of instructions: where is the number of instructions in your program.