arc099_a: Minimization

Official solution: Always ceil(N-1/K-1)

Proof:

1. each op increases # of 1s by K-1 at most, so we know it is the upperbound. We claim such bound is always achievable

2. Construct segments as c(K-1) ….(c +1)(K-1). We can see that neighboring segments share a comment element, and i =1 must exist within one segs. Also, ceil(N-1/k-1) such segs is enough to cover the whole array.

3. Therefore, we just start with the seg A[i] = 1 in, and expand to both sides

arc099_b: Snuke Numbers

I had problem proving my insights during the contest!!!

1. Because each N we find is the new mean, the N/S(N) ratios are actually increasing as K increases

2. Therefore, to iterate, we can just calculate F(N) = M, M is the the smallest # > N that yields min M/S(M), and then assign N = F(N)

Claim: the suffix of M’s must end with 9s - may be multiple though.

Proof:

a. Because M > N, from left to right there must exists a digit where M(i) > N(i). We can move some of the delta, to make first right to left non-9 to 9.

b. Thus, M/S(M) got reduced, we can repeat, until we can procceed

Therefore, the format of M is {prefix of N}{a single digit >= N[i]}{9s}. Given that each step we have at most 15 digits, we can just brute force search and find the min M/S(M) in the search space