SEADIV - Editorial

PROBLEM LINK:

Contest
Practice

Author: Sergey Nagin
Tester: Sergey Kulik
Editorialist: Kevin Atienza

PREREQUISITES:

Modular inverses, long division

PROBLEM:

Given two large numbers A and B in base 7, and L, compute A / B \bmod 7^L (and write it also in base 7). It is guaranteed that B is a divisor of A.

QUICK EXPLANATION:

Compute the digits of C := A / B one by one, starting from the least significant. Each digit can be computed using inverses modulo 7, based only on the last nonzero digits of A and B, and once you extract each digit k for a place value, say, i, then you need to subtract B\cdot k7^i from A, in other words update A := A - B\cdot k7^i.

EXPLANATION:

At first glance, it seems the problem requires implementing some optimized arbitrary precision arithmetic code. One common way of doing general-purpose division of large numbers is to use Newton’s method to compute to sufficient accuracy the inverse of the denominator using an iteration that uses only multiplication, and then multiplying it to the numerator. Multiplication can be done using standard techniques such as those based on fast Fourier transforms. However, these techniques are quite complex, and even if they might work, they’re in fact quite overkill since there is a much simpler solution to the problem at hand. This solution works in our case because of the guarantee that B is a divisor of A which turns out to be quite significant.

In the following, please keep in mind that whenever we deal with A, B, A/B, and their digits, we’re working in base 7. We also introduce the following notation: For a number X in base 7, let X_i be its i th least significant digit (starting at i = 0). X_i can be extracted as follows: X_i = \lfloor X / 7^i \rfloor \bmod 7.

Since B divides A, let C := A / B be their (integer) quotient (thus, A = B\cdot C). We want to know the last L digits of C. Suppose we want to know just the last digit of C (denoted C_0). What can we say about it? Well, we know that A = B\cdot C, so it must be the case that the last digit of B multiplied by the last digit of C is equal to the last digit of A, modulo 7. In other words:

A_0 \equiv B_0\cdot C_0 \pmod{7}

This is similar to the fact that, for instance, in base 10, the product of any number ending 6 and another number ending in 9 always ends in 4, which is equivalent to 6\cdot 9\bmod 10.

What’s nice about this congruence is that C_0 can already be calculated! It’s simply:

C_0 \equiv A_0 B_0^{-1} \pmod{7}

where B_0^{-1} denotes the modular inverse of B_0 modulo 7. Thus, we already have the last digit, without even looking at almost all other digits of A and B!

However, this only works if B_0 is not 0. If B_0 = 0, then you can’t invert B_0 any more to get C_0. But in this case, we can still do something. If B_0 = 0, then automatically we have A_0 = 0, which means that we can cancel the trailing zeroes. We’ll be left with a new A and B with one less digit, but the last digit of this new B is the old B_1. If this is again a zero, then we can repeat this process, until the last digit of B is not a zero! So we can reduce every case to the case where B_0 \not= 0!

Now that we have C_0, how can we get the next digit, C_1? Since the last digit is C_0, we know now that C is of the form C'\cdot 7 + C_0 for some C', and that C_1 = C_0', so we want to get the last digit of C'. Let’s see what we can do:

