
ZOJ Problem Set  4017
It's a beautiful day outside. Birds are singing. Flowers are blooming. You turn on your computer and are ready for a day's work. But, alas, your disk FAILED and all your data goes down the drain! But don't worry, it's time for RAID (Redundant Array of Independent Disks) to come to your rescue! The idea behind RAID is quite simple: make copies of data on other disks. This is exactly what RAID1 does. RAID1 makes a mirror for every disk, so each bit of your data is stored identically on two different disks. If one disk fails, you can still restore your data from another disk. RAID1 is nice, but isn't clever enough, as you can only use 50% of your disks to store meaningful data. RAID3 is a smarter approach. Let's say you have \(m\) data disks, each containing \(n\) bits, where the \(i\)th bit in the \(j\)th data disk (note that we count \(i\) from 0 to \((n1)\), and \(j\) from 0 to \((m1)\)) is indicated as \(b_{i,j}\). RAID3 only requires you to buy one more disk, called the row parity disk, to store extra data. Let the \(i\)th bit in the row parity disk to be \(r_i\). RAID3 calculates \(r_i\) as follows: \[r_i = b_{i,0} \oplus b_{i,1} \oplus \dots \oplus b_{i,m2} \oplus b_{i,m1}\] where \(\oplus\) is the bitwise exclusive or operation (\(0 \oplus 0 = 1 \oplus 1 = 0\), \(0 \oplus 1 = 1 \oplus 0 = 1\)). With the row parity disk in hand, if the \(j\)th data disk fails, we can restore the data on that disk by adjusting the above formula to \[b_{i,j} = r_i \oplus b_{i,0} \oplus b_{i,1} \oplus \dots \oplus b_{i,j2} \oplus b_{i,j1} \oplus b_{i,j+1} \oplus b_{i,j+2} \oplus \dots \oplus b_{i,m2} \oplus b_{i,m1}\] What's more, you can now use \(\frac{m}{m+1}\) of your disks to store meaningful data! Horray! RAID3 seems to be such a perfect approach, that we even put ourselves under the illusion that we can sit back and relax after deploying RAID5 (similar to RAID3, but more reliable) on ZOJ and stop thinking about disk failures. But guess what, the careless administrator of the data center didn't notice the warning when a disk failure occurred, and when another disk failed in May 2016, everything was too late. RAID3 and RAID5 can both protect their users from one disk failure, but if two disks fail simultaneously (though the probability is small) or you have a careless data center administrator, they still can't help you restore your data. This is why we invent RAIDZOJ. RAIDZOJ is another RAID approach hoping to guard its users against two simultaneous disk failures. To achieve this goal, apart from the row parity disk, we add a second parity disk to the system, called the diagonal parity disk. For a bit \(b_{i,j}\) on the data disk, we define its diagonal value \(D(b_{i,j}) = (i+j) \mod n\). Let \(d_i\) be the \(i\)th bit on the diagonal parity disk, we calculate \(d_i\) as follows: \[d_i = \bigoplus_{D(b_{k,j}) = i}b_{k,j}\] which means that \(d_i\) is calculated as the bitwise exclusive or of every bit whose diagonal value equals \(i\). To help you understand, check the sample figure showing a RAIDZOJ system with \(n = 3\) and \(m = 4\) below. Now comes the final problem: is RAIDZOJ capable of restoring data on two failed disks? We now provide you with a RAIDZOJ system with \(m\) data disks, each containing \(n\) bits, a row parity disk, and a diagonal parity disk. In this system, exactly two data disks are broken. Your task is to restore the data on the two failed data disks so that the restored data are consistent with the two parity disks. As there might be multiple valid answers, you just need to calculate the minimum and the maximum possible number of 1s in the broken bits. InputThere are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case: The first line contains two integers \(n\) and \(m\) (\(1 \le n \times m \le 10^6\)), indicating the number of bits in each data disk and the number of data disks. Each of the next \(n\) lines contains \(m\) characters denoting the bits in the data disks. The \(j\)th character on the \(i\)th line (don't forget we count both \(i\) and \(j\) from 0) is \(b_{i,j}\) (\(b_{i,j} \in \{0, 1, \text{X}\}\)), indicating the \(i\)th bit in the \(j\)th data disk, where \(b_{i,j} = \text{X}\) (ASCII code: 88) means that this bit is broken and its your task to restore its value. The next line contains \(n\) characters \(r_0, r_1, \dots, r_{n1}\) (\(r_i \in \{0, 1\}\)), indicating the bits in the row parity disk. The next line contains \(n\) characters \(d_0, d_1, \dots, d_{n1}\) (\(d_i \in \{0, 1\}\)), indicating the bits in the diagonal parity disk. It's guaranteed that there exist exactly two different integers \(a\) and \(b\) such that \(1 \le a, b \le m\) and \(b_{i,a} = b_{i,b} = \text{X}\) for all \(1 \le i \le n\). It's also guaranteed that the sum of \(n \times m\) over all test cases will not exceed \(3 \times 10^6\). OutputFor each test case output one line containing two integers separated by a space, indicating the minimum and the maximum possible number of 1s in the broken bits. If no valid answer exists, print "No Solution" (without quotes) instead. Sample Input4 3 4 0XX1 1XX1 0XX0 000 110 2 3 X1X X0X 10 01 3 5 X0X01 X0X01 X0X01 101 010 1 2 XX 1 1 Sample Output1 5 0 4 No Solution 1 1 HintThe two possible answers for the first sample test case are shown as follows (the restored broken bits are shown in bold): The first possible answer has five 1s in the broken bits, while the second possible answer has one 1. So the answer is "1 5". The four possible answers for the second sample test case are shown as follows (the restored broken bits are shown in bold): The first possible answer has no 1 in the broken bits, while the second and the third possible answer each has two 1s, and the fourth possible answer has four 1s. So the answer is "0 4". Author: WANG, Yucheng Source: The 18th Zhejiang University Programming Contest Sponsored by TuSimple 