Editorial for W02 Contest - CS 334 - Spring 2025

581634A - Not Quite Latin Square

Output the element in the matrix which occurs only twice.

Original problem: 1915B - Not Quite Latin Square, leads to official tutorial and all solutions including WS solution: 277700626

581634B - Digit Game

Raze wins if the last unmarked digit is odd. So Raze's optimal strategy is to mark all even digits before marking odd digits. Breach wins if the last unmarked digit is even. So Breach's optimal strategy is to mark all odd digits before marking any even digits.

If $$$n$$$ is odd, then the last unmarked number will be in an odd position, i.e. in a position that only Raze can access. Raze can win if there is at least a single odd digit among the odd positions. Raze can take care to leave this number unmarked till the end. If there is no odd digit among the odd positions, i.e. all the digits in the odd positions are even, then the last unmarked digit is even and Breach wins. So, if $$$n$$$ is odd, Raze wins if there is at least one odd digit among the odd positions, otherwise Breach wins.

Similarly, if $$$n$$$ is even, then Breach wins if there is at least one even digit among the even positions, otherwise Raze wins.

Original problem: 1419A - Digit Game, leads to official tutorial and all solutions including WS solution: 300911809

581634C - King Escape

We can imagine the position of the queen defining 4 quadrants: each comprising of positions above-left, above-right, below-right, and below-left of the queen. Some quadrants may be empty if the queen is at an edge or corner. The king can reach the destination only if its position and the destination position are in the same quadrant. Otherwise, it will have to change quadrants which it cannot do without going into check.

Original problem: 1033A - King Escape, leads to official tutorial and all solutions including WS solution: 300913056

581634D - ABC String

The string, $$$a$$$, comprises three letters, A, B, and C. For $$$a$$$ to be balanced, the first letter and last letter in $$$a$$$ must correspond to ( and ) respectively. If these letters are the same, the string is not balanced.

Further, for $$$a$$$ to be balanced, the count of the third letter, i.e. the letter that is not the first or last in $$$a$$$, must be equal to the absolute difference of the counts of the first and last letters. If this is not the case, the string is not balanced.

One way to find the third letter is as follows. In $$$a$$$, replace A with 0, B with 1, and C with 2. Then if the integer values of the first and last letters are $$$F$$$ and $$$L$$$, then the integer value of the third letter is $$$3-F-L$$$.

Further, for $$$a$$$ to be balanced, the third letter corresponds to ( if the count of the first letter in $$$a$$$ is less than the count of the last letter. Otherwise, the third letter corresponds to ).

Now that we know the brackets corresponding to all three letters, we determine whether $$$a$$$ represents a balanced bracket sequence, e.g., using a stack.

Original problem: 1494A - ABC String, leads to official tutorial and all solutions including WS solution: 301131398

581634E - I Love 1543

The number of layers is $$$\min(m,n)/2$$$.

We can use index calculations to determine the corners of each layer. It helps that layers are symmetric horizontally and vertically. We unravel a layer into a string $$$s$$$ as follows. Starting from any position in the layer and traversing the layer in clockwise order, assemble all the encountered digits into a single string, $$$s$$$. We then count the number of occurrence of the string 1543 in $$$s$$$.

We need to take care to also check if unraveling a layer has split an occurrence of the string 1543 into different ends of $$$s$$$.

Original problem: 2036D - I Love 1543, leads to official tutorial and all solutions including WS solution: 289530642