\begin{aligned} A &= B\cdot C \\\ A &= B\cdot (C'\cdot 7 + C_0) \\\ A &= B\cdot C'\cdot 7 + B\cdot C_0 \\\ A - B\cdot C_0 &= B\cdot C'\cdot 7 \\\ (A - B\cdot C_0) / 7 &= B\cdot C' \end{aligned}

Let’s define A' := (A - B\cdot C_0) / 7 to be the value at the left hand side.

Notice that the latter is the same form as the original problem, so somehow we’ll be able to extract the last digit of C' if we have the value A'. But A' = (A - B\cdot C_0) / 7 can be computed in O(\log_7 B) time! (Note that B has \Theta(\log_7 B) digits.) Because remember that C_0 is just a single digit, and when subtracting B\cdot C_0 from A we only need to iterate through the digits of B, not A. Also, dividing by 7 is simply moving the digits one place to the right, which at first glance seems to take O(\log_7 A) time, but we can easily get around this. The following are a few ways:

  • We can represent A as an array list with the digits stored in decreasing significance (so the least significant digit is last), because popping from the end of an array list can be done in O(1) amortized time.

  • We can simply represent A as a pointer to a position to the array and a number representing its length. Then to pop from the end of A, simply decrement the length!

So now that we have this number, we can now get C_0' by recursively using the same method. Remember that C_0' is really C_1. To get the next few digits, we simply repeat this until we get the L digits we are looking for!

Optimizations

Since we’re repeating this step L times, and each step takes O(\log_7 B) = O(\log B) time, the overall algorithm runs in O(L \log B) time, which could pass the time limit if implemented with a couple of optimizations in mind. Here, we enumerate some.

First, after ensuring that B_0 \not= 0, we may use only the last L digits of A and ignore the rest. This is because by analyzing our algorithm above, notice that we won’t ever have any use of all the higher-order digits of A. For instance, if we only want the last digit of C, then we only need the last digit of A. This reduces the amount of work to be done by about half, because the number of digits that need to be updated at each step decreases one by one.

Another way to look at it is the following:

If B \not\equiv 0 \pmod{7}, then there is a unique solution x to A \equiv B\cdot x \pmod{7^L}, so if A = B\cdot C, then it must be the case that C\bmod 7^L = x \bmod 7^L. Thus, we are really only solving for the solution to the congruence A \equiv B\cdot x \pmod{7^L}, and we only really need the values A and B modulo 7^L, i.e. the last L digits of A and B.

Second, we can further reduce the number of operations needed by operating in base 7^k rather than just base 7. To maximize the effect, choose k as large as possible such that 7^k is still below the signed 32-bit limit (to not cause too much headache about overflow). In the editorialist’s solution, k = 10 is used. This reduces the number of “digits” of A and B by a factor of k, and also reduces the number of “digits” we want, L, by a factor of k, so the running time becomes O((L \log B) / k^2) which is a good speedup! Now, the constant becomes higher because we now have to use larger int types, but still you’ll find that this will give a noticeable improvement in running time.

Time Complexity:

O(L \log B)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester
Editorialist

I tired to implement trival solution for 20 points as follows, still it gives WA in 1 subtask.

  1. Convert to base 10.
  2. Divide numbers.
  3. Convert to base 7.
  4. Print last L digits
    Can anybody help me find testcase where this solution will be wrong ?
    https://www.codechef.com/viewsolution/8921637

When the last L digits all are 0, it will print 0 L times. It should print it just once.

Thank you rishivikram.

Because of this silly mistake I missed 50 points.

Here are my solution with updates -

https://www.codechef.com/viewsolution/8957426 - 20 pts

https://www.codechef.com/viewsolution/8957453 - 50 pts

I will work on this next to score 100 pts.

1 Like

Here is my Problem Analysis

2 Likes

Can anyone tell me what is wrong with this? Just for the 20 points, as for the rest it would overflow.

https://www.codechef.com/viewsolution/8958535

@ramit2727

It still overflows for 20 points. Consider test case

66666666666666666666 1 5

Also, there is problem of preceding zeroes. Consider test case

1000000010 10 5

Thank you!
However, 6(20 times) is 6*(111…)20 times. which in base 10 is: 6*(7^20-1)/6-1, which is less than 2^64-1 (range of unsigned long long), so why is there an overflow? What am I missing?

@kevinsogo Please help me find your solution link…I need to understand the part "In the editorialist’s solution, k=10 is used " …

2 Likes

The thing you are missing is - You are reading 6.66… * 10^19 not ~7^20.

Also avoid using pow function for calculating powers of integer. Use multiplication.

Issue is due to precision - It gives 6666666666666666 + 6*10^16 = 66666666666666664, rather than 66666666666666666.

See code here - http://ideone.com/xCvIW2

why do the ith digit of A becomes 0 if ith digit of B is zero. What is the logic behind this?
“If B0=0, then automatically we have A0=0, which means that we can cancel the trailing zeroes. We’ll be left with a new A and B with one less digit, but the last digit of this new B is the old B1. If this is again a zero, then we can repeat this process, until the last digit of B is not a zero!”

Because A0 = B0 * C0 (mod 7). In other words, if 7 divides B and B divides A, then 7 divides A. It’s only true for the last digit though.

Where is the editorialist solution?

1 Like

I have gone through both the Tester’s and Setter’s solution. Can anyone please tell me whats exactly stored in the 3D array and how is it used?

In multiplication of 2 numbers, each digit is computed as (carry + d1*d2)%BASE = dp,

Where d1, d2 - Digits of multipliers

dp - Digit of product

BASE - 7 here

Here, Setter & Tester have precomputed d2 for all combination of carry, d1 & dp(All 0-6) & stored in 3D array.

It is used to calculate digits of C(answer).

@kevinsogo thnks man…

You’re welcome :slight_smile:

A link has been added. Please check.

1 Like