We will hold AtCoder Beginner Contest 208.
- Contest URL: https://atcoder.jp/contests/abc208
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210704T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: Nyaan
- Tester: Kodaman
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
downvote if you have tiny pp.
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.
Guys like you are like a mad rabid dog who needs to be put to sleep legally
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 Powers
Lagrange polynomials in a "Beginner Contest".
Floyd-Warshall algo without modifications in D, problemsetters are you serious?
How to solve D?
just read the description of the algo
Okay Thanks. :)
Why not? It's ABC meant to be educational.
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 .
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
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
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.
I think it is obvious, isn't it?
For someone who understands the algorithm, yes.
D was not graphs, it was just dp.
dp on graphs lol
So what do you expect in a "beginner's" contest? Problems like F?
problems, where I have to think(also, don't forget, it's D for 400 points)
Well, if you didnt know the working of FW, you would have to spend some time with the algorithm.
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.
Pratik-Kumar Algorithm orz
In F, $$$O(MKlog(mod))$$$ was giving TLE. Were you expecting $$$O(M*K + (M+K)log(mod))?$$$ The TL was too strict.
.
You would only need one inverse if you compute factorials properly.
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?
Mine is O(MK + M + K)
Because you only need one inverse. But TL is still a little bit strict.
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?
Because for inverse factorials you should do this.
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.
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?
No.
Can someone please explain E in more simple words?
editorial is not quite clear to me
I used 5 states DP to solve it , I am presuming that you know basic Digit DP.
map<lli,lli> 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
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.
4D dp is sufficient for solving the problem (use map for storing dp) The dp will look something like this :- ~~~~~
map<pair<pair<int,int>,pair<bool,bool> >,int>dp; // {{pos,prod},{tight,st}}
~~~~~
So if u know basics of digit dp , this problem can be solved :) For reference : My Accepted Code(c++)
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.)
Problem D was very nice!
Unluckily,somebody have seen this thick.....
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))$$$
Isn't this the answer for $$$f(n, m)$$$ when $$$n > 0$$$ in problem F?
Yes, but how to calculate that for a huge N
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.
Bad decision starting with F. lol
UPD: No, my calculation is just plain wrong.
Oh, I got
You count the paths from $$$f(n,m)$$$ to $$$f(i,0)$$$ and multiply by $$$i^K$$$ for all $$$i$$$. Is that the same?
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$$$).
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!
Can someone please give a rigorous proof of upper_bound for E's naive top down solution's complexity ?
Do you mean why the number of distinct products fits in constraints?
Yes. Is there a convincing proof of this thing ?
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)
Woah, I was looking for a upper_bound too. I have 2 doubts now
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 ?
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 ?
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,
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.
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.
Ok, now its pretty satisfactory that why the distinct values are pretty low. Thanks a lot !
Is there a way to interpolate using the Atcoder library?
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
Declare your 'dp' array globally. Size of the array is too large (10^8) to be declared locally
thank you. learned a new thing today
Better use vectors.
For later, if you're doing a coin change dp, do something like this:
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)$$$).
Can someone prove how the number of states is limited in this(the code is clean) solution?
Obviously, the numbers of possible
x
,z
, andw
are $$$d :=log N$$$ (the number of digits in $$$N$$$), $$$2$$$, and $$$2$$$, respectively. The non-trivial part isy
. 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:
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!
Consider the one-dimensional object
(it is actually a segment). Its "volume" (i.e. its length) is obviously $$$1$$$.
Then consider the two-dimensional object
(it represents a triangle). Its "volume" (i.e. its area) is 1/2.
Now consider the three-dimensional object
(it looks like a pyramid). Its "volume" (yes, literally volume!) is 1/6 = 1/(3!).
Analogously, the four-dimensional object
(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!}. $$$
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.