### chokudai's blog

By chokudai, history, 3 years ago,

We will hold AtCoder Beginner Contest 208.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +76

| Write comment?
 » 3 years ago, # | ← Rev. 3 →   -100 downvote if you have tiny pp.
•  » » 3 years ago, # ^ |   +16 I really don't see which part of D's statement is ambiguous. Also, you should ask for the clarification on the atcoder site if you're unsure about something, not on CF.
•  » » 3 years ago, # ^ |   +2 Guys like you are like a mad rabid dog who needs to be put to sleep legally
 » 3 years ago, # |   +6 I am pretty sure the solution of F uses some pretty advanced stuffs, because for $M=1$, it reduces to 622F - The Sum of the k-th PowersLagrange polynomials in a "Beginner Contest".
 » 3 years ago, # |   +1 Floyd-Warshall algo without modifications in D, problemsetters are you serious?
•  » » 3 years ago, # ^ |   +7 How to solve D?
•  » » » 3 years ago, # ^ |   +5
•  » » » » 3 years ago, # ^ |   0 Okay Thanks. :)
•  » » 3 years ago, # ^ |   0 Why not? It's ABC meant to be educational.
•  » » » 3 years ago, # ^ |   -13 Maybe just copy pasting the algorithm is not a good idea . There should have been something additional , anyways maybe I am not qualified to answer as I was even unable to solve this .
•  » » » 3 years ago, # ^ |   0 educate to google and copypaste? when one has to modify an algorithm, he/she has to fully understand it, but probably on the contest, most people, who didn't know and managed to find this algo just copypasted, even if this algo is simple and has nothing that hard to understand. But in general, there would be more complex algos which can be copypasted w/o understanding
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 I think it is very adequate for a Beginner Contest. You need to understand the algorithm and understand where to insert the new code inside a known algorithm. My brother got to know Floyd-Warshall for the first time and even I learned how FW works more in detail. I am really positive that I won't mistakenly put $i$,$j$,$k$ in the wrong order from now on, knowing which invariant $k$ creates. :D
•  » » 3 years ago, # ^ |   +3 wait, was'nt the extra summation over k a modification? if I didn't understand Floyd-warshall, I don't think I could have solved it.
•  » » » 3 years ago, # ^ |   -14 I think it is obvious, isn't it?
•  » » » » 3 years ago, # ^ |   +15 For someone who understands the algorithm, yes.
•  » » 3 years ago, # ^ |   0 D was not graphs, it was just dp.
•  » » » 3 years ago, # ^ |   0 dp on graphs lol
•  » » 3 years ago, # ^ |   0 So what do you expect in a "beginner's" contest? Problems like F?
•  » » » 3 years ago, # ^ |   0 problems, where I have to think(also, don't forget, it's D for 400 points)
•  » » » » 3 years ago, # ^ |   0 Well, if you didnt know the working of FW, you would have to spend some time with the algorithm.
•  » » 3 years ago, # ^ |   +14 Actually that algorithm is just a greedy observation. When I solved that problem I didn't even knew that such a algorithm exists. Coincidentally I wrote the exact algorithm without even knowing about it.
•  » » » 3 years ago, # ^ |   +2 Pratik-Kumar Algorithm orz
 » 3 years ago, # |   +1 In F, $O(MKlog(mod))$ was giving TLE. Were you expecting $O(M*K + (M+K)log(mod))?$ The TL was too strict.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 .
•  » » 3 years ago, # ^ |   0 You would only need one inverse if you compute factorials properly.
•  » » » 3 years ago, # ^ |   0 In lagrange Interpolation, you need to take modular inverse $(10^9 + 7)$. So log(mod) because of that. $O(M*K)$ because I am doing interpolation that many times.Although I know, that we can do it in single interpolation by some-precomputation but $K$ was too high and problem setters should have allowed $O(MKlog(mod))$ AC. What's your code complexity?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Mine is O(MK + M + K)Because you only need one inverse. But TL is still a little bit strict.
•  » » » » » 3 years ago, # ^ |   0 How? If I am not wrong, this problem is just and extension of this whose complexity is $O(klog(mod))$. Are you doing something different?
•  » » » » » » 3 years ago, # ^ |   +20 Because for inverse factorials you should do this. Inversesvector fact(p + 1), invfact(p + 1); fact[0] = 1; for (int i = 1; i <= p; i++) { fact[i] = fact[i - 1] * i; } invfact[p] = inv(fact[p]); for (int i = p - 1; i >= 0; i--) { invfact[i] = invfact[i + 1] * (i + 1); }
 » 3 years ago, # |   +13 I solved F by using the fact that f(x, M) is a polynomial with degree (K + M). I used linear complexity (O(degree)) interpolation. Is this intended? K = 2.5e6 is kinda large, my code took 1.7s to run.
•  » » 3 years ago, # ^ |   0 Why is it polynomial of degree (K+M)? Since f(n, m) defined as sum of some number of zeros and (n^k) for n from 1 to N, then: f(N, M) = b1 * 1^k + b2 * 2^k + b3 * 3^k + ... bn * N^k — (with b_i — some unknown integers) and that makes if polynomial (of variable n) of degree (K+1), because we can turn this expresion into f(N, M) = b1*(N-(N-1))^k + b2*(N-(N-2))^k+ ... + bn*N^k = a0 + a1*n^1+a2*n^2+..+ak*n^k. No?
•  » » » 3 years ago, # ^ |   +12 No.
 » 3 years ago, # |   +4 Can someone please explain E in more simple words? editorial is not quite clear to me
•  » » 3 years ago, # ^ |   +6 I used 5 states DP to solve it , I am presuming that you know basic Digit DP.map dp [leading_zero][tight][product_is_zero][no_of_digit]; except no. Of digit all other states will be 0 or 1 . I am using Map as I don't know exactly how many values of K will be there ( Hoping that someone will tell me the upperbound on no. of K for each state ). Tight represents that whether the current no. through which I came here is till now equal to N or not.Then just some digit DP stuffs.code
•  » » 3 years ago, # ^ |   +6 I did this DP from least significant digit to most significant digit. Submission link. As far as I can tell, there's no need to have the optimization they mention in the editorial where products greater than K are indistinguishable, so I'll ignore that.The DP state I use only needs to store two values — the maximum possible value that the number can take on given the digits we already have, and the product attained so far from the digits we have already used. The starting state is therefore $(N, 1)$. The base case for this DP is if the maximum possible value that the number can take on is zero — in this case, we can't add any more digits, so we simply check if our attained product is less than or equal to $K$.If we are not in the base case, then we can append digits to the left. The transitions are therefore adding the digits from zero to nine (or $N$, if $N < 9$) to the left of the number we have built so far. Adding the nonzero digits is straightforward, the product just scales by the digit we added, and the maximum value goes from $v$ to $\left \lfloor \frac{v-d}{10} \right \rfloor$ if we just appended a digit $d$. The interesting transition is when we add a zero. There are two cases — either all the digits will be zero from here to the most significant digit, or there will be a digit to the left that is nonzero. In the former case, the number we have built so far is evaluated to see if it is valid. In the latter case, we mark the current product as being equal to "zero", except that it is not valid if we run into the base case. This is necessary to avoid overcounting. If we multiply this "zero" by any non-zero digit, then the product becomes exactly zero. In my code, the sentinel ZERO is used as a placeholder for this fake zero.Note that in the above, we cleanly handle numbers where the length is less than or equal to the length of $N$. This avoids a typical issue in digit DP where we have to keep track of when the number is "initialized", if the DP is done from most significant digit to least significant digit.This DP also counts zero, so you'll need to decrease the answer by one at the end.
•  » » 3 years ago, # ^ | ← Rev. 4 →   +8 4D dp is sufficient for solving the problem (use map for storing dp) The dp will look something like this :- ~~~~~map,pair >,int>dp; // {{pos,prod},{tight,st}} pos : current pos in the number prod : current product of digits so far tight : tells whether current no is smaller than N or not st : tells does the number has leading zeros or not. ~~~~~So if u know basics of digit dp , this problem can be solved :) For reference : My Accepted Code(c++)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I think the easiest way is to iterate over the most significant digit that differs, and then use the naive $dp[i][j] :=$ number of $i$-digit numbers with product $\leq j$. Since every $j$ will be of the form $\left \lfloor{K/x}\right \rfloor$ for some $x$, $j$ can take on at most $2\sqrt{K}$ distinct values. I think the editorial proves a tighter bound, but $O(18\cdot 2 \cdot \sqrt{K})$ is already good enough. (There is a small edge case with trailing 0s, but you can use the same DP to handle that.)
 » 3 years ago, # |   +14 Problem D was very nice!
•  » » 3 years ago, # ^ |   0 Unluckily,somebody have seen this thick.....
 » 3 years ago, # |   +5 A simple solution for F with interpolation.We know that,for a function $f$ on $\mathbf{N}$ with $\deg(f)=k(k>0)$,denote $g$ as the prefix sum function of $f,$ $\deg(g)=k+1$ holds.Consider $(i,j)$ of the chart as $f_j(i)$,then $\deg(f_j)=\deg(f_{j-1})+1=k+j$Calculate $f_j(1...m+k)$ and use interpolation to solve it.$O(m\log k+m(m+k))$or $O(m\log k+m+k)$ in total.Bonus:How about $10^5$ queries($m,k$ are the same)? Just use fast evalution on polynoimal,$O(m\log k+Q\log^2(m+k))$
 » 3 years ago, # |   +21 Isn't this the answer for $f(n, m)$ when $n > 0$ in problem F? $\sum\limits_{i = 1}^n ( \binom{n + m - i - 1}{m - 1} \cdot i^k )$
•  » » 3 years ago, # ^ |   0 Yes, but how to calculate that for a huge N
•  » » 3 years ago, # ^ |   0 Yeah, I caught this series pretty quick, but I tried for like 90 mins on how to get this sum and failed. Bad decision skipping E and going for F.
•  » » » 3 years ago, # ^ |   +14 Bad decision skipping E and going for F. Bad decision starting with F. lol
•  » » 3 years ago, # ^ | ← Rev. 4 →   -11 UPD: No, my calculation is just plain wrong.Oh, I got $\sum\limits_{i = 1}^n ( \binom{(m - 1) \cdot ( i- 1)}{m - 1} \cdot i^K )$You count the paths from $f(n,m)$ to $f(i,0)$ and multiply by $i^K$ for all $i$. Is that the same?
•  » » » 3 years ago, # ^ |   +14 No, just plug in random small values of n and m, your formula will give incorrect answers (i.g. $f(2, 5) = 5 + 2^k$, and your formula gives $\binom{(5 - 1) \cdot (1 - 1)}{5 - 1} \cdot 1^k + \binom{(5 - 1) \cdot (2 - 1)}{5 - 1} \cdot 2^k = \binom{0}{4} \cdot 1^k + \binom{4}{4} \cdot 2^k = 2^k$).
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   -11 Argh, you are right, got my error. First of all I got $\pm 1$-errors galore. Second of all, the formula on this site which I used as my source is wrong. It says $Number Of Paths=\binom{(W-1)(H-1)}{(W-1)}$ but this is just plain wrong, compare to the wiki article. If I replace the multiplication with addition in my formula I get your formula.Thanks very much, I won't make this mistake again!
 » 3 years ago, # | ← Rev. 2 →   +3 Can someone please give a rigorous proof of upper_bound for E's naive top down solution's complexity ?
