Homework 03 - HackMD

--- tags: homework title: Homework 03 --- # Homework 3 ## TA information > Contact with TAs if having any problems. * 莊博傑 Po-Chieh Chuang / 40747019s@gapps.ntnu.edu.tw * 林育辰 Yu-Chen Lin / 40771131h@gapps.ntnu.edu.tw --- # Learning and forgetting > [name=Yu-Chen Lin] ## Description #### Previously *Salmon Liou*, a senior high school student, and he always binge-watched drama at home. Such as "[Scarlet Heart](https://en.wikipedia.org/wiki/Scarlet_Heart)"、"[Moon Embracing the Sun](https://en.wikipedia.org/wiki/Moon_Embracing_the_Sun)". Furthermore, he also a game lover, such as play an RPG "[SoulSpace](https://forum.gamer.com.tw/C.php?bsn=4918&snA=15026)". He trashed his "[General Scholastic Ability Test](https://en.wikipedia.org/wiki/General_Scholastic_Ability_Test)" maybe. Of course, this is outside the scope of our problem inquiry. Salmon traveled back in the “Moon Embracing world the Sun” world one day, and then a story is about to begin. #### Adoptive mother - Jang Nok-young Salmon Liou is equipped with magical abilities. Jang Nok-young, his adoptive mother, is the head shaman of the country. She say: 「There are thirty kinds of spells, like "black spell", "fireball spell", and I teach three spells to you today, and another three spells the next day. MUST obey the "learning rule", or you will die.」 Rule: 1. unable \==(teach)==> enable 2. enable \==(teach)==> unable #### Gaffer *Salmon* meet up with a gaffer and learned a rule: 1. enable \==(teach)==> enable 2. unable \==(teach)==> enable 3. enable \==(forget)==> unable 4. unable \==(forget)==> unable #### Loyal bodyguard - Kim Jae-woon *Salmon* participates in a martial art test, ranking in the top 1. He take *Kim Jae-woon* as one's teacher learned a rule: 1. enable \==(teach)==> enable 2. "Martial art" value equal to the summation of skill points, and the skill points is $2^{\ (the \ skill \ number)}$ #### Task Help *Salmon* to finish those tasks: 1. Adoptive mother: She teaches three skills to *Salmon*, and another three skills the next day. How much is the number of learned skills base on her rules? 2. Gaffer: He teaches three skills to *Salmon*, and requires *Salmon* to forget three skills. How much is the number of learned skills base on the Gaffer rules? 3. Loyal bodyguard: He teaches three skills to *Salmon*, How much is the "martial arts value"? ![](https://i.imgur.com/YVK0HS8.png) If these tasks finished, he would return his "original" name. ## TestCase Explanation Skill $S_i$ is a positive integer, range from zero to thirty (close interval). Line 1: Adoptive mother taught three skills $S_1, \, S_2, \, S_3$ in order. Line 2: Adoptive mother taught another three skills $S_1, \, S_2, \, S_3$ in order. First, you should print the number of learned skills $A_1$ in one line. Line 3: Gaffer taught three skills $S_4, \, S_5, \, S_6$ in order. Line 4: Gaffer requires you to forget three skills. Second, should print the number of learned skill $A_2$ in one line. Line 5: The loyal bodyguard taught you three skills $S_{13}, \, S_{14}, \, S_{15}$ in order. Finally, should print the "martial art value" in one line. IMPORTANT: DON'T calculates the repeat skill. #### Subtasks | | Limits | Score | | --------- |:------ | -----:| | #0 |* $\{S_1, S_2, S_3\} \cap \{S_4, S_5, S_6\} = \emptyset$, * $\{S_7, S_8, S_9\} \cap \{S_{10}, S_{11}, S_{12}\} = \emptyset$, * $S_{13}=S_{14}=S_{15} = 1$, * $0 \leq S_i \leq 10$ | $35$ | | #1 |* $\{S_7, S_8, S_9\} \cap \{S_{10}, S_{11}, S_{12}\} = \emptyset$, * $S_{13}=S_{14}=S_{15} = 1$, * $0 \leq S_i \leq 10$ | $25$ | | #2 | * $\{S_7, S_8, S_9\} \cap \{S_{10}, S_{11}, S_{12}\} = \emptyset$ | $25$ | | #3 | Following the “limits” block conditions only. | $15$ | | **Total** | | $100$ | ## Input $\text{Line 1:} \ \ S_1 \ S_2 \ S_3$\ $\text{Line 2:} \ \ S_4 \ S_5 \ S_6$\ $\text{Line 3:} \ \ S_7 \ S_8 \ S_9$\ $\text{Line 4:} \ \ S_{10} \ S_{11} \ S_{12}$\ $\text{Line 5:} \ \ S_{13} \ S_{14} \ S_{15}$ The consecutive numbers separated with space, ending with a newline character. **limit** * $0 \leq S_i \leq 30, \ S_i \in \mathbb{N}$ ## Output Output three lines totally. Each line contains one integer only, ending with a newline character. DON'T include any space character. $\text{Line 1:}$ an integer $A_{1}$\ $\text{Line 2:}$ an integer $A_{2}$\ $\text{Line 3:}$ an integer $A_{3}$ Number range is legal below: * $0 \leq A_1 \leq 6$ * $0 \leq A_2 \leq 3$ * $0 \leq A_3 \leq 2^{31}-1$ ## Example Input 3 5 3 6 9 5 10 30 15 30 20 10 3 5 7 ## Example Output 2 1 168 ## Hint * The bitwise operation is necessary, like XOR(`^`), OR(`|`), AND(`&`), etc. * You should focus on the example and those rules, rather than the story. * The bitwise operation as shift operation (`<<`) and OR(`|`) could compute the martial art value. **Explain** 1. Line `1` `2` * Learned the skills $3, 5, 3$, and the second 3 is "learned", so you should forget it. So, you only learned skill 5 NOW. * Learned the skills $6, 9, 5$, and the number 5 is "learned", so you forget it. Finally, you learned the skills $6, 9$, print $2$, that is the number of learned skills. 2. Line `3` `4` * Gaffer taught the skills $10, 30, 15$. * Gaffer requires you to forget the skills $30, 20, 10$, and you forget the skills $10$. Finally, you learned the skill $15$ only, print $1$. 3. Line `5` * The loyal bodyguard taught three skills $3, 5, 7$, and those points are $2^3, 2^5, 2^7$. However, the martial art value is summarize all skill points = $8 + 32 + 128 = 168$, print $168$ ## Problem-Solving idea * If you want to `1` change to `0` and `0` change to `1`, the XOR operation is needed. * `~` is **NOT operation** in C language, it can change `0110` to `1001`. * Any bit and `0` do the AND operation, it can force the original bit to zero. Using the information and NOT operation, you could forget some skills. * The $2^x$ can be calculated by `1 << x`. ---  ## Number Steganography > [name=Yu-Chen Lin] ### Description Steganography is the practice of concealing a file, message, image, or video within another file, message, image, or video. In this problem, I want you to implement a simple number hiding program. The concept is simple. Given a number $X$, and a integer $n$ is an array size, then the array like $[Y_1, \ Y_2, \ Y_3, \ \cdots, \ Y_n]$. To embed a secret number $X$ in each number of the array, you just replace the least significant bits with the secret number bit, as shown in this figure. ![](https://i.imgur.com/p9kEm1T.png) Since we don't want to affect the original number too much, the embedding order is from LSB to MSB. Now I want you to embed and extract a secret number $X$ in/from a given array $Y$. * Given $X$, represent the secret number, and an integer $n$ is the array size. * Next, given the array context from $Y_1$ to $Y_n$, and limits this number range is $0 \leq Y_i \leq 2^{31} -1$ * Then given $b$, represent we would embed $X$ in the $b$ bits from LSB to MSB. If $X$'s bit hide in the array, and the bit would initialize to zero. In this figure, the secret number is all hiding in those three numbers, therefore, the secret number $X$ would initialize to zero. If the array size is 2, we only hide $4$ bits(`1001`) into the array, those bits initialize to zero, so the $X = (000010)_2$. * Finally, given $a$ is the number of the extract bits. In contrast, to embed operation, you should reverse the embed operation to extract the original number. However, $a \neq b$ is allowed, which we wouldn't extract the original number, and then $a$ equal to $b$ means that we would extract the original number. ![](https://i.imgur.com/va3XlLd.png) For example, given: * $X=(1001011)_2, \ n = 3$ * $Y = [(1100001)_2, (11011011)_2, (10)_2]$ * $b = 2, \ a = 2$ #### Hiding the secret number $X$ Then, X from MSB to LSB to embed in the array $Y$ number(from LSB to MSB). * $X=(0000001)_2$ > embed in $6$ bits * $Y = [(1100001)_2, (11011010)_2, (10)_2]$ #### Extact from the array to get original number * $Y = [(1100001)_2, (11011010)_2, (10)_2]$ * $X=(0000001)_2$, (Since the original bit `1` exist, so we recover from **second** bit to MSB) Then the $X = (1001011)_2$ #### Change the $a$ to `3` > How to extract the number from array? > case: $a \neq b$ * $Y = [(1100001)_2, (11011010)_2, (10)_2]$ ==> $[(1100001)_2, (11011010)_2, (010)_2]$ * $X = (0000001)_2$ ==> $(0000000001)_2$ ==> $(1000100101)_2$ #### Case: $a = 2, \ b = 5$ > How to embed this in array? * $X=(1001011)_2$, embed in $15$ bits ==> $X=(100101100000000)_2$ ==> $(000000000000000)_2$ * $Y = [(1100001)_2, (11011010)_2, (10)_2]$==> $[(1100001)_2, (11011010)_2, (00010)_2]$ ==>$[(1101001)_2, (11000011)_2, (00000)_2]$ ### Input Line 1: two integers $X$, $n$, split with space. Line 2: $n$ integers, represent the $[Y_1, \ Y_2, \ Y_3, \ \cdots, \ Y_n]$. Line 3: integer $b$, that is the number of replacing bits. Line 4: integer $a$, that is the number of extract bits from each number of the array. #### Limits * $X, \ n, \ a, \ b \in \mathbb{N}$ * $2^{31}-1 \geq X \geq 0$ * $0 \leq n \times b \leq 31$ * $0 \leq n \times a \leq 31$ #### Subtasks | | Limits | Score | | --------- |:------ | -----:| | #0 | $a=b=1, \ 0 < n < 4$ | 35 | | #1 | $a=b < 4, \ 0 < n < 4$ | 25 | | #2 | $a < 4, \ b < 4$ | 20| | #3 | Following the “limits” block conditions only. | $20$ | | **Total** | | $100$ | ### Output After **hiding operation**. * Line 1: print the $X$. * Line 2: print each number in the array Y, and the consecutive numbers separated with space, ending with a newline characrter. After **extracting operation**. * Line 3: print the $X$. ### Sample Input 0 ``` 75 3 97 219 2 2 2 ``` ### Sample Output 0 ``` 1 97 218 2 75 ``` ### Sample Input 1 ``` 75 3 97 219 2 2 3 ``` ### Sample Output 1 ``` 1 97 218 2 549 ``` ### Sample Input 2 ``` 75 3 97 219 2 5 2 ``` ### Sample Output 2 ``` 0 105 195 0 44 ``` ### Hint * The problem is modified from [Po-Wen Chi Hw04](https://drive.google.com/file/d/1wR6JgcrcG2j4bJBVQgsYn5oot0DKE5nz/view), thanks to him so much! ### Problem-solving Ideas * Implement a function to compute the MSB position, for example, given `100010`, return `6` since the number has six bits. * Implement a function to do the **fetch** operation. Given a bit position and a number, it would return the bit value, furthermore, a **change** bool value helps you to initialize the bits. * If you fetch a bit, notice the right shift operation is needed. For example, the number `10010`, we want to fetch the second bits from LSB to MSB, so the formula "10010 & 00010 = 00010", and the right shift 1 bits to get "1". * Implement a function have four-parameter `(int32_t *x, int32_t arr[], int32_t n, int32_t b)`, n is the arr size, and the b just as the problem description. There is nested loop maybe, outer-loop is from 0 to n, inter-loop is from 1 to n, and to do the fetch and replace operation. * extract is like the embed function, just to reverse the embed function doing. * Check the x MSB position, whether greater equal than n * b? * OR, AND, NOT, the Shift operation is needed. And the shift operation is IMPORTANT! --- ## Maximize it! (20%) > [name=Bogay] ### Description Give you one integer $c$, find 2 integer $a, b$ that satisfy $a \oplus b = c$ and maximize $a \times b$. For example, given $c=7$, we can find $a=3, b=4$ will make $a \times b$ largest. ### Input One integer $c$. #### Limits * $0 \le a,b,c \le 2^{31}-1$ * $a \le b$ * $|\text{bin}(a)|, |\text{bin}(b)| \le |\text{bin}(c)|$ $|\text{bin}(n)|$ is minimum bits that required to represent $n$, e.g., $|\text{bin}(3)| = 2 \because 3 = (11)_2$ #### Subtasks | | Limits | Score | | --------- |:---------------- | -----:| | #0 | $c \le 10^2$ | $45$ | | #1 | $c \le 10^4$ | $30$ | | #2 | $c \le 10^6$ | $15$ | | #3 | No other limits. | $10$ | | **Total** | | $100$ | ### Output Print 2 integer $a, b$, seperated by single space. ### Sample Input 0 ``` 7 ``` ### Sample Output 0 ``` 3 4 ``` ### Sample Input 1 ``` 1000000 ``` ### Sample Output 1 ``` 524287 572863 ``` ### Sample Input 2 ``` 4096 ``` ### Sample Output 2 ``` 4095 8191 ``` ### Sample Input 3 ``` 2147483647 ``` ### Sample Output 3 ``` 1073741823 1073741824 ``` ### Hint * $a \times b$ may larger than $2^{31} - 1$ ### Problem-solving Ideas For $i\text{-th}$ bit of $c$, called it $c_i$, it's value is from $a_i \oplus b_i$. There are 2 cases: 1. $c_i = 0$ In this case, $(a_i, b_i)$ will be either $(1, 1)$ or $(0, 0)$. Obviously, if we want to maximize $a \times b$, choose $(1, 1)$ is better. 2. $c_i = 1$ In this case, $(a_i, b_i)$ will be either $(1, 0)$ or $(0, 1)$. In other words, $a_i + b_i = 1$. According to above discussion. We know that for every $i$ satisfy $c_i = 0$, and $a_i = b_i = 1$. In this step we can find a mask formed by these bits. Let's call it $M$. Take $c = 10$, for example. Its binary form is $(1010)_2$. $M = (0101)_2 = 5$. The remaining bits form another mask. In fact, it equals to $c$. So if we found 2 number $a^\prime, b^\prime$, and they satisfy: 1. $a^\prime + b^\prime = c$ 2. $a^\prime\ \&\ b^\prime = 0$ So now, we know $a \times b = (M + a^\prime) \times (M + b^\prime)$. --- ## Minimize it! (20%) > [name=Bogay] ### Description Give you 2 integer $a, b \gt 0$, and you can transform a number by flip one of its bit. Take $a=1, b=3$, for example. Their binary representation is $(01)_2$ and $(11)_2$. You can flip the higher bit of $1$ to turn it into $3$, and get a sequence $S = \{1, 3\}$. Your task is to minimize the value of $s_0 \oplus s_1 \oplus s_2 \oplus \dots \oplus s_n$. In above example, it is $1 \oplus 3 = 2$. Let's look at another bigger example, $a=0, b=7$. You can find a $S=\{0, 1, 3, 7\}$, and the xor result is $5$. But you can find a smaller one with $S=\{0, 1, 5, 7\}$, which the xor result is $3$. ### Input 2 integer $a, b$, seperated by a single space. #### Limits * $0 \le a, b \le 2^{31} - 1$ * $a_n = b$ * $n$ = different bits between $a, b$ #### Subtasks | | Limits | Score | | --------- |:--------------------------------- | -----:| | #0 | different bit between $a, b$ = 1 | $60$ | | #1 | different bit between $a, b$ < 10 | $30$ | | #1 | No other limits. | $10$ | | **Total** | | $100$ | ### Output Print minimum of $s_0 \oplus s_1 \oplus s_2 \oplus \cdots \oplus s_n$. ### Sample Input 0 ``` 1 3 ``` ### Sample Output 0 ``` 2 ``` ### Sample Input 1 ``` 123 456 ``` ### Sample Output 1 ``` 73 ``` ### Sample Input 2 ``` 100 101 ``` ### Sample Output 2 ``` 1 ``` ### Sample Input 3 ``` 128 256 ``` ### Sample Output 3 ``` 0 ``` ### Hint * $1 \oplus 1 = 0$ * The solution of [this problem](https://tioj.ck.tp.edu.tw/problems/1513) may be helpful. You can find solution on internet, just search it. * The last group of testcase may be a little hard. I recommand you try to solve it after the problem-solving ideas released if you don't want to spend too much time. But I think it will be fun to find out the solution. ### Problem-solving Ideas #### Brute force (90%) You can solve this recursively, just found all permutation of that sequence, and calculate the xor results. The minimum is answer. #### Full score solution Observe the sequence, we can write it in this form: > $m_i$ means a number with only 1 bit is $1$. $s_0 = s_0$ $s_1 = s_0 \oplus m_0$ $s_2 = s_0 \oplus m_0 \oplus m_1$ $s_3 = s_0 \oplus m_0 \oplus m_1 \oplus m_2$ $\ \ \ \ \ \vdots$ $s_n = s_0 \oplus m_0 \oplus m_1 \oplus m_2 \oplus \dots \oplus m_{n-1}$ If $n$ is odd, the xor results will be $m_0 \oplus m_2 \oplus \dots \oplus m_{n-1}$. If $n$ is even, the results will be $s_0 \oplus m_1 \oplus m_3 \oplus \dots \oplus m_{n-1}$. Try minimizing these 2 sequences, that is answer. --- ## Bookshelf (20%) > [name=Bogay] ### Description Write a program to simulate a bookshelf. Suppose you have 255 books and a shelf for 8 books. 255 books are each numbered from 1 to 255, and the books are in the bookcase at first. 8 books are on the shelf on the table, and it is empty at first. When we want to read a book, we will first look for it on the shelf, and if we find it, we will take it out and read it, and then stuff it back on the far right side of the shelf when we are done. If we can't find it on the shelf, we will find it from the bookcase and read it, and then stuff it back to the far right side of the shelf. But at this time, there may be 8 books on the shelf, so we will put the leftmost book on the shelf back into the bookcase and move the books on the shelf to the left, leaving the rightmost book free for the book we just finished reading. Please simulate the situation of the bookshelf after a period of time. Since the maximum number of a book is 255, we can use 8 bits to represent it. Also, a long long int has 8 bytes, which can be used to simulate the shelf of 8 books. ### Input The input is a sequence of integers between 1 and 255, representing the order in which we read the book. The program must process all inputs up to EOF. #### Limits * $0 \le N \le 10^{6}$, $N$ is size of input sequence. #### Subtasks | | Limits | Score | | --------- |:---------------- | -----:| | #0 | $N \le 10$ | $40$ | | #1 | $N \le 10^2$ | $30$ | | #2 | $N \le 10^4$ | $20$ | | #3 | No other limits. | $10$ | | **Total** | | $100$ | ### Output The output is 8 integers, representing the number of the book in the last shelf from left to right, or 0 if there is no book in that position in the shelf. ### Sample Input 1 ``` 1 2 3 4 5 6 7 8 ``` ### Sample Output 1 ``` 1 2 3 4 5 6 7 8 ``` ### Sample Input 0 ``` 1 2 3 4 5 6 7 8 6 10 23 7 4 ``` ### Sample Output 0 ``` 3 5 8 6 10 23 7 4 ``` ### Sample Input 2 ``` 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ``` ### Sample Output 2 ``` 0 0 0 0 0 0 0 1 ``` ### Hint This problem is translated from [Judge Girl](https://judgegirl.csie.org/problem/0/222). ### Problem-solving Ideas * As description says, you can use a `long long` to store book numbers on shelf, each is 1 byte. * Use `<<` or `>>` to shift the shelf, e.g., `<< 8` will drop leftmost book, and move the other books to left. Reserve a slot for next book.