In the following two submissions 224059045 and 224058953 the only difference is one line where I replaced

memset(dc, n+5, sizeof(dc));

with

for(int i=1;i<=n;i++) dc[i] = n+5;

and it WA on the first but AC with the latter. I'm not sure why this is happening. Any ideas?

Here's an interesting string problem I have been thinking about related to the game of Kilordle, a variant of Wordle. I'm curious to see if there is a good solution.

Kilordle is a word game played like Wordle, but instead of having one game, you play several games of wordle simultaneously, and each guess is applied to each individual game. You win after correctly solving every game of wordle. In kilordle, you don't have to guess the exact word for any of the individual games. As long as you guess words that have letters in the correct places that will suffice. You can guess as many times as you want. For example, if the word for one of the individual games is "CARTS", then if you guess "CAtch" and then "foRTS" that individual game will be solved, as you have guessed a word that contains C as the first letter, you've guessed a word that contains A as the second letter, you've guessed a word that contains R as the third letter, etc.

One simple strategy for kilordle is just to type in a sequence of words that covers all possible words in the dictionary.

Formally, suppose the dictionary contains a set $$$S$$$ of $$$n$$$ strings, each of length $$$k,$$$ and there are $$$m$$$ distinct letters in the language. Give an efficient algorithm to find the size of the smallest subset $$$S' \subset S$$$ such that for all $$$s \in S,$$$ and all $$$1 \leq i \leq k,$$$ there exists some $$$s' \in S'$$$ such that $$$s[i] = s'[i].$$$

I want to compute the sum $$$\left\lfloor \frac{m}{n} \right\rfloor + \left\lfloor \frac{2m}{n} \right\rfloor + \cdots + \left\lfloor \frac{(n-1)m}{n} \right\rfloor = \sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor$$$ in log time.

I know that when $$$\gcd(m,n) = 1,$$$ this can be viewed as counting lattice points under the line $$$y=\frac{m}{n} x$$$ and by symmetry it's equal to half the number of lattice points contained in the entire rectangle (because there's no lattice points exactly on the line segment between $$$(0,0)$$$ and $$$(m,n)$$$ as $$$\gcd(m,n) = 1$$$), so the sum is equal to $$$\frac{(m-1)(n-1)}{2}.$$$ (When $$$m,n$$$ are prime, the sum is a nice lemma that is used in a proof of Quadratic Reciprocity.)

I'm told that there's a way to think about this that is similar to the Euclidean Algorithm for gcd. Is there a connection to that? Is there a way to generalize the lattice point counting approach for relatively prime $$$m,n$$$?