•  » » 3 years ago, # ^ |   +1 Do you mean why the number of distinct products fits in constraints?
•  » » » 3 years ago, # ^ |   +3 Yes. Is there a convincing proof of this thing ?
•  » » » » 3 years ago, # ^ |   +1 Ah, i dont have a "proof", but i have some combinatorics. It's obvious that the product is independent of the order of the digits, to we don't care about permutations. We only consider different combinations for distinct products. If i consider for n=1e18, i have 18 digits, to choose from digits [1,9] (let's ignore 0). This can be given by stars and bars as, (n+r-1)C(r-1). that is choosing a non zero value for (x1+x2+x3....x9) = 18 where x1 -> number of digits '1', and so on. This number comes out to be around 1e6 when i computed it. you can similarly compute it for 1,2,3,..18 and i'm sure it won't exceed 1e7. rest of the states are pretty small so we can squeeze them in the given constraints. (P.S. I'm really bad with numbers so i might've made some mistakes but you get the idea)
•  » » » » » 3 years ago, # ^ |   +1 Woah, I was looking for a upper_bound too. I have 2 doubts now This number comes out to be around 1e6 when i computed it. you can similarly compute it for 1,2,3,..18 and i'm sure it won't exceed 1e7. Why would you also computer for upto 18, if I understood it properly x(digit) stands for no of that particular digits used and 9 is the biggest digit ? rest of the states are pretty small so we can squeeze them in the given constraints. If you see my submission, its running in about 290 ms. Which is pretty low for 20 * 2 * 2 * 1e6 * log ? Is there a reason here ?
•  » » » » » » 3 years ago, # ^ |   +4 Answer to first doubt. (it's actually 17, not 18, my bad) x1+x2+....x9 = 17 so if i have x1=15 and x2=2, and rest zero, I get the number 11111111111111122. (or any permutation of it). The number can be of 17 digits, since n<=1e18 and i have to choose digits [1,9] to fill these 17 vacancies. Second doubt: I think the answer lies with the fact that not all dp states are calculated. 20*2*1e16*log would be the very worst case which doesn't happen in most problems. Well, honestly i have no good answer to why the size of the map is the order of 1e5 when you print it in the the third sample, but i think what i mentioned has something to do with it,
•  » » » » » » » 3 years ago, # ^ |   +4 Yeah, seems that the actual values getting hit as states in the problems are still very few than the above upper bound. Anyways, thanks, that helped.
•  » » » » » » » » 3 years ago, # ^ |   +3 Also something i missed, the number of distinct products is even lesser than what i mentioned bcoz i only counted the combinations. but few combinations can give same products. prod(14) = prod(22). so it's way lesser than what i mentioned.
•  » » » » » » » » » 3 years ago, # ^ |   0 Ok, now its pretty satisfactory that why the distinct values are pretty low. Thanks a lot !
 » 3 years ago, # |   +3 Is there a way to interpolate using the Atcoder library?
 » 3 years ago, # |   0 I tried this solution for problem B. can someone please tell me why this code is not giving any output for large inputs(i.e input greater than 30000? for small inputs, it is giving correct output my code#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long t; t=1; // cin>>t; vector v(10); v[0]=1; for(long long i=1;i<10;i++) { v[i]=v[i-1]*(i+1); } while(t--) { long long n; cin>>n; long long dp[11][n+1]; for(long long i=0;i=v[i-1]) { dp[i][j]=min(dp[i][j-v[i-1]]+1,dp[i-1][j]); } else dp[i][j]=dp[i-1][j]; } } cout<
•  » » 3 years ago, # ^ |   0 Declare your 'dp' array globally. Size of the array is too large (10^8) to be declared locally
•  » » » 3 years ago, # ^ |   0 thank you. learned a new thing today
•  » » » » 3 years ago, # ^ |   0 Better use vectors.
•  » » » 3 years ago, # ^ |   0 For later, if you're doing a coin change dp, do something like this: You only need 1D dpint dp[MAXN]; void precalc() { fill_n(dp, MAXN, INF); for (int c: coins) { for (int i = c; i < MAXN; i++) { dp[i] = min(dp[i], dp[i-c]+1); } } } Also if there were more than one test case, it'd be much better to pre-calculate it outside the test case loop (because otherwise you'd have a complexity of $O(T * 10^8)$).
 » 3 years ago, # |   0 Can someone prove how the number of states is limited in this(the code is clean) solution?
