Leaderboard

1. bernds - 24
2. ugoertz - 16
3. Solomon, gamesorry - 15
4. dfan - 9
5. peti29 - 6
6. jeromie, quantumf - 5
7. Kirby - 3

Contest Link: https://open.kattis.com/contests/efr2j9

Start Time: 2017-06-09 17:00:00 UTC (Fri June 9 2017 10am PST, 19:00 CEST)
Duration: 60 hours
Problems: 6
Theme: Math

Past Rounds:

• Round 5 (June 2 2017)
• Round 4 (May 19 2017)
• Round 3 (May 12 2017)
• Round 2 (May 6 2017)
• Round 1 (April 28 2017)

Also, this round might be good for people who don't like coding so much but enjoy math, because I have a feeling (i.e., I don't really know but it's just my hunch) that the amount of code needed to be written for these questions will be short.

Spent way too much time thinking about and trying to figure out Three Digits (C) . A and D weren't too bad, and I went with an approximation formula for B so it really only feels like I got 2. Even though both B and C both centralized on factorials, I just could not figure out a way to work around C without actually computing the factorial. Failing to solve C and E (unfortunately never got around to F), I think this only made me realize how weak my grasp on number theory is (despite having a degree in mathematics, my classes heavily outweighed probability theory and statistics and I had never taken courses in number theory or abstract algebra, which I do regret).

Anyways, I would love to hear from ugoertz, bernds, or gamesorry how they tackled C and E (especially C) and I hope it's not too complicated!

For both C and E, I submitted the Python3 codes first but got TLEs, even if I hard-coded a prime number table in E. After converting them into C++ they got accepted within the time limit with quite large margin. For D Python worked nicely for the large number though. So I guess next time I need to quickly figure out whether the time limit would be an important factor before choosing the language. (ugoertz got accepted in Python3 for E, and I'd like to know how to achieve that )

C: there's a famous problem of counting the number of trailing zeroes in n! - the answer is to count how many 5s are in the factors of 1..n. Therefore, in order to remove them, we just need to avoid multiplying these 5-factors and the same number of 2-factors, so that the last digit of the result would always be non-zero. After that, we just need to mod 1000 during multiplication to keep the last 3 digits.

C solution, 0.07 s

Almost same code in Python, TLE

E: If the last digit of n in base k is 3, then n mod k = 3 (k > 3), or (n-3) mod k = 0 - more importantly, this property can hold in the other direction, i.e., if (n-3) mod k = 0 (k > 3), then the last digit of n in base k must be 3. Therefore, (n-3) must be divisible by the base k and we only need to find out the minimum factor of (n-3) that is larger than 3. There are quite a few corner cases and hand-checking the examples of 1..20 helps a lot.

C++ solution in 0.03 s

Python code with the same logic getting TLE:

I'm wondering if there's an elegant solution for A. I worked on it for an hour trying to write down a dp solution but couldn't figure it out completely - there seem to be many cases to be analyzed.

Thanks, Solomon, for setting up the contest! Here are some thoughts on my solutions:

A. Taking a difference in the final step, it is enough to compute the number of zeros needed to write down all numbers from 0 to n. To do this, I computed how often the i-th digit is a 0, for all i. This is quite easy: Say n = 12345, then for the 5th digit we get 1235, for the 4th digit we get 123 * 10, for the 3rd digit 12 * 100, for the second digit 1 * 1000. (If a digit is 0, the formula changes slightly.)

B. I used (the logarithm of) Stirling's formula.

C. Up to trailing zeros, we want to compute modulo 1000, so we will first discard all powers of 2 and 5, and fix that in the end. Now for every n > 0, the product of all those numbers in {n, n+1, n+2, ..., n+999} which are coprime to 2 and 5, is independent of n, and is easily checked to be equal to 1. (The independence of n has nothing to do with computing modulo 1000, of course; the value of the product is not always 1, however: e.g., doing this modulo 10, we get -1.) This means that splitting the factorial into chunks of 1000 consecutive numbers, we can ignore all those coprime to 2 and 5.

As gamesorry pointed out, all powers of 5 go into trailing zeros; so we just compute what this power is (using Legendre's formula). The same power of 2 is then also used up for the trailing zeros. The remaining power of 2 must be multiplied with what we had from the first step.

(Finally, to speed up things, I precomputed the values of the first step for multiples of 1,000,000. Then for large numbers one can start off from the greatest multiple of 1000000 which is smaller than the number in question.


D. The problem is easily translated into the problem of finding the binary expression of n-1.

E. Up to some border cases, we need to find the smallest prime factor of n-3. (The border cases are that for 1, 2, 4, 5, 6 there is no solution, and we really want to find the smallest divisor of n within [4, 5, 6, 7, 9, 11, 13, ...] (continue with primes > 13). Finally, we do not want to compute all primes up to 2**31; if no divisor in the above list <= sqrt(n) was found, then n is a prime (or twice a prime, or three times a prime), and we return n (or n//2, n//3, resp.).

@gamesorry: I think this is exactly what you said. If I understand your code correctly, you go on to find all prime divisors though, which is probably what takes too long.

F. I have "sort of" a solution but it clearly does not meet the time requirements.

You can look at the code here.

Best, Ulrich

_________________
u-go.net

Congratulations to Ulrich!

I don't have too much to add to the already posted explanations. Problem A rather reminded me of the digit sum problem from an earlier round.
I'm guessing 1235 instead of 1234 for the fifth because zero has to be counted? I had a slightly different approach: count the number of zeros printed for numbers 0..10^n-1, with or without leading zeros, with a bit of recursion.
Is that what everyone did? I didn't know a good way to approximate the factorial and didn't want to just google the answer. So I thought of a solution that would have involved extracting 2s and 5s again, computing subresults that fit within a 64-bit integer, then having a series of widening multiplies discarding the low parts at every step, and organizing the calculation in a binary tree so as to minimize the rounding errors... then I looked at the column of green and decided that can't be what everyone is doing.
Huh. I'm pretty sure I didn't use that. I guess I'll need to go look at your code to see if that would have helped any; the problem seemed quite simple without it.
Yeah. I kind of knew all or most of this, but I screwed up the last step because for a while I didn't realize I'd have prime divisors above sqrt(n) if I skipped 2 and 3. I actually realized what the problem was after I'd gone to bed on Sunday.

As always, thx for the round, Solomon!

B) I googled up a formula that had PI, E and lots of log10 in it, had no idea how it works, but apparently everyone else used the same here, so

D) I really enjoyed D. That's my level of math (shame or not). First I realized that in base 3 those sets consist of elements like 10, 100, 101, 1101, etc. And then I realized that if we sort those we get base 2 numbers in order (plus the empty set at the first place).

Yes, that's right.


It's probably nearly as good to keep track of the 5's and 2's more directly. But Legendre's formula is quite nice (and not hard to derive and to apply), so it seemed a good opportunity to use it. I suppose the remark about omitting factors coprime to 2 and 5 in complete chunks of one thousand numbers gives only a marginal speed-up and can be ignored (for Python code maybe at the cost of precomputing a couple more values).

Best, Ulrich

_________________
u-go.net

My first attempt was to just calculate the sum of log(i) for i = 2 to n and take the floor of that, but I hit TLE (my second attempt was rewriting it in C++ only to hit TLE again). I was already aware of Stirling's formula so I just took the easy route, but afterwards realized I could have just memoized everything up to 1e6 and that could have worked as well: