hackercupai/hackercup

1<p>2The far-off land of Tamriel is brimming with opportunity! Opportunity for adventure, politics, romance... and, perhaps most importantly of all, commerce.3</p>4 5<p>6A group of Khajiit merchants, traditionally known for roaming the countryside selling their wares, have recently set up permanent bazaars in a number of towns. 7Having gotten their cat-like paws on a large supply of raw amber and bronze, they're prepared to strategically work together to maximize their profits selling it!8</p>9 10<p>11One bazaar has been set up in each of <strong>N</strong>*<strong>M</strong>+1 towns. The towns are numbered from 0 to <strong>N</strong>*<strong>M</strong>, inclusive, 12and are connected by roads in a hub-and-spokes arrangement, with town 0 in the center and <strong>N</strong> lines of <strong>M</strong> towns each arranged around it. 13The <em>i</em>th such line consists of towns <strong>M</strong>*(<em>i</em>-1)+1 to <strong>M</strong>*<em>i</em>, inclusive, 14connected together in order by <strong>M</strong>-1 roads (with one between towns <strong>M</strong>*(<em>i</em>-1)+1 and <strong>M</strong>*(<em>i</em>-1)+2, 15another between towns <strong>M</strong>*(<em>i</em>-1)+2 and <strong>M</strong>*(<em>i</em>-1)+3, and so on). 16For each line <em>i</em>, there is furthermore a road connecting its first town (<strong>M</strong>*(<em>i</em>-1)+1) to town 0. 17Note that each of the <strong>N</strong>*<strong>M</strong> roads may be travelled in either direction, 18and that each town may be reached from each other town by following a sequence of roads.19</p>20 21<p>22For example, if <strong>N</strong>=4 and <strong>M</strong>=2, the arrangement of towns and roads would look as follows:23</p>24 25<img src={{PHOTO_ID:291992558607686}} width="200px" />26 27<p>28Initially, the bazaar in each town <em>i</em> is stocked with either amber (if <strong>X<sub>i</sub></strong> = "A") or bronze (if <strong>X<sub>i</sub></strong> = "B"). 29However, in order to satisfy demand, it should end up stocked with a potentially different ware, either amber 30(if <strong>Y<sub>i</sub></strong> = "A") or bronze (if <strong>Y<sub>i</sub></strong> = "B"). 31It's guaranteed that the number of bazaars initially stocked with amber is equal to the number of bazaars which should end up stocked with amber (consequently, the same holds true for bronze).32</p>33 34<p>35In order to accomplish their goal, the Khajiit merchants may repeatedly select a pair of towns which are directly connected by a road, and swap their bazaars' wares. 36Please help them determine the minimum number of such swaps required for all <strong>N</strong>*<strong>M</strong>+1 bazaars to end up stocked with the required wares! 37This is guaranteed to be possible for every possible valid input.38</p>39 40 41<h3>Input</h3>42 43<p>44Input begins with an integer <strong>T</strong>, the number of Khajiit groups.45<br />For each group, there is first a line containing the space-separated integers <strong>N</strong> and <strong>M</strong>.46<br />Then follows a line with the length-(<strong>N</strong> * <strong>M</strong> + 1) string <strong>X</strong>,47the characters <strong>X<sub>0</sub></strong> through <strong>X<sub>N*M</sub></strong>.48<br />Then follows a line with the length-(<strong>N</strong> * <strong>M</strong> + 1) string <strong>Y</strong>,49the characters <strong>Y<sub>0</sub></strong> through <strong>Y<sub>N*M</sub></strong>.50</p>51 52 53<h3>Output</h3>54 55<p>56For the <em>i</em>th group, print a line containing "Case #<em>i</em>: " followed by57one integer, the minimum number of swaps required to stock all of the bazaars with the required wares.58</p>59 60 61<h3>Constraints</h3>62 63<p>641 &le; <strong>T</strong> &le; 80 <br />651 &le; <strong>N</strong>, <strong>M</strong> &le; 1,000,000 <br />661 &le; <strong>N</strong> * <strong>M</strong> &le; 1,000,000 <br />67</p>68 69<p>70The sum of <strong>N</strong> * <strong>M</strong> across all <strong>T</strong> test cases is no greater than 10,000,000.71</p>72 73 74<h3>Explanation of Sample</h3>75 76<p>77In the first case, no swaps are required.78</p>79 80<p>81In the second case, bazaars 1 and 2 should swap their goods.82</p>83 84<p>85In the third case, the bazaars are initially set up as follows (with ones carrying amber marked in yellow, and ones carrying bronze marked in orange):86</p>87 88<img src={{PHOTO_ID:266243124686458}} width="300px"/>89 90  91<p>92The following sequence of 3 swaps could then be performed to arrive at the required configuration:93</p>94 95<img src={{PHOTO_ID:637978470132709}} width="300px"/><br />96<img src={{PHOTO_ID:950762542025264}} width="300px"/><br />97<img src={{PHOTO_ID:635336360404128}} width="300px"/><br />98