•  » » 3 years ago, # ^ | ← Rev. 4 →   +16 Obviously, the numbers of possible x, z, and w are $d :=log N$ (the number of digits in $N$), $2$, and $2$, respectively. The non-trivial part is y. How many possible "products of digits" are there? Actually, every product of digits has only factors 2, 3, 5, and 7. Plus, the upper bound of the product is $9^d$, or more loosely $10^d \simeq N$. Now every product except for $0$ can be expressed in a form of $2^a 3^b 5^c 7^d$ for some non-negative integers $(a, b, c, d)$, and the product is $\leq N$. Applying logarithmic function we obtain $a \log 2 + b \log 3 + c \log 5 + d\log7 \leq \log N$. How many tuples of integers are there that satisfies this inequality? It is equal to the number of grid points in a certain "pyramid" on a 4-dimensional space (which is technically called a simplex). Since the number of grid points is approximately equal to the volume, we can estimate the number as $\dfrac{\log N}{\log 2} \cdot \dfrac{\log N}{\log 3} \cdot \dfrac{\log N}{\log 5} \cdot \dfrac{\log N}{\log 7} \cdot \dfrac{1}{4!} \simeq 51555$.Alternatively, with the observation of prime factors being $2, 3, 5, 7$, one can just write a simple code to verify the number is small enough: #include using namespace std; using ll = long long; int main() { ll cnt = 0; ll n = 1'000'000'000'000'000'000LL; for(ll a = 1; a <= n; a *= 2) { ll na = n / a; for(ll b = 1; b <= na; b *= 3){ ll nb = na / b; for(ll c = 1; c <= nb; c *= 5){ ll nc = nb / c; for(ll d = 1; d <= nc; d *= 7){ cnt++; } } } } cout << cnt << endl; } 
•  » » » 3 years ago, # ^ |   0 Hey, one doubt, why divide by 4! for estimation?I know that we should divide by something because we have multiplied the maximum values of a, b, c, d by why 4!, how did you estimated that ?Thanks!
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Consider the one-dimensional object $0 \leq x;\quad x \leq 1$(it is actually a segment). Its "volume" (i.e. its length) is obviously $1$.Then consider the two-dimensional object $0 \leq x, y;\quad x + y \leq 1$(it represents a triangle). Its "volume" (i.e. its area) is 1/2.Now consider the three-dimensional object $0 \leq x, y, z; \quad x + y + z \leq 1$(it looks like a pyramid). Its "volume" (yes, literally volume!) is 1/6 = 1/(3!).Analogously, the four-dimensional object $0 \leq x, y, z, w; \quad x + y + z + w \leq 1$(which I referred to as a "pyramid" in the comment above, or formally a "simplex") has the volume 1/(4!).One can prove that the simplex's volume is actually \$\dfrac{1}{4!}$by$$\displaystyle V = \int_0^1 dx \int_0^x dy \int_0^y dz \int_0^z dw = \int_0^1 dx \int_0^x dy \int_0^y dz\; z = \int_0^1 dx \int_0^x dy\; \frac{1}{2}y^2 = \int_0^1 dx\; \frac{1}{2} \cdot \frac{1}{3} x^3 = \frac{1}{2} \cdot \frac{1}{3} \cdot \frac{1}{4} = \frac{1}{4!}.$
•  » » » » » 3 years ago, # ^ |   +8 Thanks a lot for taking time and writing this, finally got it, it is absolute beautiful that how we can arrive at non trivial results from absolute basic stuff.Thanks again.