Online Course Discussion Forum

8 Week Usaco Prep Course Assignment 5 Problem 1

 
 
Picture of Alvin Han
8 Week Usaco Prep Course Assignment 5 Problem 1
by Alvin Han - Friday, November 5, 2021, 8:50 PM
 

For the prefix sums problem, multiples of 2019, I tried out the algorithm but it doesn't give any correct results. I think I might have misunderstood step 2, since it wasn't explained very clearly. Step 2: Build an array of remainders mod 2019 of the powers of 10, multiply the corresponding results from (1) and (2) in reverse order, and record the results mod 2019 in an array. Note that 0 should be the first element of this array.

Can you please give an example depicting this step? Thanks!

 
Picture of Dr. Kevin Wang
Re: 8 Week Usaco Prep Course Assignment 5 Problem 1
by Dr. Kevin Wang - Sunday, November 7, 2021, 12:20 AM
 

Let me give an example.  Let's take the string $2019$ itself.  This string contains two substrings that are multiples of $2019$: the whole string $2019$ itself, and the single digit $0$.  We shall use the method described in the homework to verify it.

Consider an invisible leading $0$ as index $0$, and the digit $2$ to be at index $1$, etc., $9$ is at index $4$.  For the array for (1), you get $0$, $2$, $20$, $201$, and $0$ (since $2019 \equiv 0 \pmod{2019}$).  For (2), take the powers of $10$, which are $1$, $10$, $100$, $1000$, $1924$ (since $10000 \equiv 1924\pmod{2019}$).

Then you multiply the results in reverse order: $0\times 1924$, $2\times 1000$, $20\times 100$, $201\times 10$, $0\times 1$, and take each value mod $2019$, and this is the resulting array: $0$, $2000$, $2000$, $2010$, $0$.  There are two pairs of identical values: between indices $0$ and $4$, which gives $2019$; and between indices $1$ and $2$, which gives $0$.  Of course, the original question does not use the digit $0$, but that doesn't really affect the method.

Why does this method work?  This is the mathematical problem that I would like you to figure out by yourself.  It is not hard at all, if you spent some time to think about it.