chokudai's blog

By chokudai, history, 4 months 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

 » 4 months ago, # | ← Rev. 3 →   -100 downvote if you have tiny pp.
•  » » 4 months 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.
•  » » 4 months ago, # ^ |   -91 jisne downvote mara uski maa ramdi
•  » » 4 months ago, # ^ |   +2 Guys like you are like a mad rabid dog who needs to be put to sleep legally
 » 4 months 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".
•  » » 4 months ago, # ^ |   -15 bruh it is 7:08 right now , wait pls
 » 4 months ago, # |   +1 Floyd-Warshall algo without modifications in D, problemsetters are you serious?
•  » » 4 months ago, # ^ |   +7 How to solve D?
•  » » » 4 months ago, # ^ |   +5
•  » » » » 4 months ago, # ^ |   0 Okay Thanks. :)
•  » » 4 months ago, # ^ |   0 Why not? It's ABC meant to be educational.
•  » » » 4 months 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 .
•  » » » 4 months 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
•  » » 4 months 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
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   -14 I think it is obvious, isn't it?
•  » » » » 4 months ago, # ^ |   +15 For someone who understands the algorithm, yes.
•  » » 4 months ago, # ^ |   0 D was not graphs, it was just dp.
•  » » » 4 months ago, # ^ |   0 dp on graphs lol
•  » » 4 months ago, # ^ |   0 So what do you expect in a "beginner's" contest? Problems like F?
•  » » » 4 months ago, # ^ |   0 problems, where I have to think(also, don't forget, it's D for 400 points)
•  » » » » 4 months ago, # ^ |   0 Well, if you didnt know the working of FW, you would have to spend some time with the algorithm.
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   +2 Pratik-Kumar Algorithm orz
 » 4 months 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.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 .
•  » » 4 months ago, # ^ |   0 You would only need one inverse if you compute factorials properly.
•  » » » 4 months 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?
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   0 Mine is O(MK + M + K)Because you only need one inverse. But TL is still a little bit strict.
•  » » » » » 4 months 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?
•  » » » » » » 4 months 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); }
 » 4 months 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.
•  » » 4 months 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?
•  » » » 4 months ago, # ^ |   +12 No.
 » 4 months ago, # |   +4 Can someone please explain E in more simple words? editorial is not quite clear to me
•  » » 4 months 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
•  » » 4 months 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.
•  » » 4 months 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++)
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 Almost understood all except the "st" part, can you elaborate little more??upd: Got it !
•  » » 4 months 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.)
 » 4 months ago, # |   +14 Problem D was very nice!
•  » » 4 months ago, # ^ |   0 Unluckily,somebody have seen this thick.....
 » 4 months ago, # |   0 My D solution passed example test cases and some of the hidden test cases. But still can't figure out why it gave WA. I used DP. Can anyone help me figure out what is error in my code. Here is my submission Submitted Code
 » 4 months 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))$
 » 4 months 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 )$
•  » » 4 months ago, # ^ |   0 Yes, but how to calculate that for a huge N
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   +14 Bad decision skipping E and going for F. Bad decision starting with F. lol
•  » » 4 months 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?
•  » » » 4 months 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$).
•  » » » » 4 months 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!
 » 4 months ago, # |   -20 ABC in 25 minutes then waiting for contest to end tried F with vey bad and illogical medthod if n>30 n=30 and then dp but it passes 11/35 only can anyone explain problem D ??
 » 4 months ago, # | ← Rev. 2 →   +3 Can someone please give a rigorous proof of upper_bound for E's naive top down solution's complexity ?
•  » » 4 months ago, # ^ |   +1 Do you mean why the number of distinct products fits in constraints?
•  » » » 4 months ago, # ^ |   +3 Yes. Is there a convincing proof of this thing ?
•  » » » » 4 months 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)
•  » » » » » 4 months 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 ?
•  » » » » » » 4 months 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,
•  » » » » » » » 4 months 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.
•  » » » » » » » » 4 months 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.
•  » » » » » » » » » 4 months ago, # ^ |   0 Ok, now its pretty satisfactory that why the distinct values are pretty low. Thanks a lot !
 » 4 months ago, # |   +3 Is there a way to interpolate using the Atcoder library?
 » 4 months 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<
•  » » 4 months ago, # ^ |   0 Declare your 'dp' array globally. Size of the array is too large (10^8) to be declared locally
•  » » » 4 months ago, # ^ |   0 thank you. learned a new thing today
•  » » » » 4 months ago, # ^ |   0 Better use vectors.
•  » » » 4 months 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)$).
 » 4 months ago, # |   0 Can someone prove how the number of states is limited in this(the code is clean) solution?
•  » » 4 months 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 months 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 months 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 months 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.