### chokudai's blog

By chokudai, history, 12 months ago,

We will hold AtCoder Beginner Contest 204.

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

We are looking forward to your participation!

• +42

 » 12 months ago, # |   +18 Similarly to the "Discuss" tab linking respective CF blogs for regular rounds, could you please consider adding one for beginner rounds as well?
 » 12 months ago, # |   0 It's very unfortunate that AtCoder beginner contests are happening on the same days as Codeforces contests with only ~1 hour gap between. Last week I tried to participate in AtCoder beginner contest 203 for the first time and this made me skip Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2). I maybe could have taken part in both contests if I didn't try to upsolve problems from the AtCoder contest after it ended, but instead opted to take a rest and eat something. By the time when the Codeforces contest was about to start, I was hungry and somewhat tired and still thinking about the problems from the other contest.Today it's the same situation and I need to choose between AtCoder and Codeforces contests again. Or maybe try to take part in both. What do the others do about it?
•  » » 12 months ago, # ^ |   +24 Take path in both and upsolve both later :)
 » 12 months ago, # | ← Rev. 2 →   +17 How to solve E? I was trying to find the connection between the time cost and the basic inequality ($x+y\geq 2\sqrt{xy}$) but failed.
•  » » 12 months ago, # ^ |   +1 I thought of using dijkstra.For every road at time t most optimal time of starting is sqrt(d)-1 if t is already greater than this then go ahead otherwise make t = sqrt(d)-1 and calculate the ans.this approach passes for 30 testcases and gives wa on 5.https://atcoder.jp/contests/ABC204/submissions/23252742this is my submission can someone tell what is wrong with my approach.
•  » » » 12 months ago, # ^ |   0 You should check sqrt(d) too, since sqrt(d) might not be integer. For example, in case of d = 3, 1 + floor(3 / 2) < 0 + floor(3 / 1).
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 that's why i have checked it in range sqrt + [-5,+5]
•  » » » » » 12 months ago, # ^ |   0 Oh, I see. Sorry, when I reply I haven't read your code yet. Just read your idea in the comment. For WA, you get because you set the upper bound as 1e9, which isn't enough, imagine you walk through 2 edges with C = 1e9. For TLE, I'm not quite sure, but I think it's because you use set. I recommend you try PQ instead.
•  » » » » » » 12 months ago, # ^ |   +1 Ah shit!My disappointment is immeasurable and my day is ruined.BTW thank you
•  » » 12 months ago, # ^ | ← Rev. 7 →   +11 Imagine we wait for $k$ seconds. Then time of arrival will be $t+k+c+\frac{d}{t+k+1}$. We want to minimise this term. We take the derivative to $k$ and obtain $1-\frac{d}{(t+k+1)^2}$. We set this 0 and solving for $k$ yields $k=\sqrt{d}-t-1$ (Or the final time $t_{arrive}=t+k=\sqrt{d}-1$). $k$ must be 0 or bigger, so we clamp it to 0. (also I checked all values $k \pm 2$ to find the minimum and ignore rounding errors)The rest is just dijkstra then.
•  » » » 12 months ago, # ^ |   +3 But this is just what your taking in moving only one step. Our path may consists of several edges too.Why are we not adding them all? And then how can we find derivative?
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   +3 The calculation is: If we are at time $t$ and node $A$ and want to use an edge with $C$ and $D$ to node $B$, then how long should we wait to minimize the cost. This minimum cost is the real cost of the edges. We can do this for all edges at all times. Then we can use Dijkstra. For the derivative I recommend you search for "Chain rule" and "Derive Polynomial". Alternativly you can use Ternary Search to find the minimum time. I think this should still fit into the time limit, I didn't try though.
•  » » » » 12 months ago, # ^ | ← Rev. 4 →   +11 The fact is you don't need to, just use the simple inequality I mentioned before: $x+y \geq 2\sqrt{xy}$ (which is simply $A_n \geq G_n$)Proof: $x+y \ge 2 \sqrt{xy} \Leftrightarrow x-2\sqrt{xy}+y \ge 0 \Leftrightarrow (\sqrt{x} - \sqrt{y})^2 \ge 0$So, applying this, we get $t+k+c+\dfrac{d}{t+k+1} = (t+k+1+\dfrac{d}{t+k+1})-1+c \geq 2\sqrt{d}-1+c$The equality holds when $(t+k+1)^2=d$, so $k=\sqrt{d}-t-1$Fun fact: We call this function $f(x)=x+\dfrac{t}x$ the "Nike function" in some place in China because it looks like the Nike logo.
•  » » » » » 11 months ago, # ^ | ← Rev. 3 →   0 original $cost=t+k+c+(d/(t+k+1))$after finding k; $if(\sqrt{d}>=time)$why we don't write $cost=(\sqrt{d} -1+c+(d/(\sqrt{d})$while many solutions written as $cost=(\sqrt{d}+c+(d/(\sqrt{d}+1)$as $k=\sqrt{d}-t-1;$
•  » » » 11 months ago, # ^ |   0 This is better than editorial, just take derivate :)
•  » » 12 months ago, # ^ | ← Rev. 2 →   +3 The solution is using Dijkstra's with a minor twist. The wait time at each city can be decided by minimizing the function:f(x) = t+x+c+d/(t+x+1), where t is the time we reached the node and x is the amount of stay/wait time at that node.We can solve for the derivate f'(x). And that gives, x = sqrt(d)-t-1. Also, x>=0We can check for both ceil(x) and floor(x) and take the one which minimizes the total time f(x).
•  » » 12 months ago, # ^ |   +4 E is in first place dijkstra.But of course we cannt check all possible waiting times at each vertex.We can optimze this by finding the optimal time to start to use edge i is sqrt(D[i]), (or sqrt(D[i])+1). So, whenever we start to traverse an edge we check if current time is less that the optimal start time.Submission
•  » » 12 months ago, # ^ |   0 My incorrect solution of ternary search passed, in that I used r-l>500 and it worked may due to weak tests
•  » » 12 months ago, # ^ |   0 normal dijkstra , when you arrive at node v and want to traverse through edge i to node u , total cost is c[i] + (D[i] / (t+1)) + t we want to minimize (D[i]/(t+1)) + t , minimum is achieved at t = sqrt(D[i]).So now if current time when you arrive at v is t ,let x = max(t,sqrt(D[i]) we update u's time as C[i] + (D[i]/(x+1)) + x
•  » » 11 months ago, # ^ |   +6 Why can't we solve E question using ternary search? I tried solving using ternary search but 6 tc were failing. In editorial also it is written that we cannot solve it using ternary search but no reason is given.
•  » » » 11 months ago, # ^ |   +7 Hi,Did you figure out how to do it with ternary search?
•  » » » » 11 months ago, # ^ |   +6 YES
 » 12 months ago, # |   +3 D was a harder version of this
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 problem D was classical subset sum problem.we just needed to find the sum which is closest to sum/2. where sum is the sum of the entire given array.
•  » » 12 months ago, # ^ |   0 How was D different? I couldn't understand that
•  » » 12 months ago, # ^ | ← Rev. 4 →   +13 Easy D Solution#include #define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);} int main(void){ fast; int n; cin>>n; int t[n],sum=0; for(int i=0;i>t[i]; sum+=t[i]; } bool dp[sum+1]={false}; dp[0]=true; for(int i=0;i=0;j--){ if(dp[j]){ dp[j+t[i]]=true; } } } int i,ans=sum; for(i=1;i<=sum;i++){ if(dp[i]) ans=min(ans,max(i,sum-i)); } cout<
 » 12 months ago, # | ← Rev. 2 →   +3 How to solve F ?I am sure we somehow have to utilize matrix exponentiation, but I am not sure how to build the matrix. It works somehow that we combine patters of the current column with possible following patterns (all submasks or the like), and then put somehow all pieces together.Somebody explain?
 » 12 months ago, # | ← Rev. 3 →   +8 How to solve F? I only know the naive DP Bitmask O(2^n*m)UPD: I just learnt that such a DP can be optimised using matrix multiplication and binary exponentiation. What a pity that this is the first time I learn this trick and only after the contest :(This naive solution can be optimised to this
•  » » 12 months ago, # ^ |   +3 you can use matrix exponentiation to reduce m term to log(m)
•  » » 11 months ago, # ^ |   0 Hey! I_love_Alice, from where you learned can you please share, I understood $O(n.m.2^n)$ but not the matrix expo algo, how initial matrix is calculated, why this works etc.Thanks!
 » 12 months ago, # | ← Rev. 2 →   +9 Why in E have to wait in city until nearly sort(d) time?And how to solve F?
•  » » 12 months ago, # ^ |   0 My approach was to use differentiation. Let T to be the time arrived at a vertex, and t to be the waiting time. Then to move onto the next vertex, it will take f(t) = t+ C + D/(T+t+1). If you see this as a function of t, then we find the first derivative which would be 1 — D/(T+t+1)^2, and when the first derivative is zero, the original function would be minimum. Hence, t = sqrt(D) -1-T.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 We have to minimise total time right from 1 to N. So, let it start from 1 at T and let t[1],t[x],.... t[N] be waiting time on every vertex from 1 to N path which will give answer optimally.then we have to minimise T + (t[1] + C[1]+ d/(T+1)) + (t[2]+C[2]+ d/(T + (t[1] + C[1]+ d/(T+1)))) .... and so on.Isn't it? Why we are using Greedy instead of DP type solution?
•  » » » » 12 months ago, # ^ |   +3 I think it is because that as long as you arrive at a vertex early, then you can simply wait it out until the cost function is minimized. So the greedy approach (dijkstra) works.
•  » » » » » 12 months ago, # ^ |   0 Let's say t1, t2 are the times to reach some node A st, t1 sqrt(di). Then how will you prove that t1 will be optimal to choose?
•  » » » » » » 12 months ago, # ^ |   0 Then it should be t1 because the first derivative will be always positive when t is greater than sqrt(di), so the cost function would be increasing,hence the minimal time should be optimal
•  » » » » » » » 12 months ago, # ^ |   0 Agreed. Thanks for the explanation
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 May be at first, we see that the states are node and time t at which we start our journey from here. But for all t < sqrt(di), it is always optimal to go to next node at sqrt(Di) (or some plus or minus 1 from this) as that will give the minimum time to reach the next node through this node. If t > sqrt(di) (where it had been optimal to arrive at next node), then we can do no good other than to directly go to next node as waiting will further increase the time to reach next node. So, it is good for us to directly maintain minimum time to reach each node as if that minimum time is greater than sqrt(Di) for a edge, we can do not good than this to reach next node through present node.
•  » » » 11 months ago, # ^ |   0 original $cost=t+k+c+(d/(t+k+1))$after finding k; $if(\sqrt{d}>=time)$why we don't write $cost=(\sqrt{d} -1+c+(d/(\sqrt{d})$while many solutions written as $cost=(\sqrt{d}+c+(d/(\sqrt{d}+1)$as $k=\sqrt{d}-t-1;$
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 The short explanation is, that before t=sqrt(D[i]) each second waiting gives back 1 or more second less travel time, and after t=sqrt(D[i]) each second waiting gives back only 1 or less second.
 » 12 months ago, # |   0 I think berlekamp massey can be used in F, am i right??
•  » » 12 months ago, # ^ |   0 Yes, I used a 4 state dp to generate 144 terms for each width, and depending on which width is given, I used Berlekamp Massey. My code is a bit ugly though: https://atcoder.jp/contests/abc204/submissions/23248639Here is the dp code I used to generate the terms : https://www.ideone.com/48ZQxf
•  » » » 11 months ago, # ^ |   0 Nice, I had the exact same idea but for small values I was stupidly using backtracking, should have gone for bitmask dp. thanks btw.
 » 12 months ago, # |   +8 I realized today a strong weakness of binary and ternary searches on non-strict convex functions. Tried so hard to get E pass, but couldn't get past 26 AC :(
 » 12 months ago, # |   +6 Can somebody explain that why didn't ternary search work in finding the best time to move in E ?
•  » » 12 months ago, # ^ |   +8 Yes, because the function was not strictly decreasing and then strictly increasing. For instance, I tried this predicate f(mid) > f(mid + 1), which is not monotonous when the function is like a staircase, as in for eg: decrease — stays constant, decrease, increase — stay constant, increase.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +8 For me, the ternary search only passed ~ 20 cases. I think ternary search is not working since the floor of the division is not monotonous. For example 6/4 = 6/5 = 6/6. Hence increasing the denominator from 4 to 6 kept the floor of the division the same.
•  » » 12 months ago, # ^ |   +38 It actually does work if you don't floor the second summand in the expression. My submission.
•  » » » 12 months ago, # ^ |   +8 That is genius in a way. Why didn't I think of doing that of all weird things I was doing. Ah, excellent problem anyway.
 » 12 months ago, # |   0 Can anyone explain Task E's approach ???can anyone recommend me a similar type of (graph)/(shortest path) problems?
 » 12 months ago, # |   0 I found someone else's solution using greedy for problem D.https://atcoder.jp/contests/abc204/submissions/23253738
•  » » 12 months ago, # ^ |   0 Why is this solution wrong?https://atcoder.jp/contests/ABC204/submissions/23234922
•  » » » 12 months ago, # ^ |   0 8 16 14 13 13 12 10 9 3 Correct answer is 45, while your code outputs 48.
•  » » 12 months ago, # ^ |   0 Weak Tests Counter test for this submission3 9 4 3 Actual solution : 9Solution that this submission prints : 8
•  » » » 12 months ago, # ^ |   0 Nope, this solution also gives 9
•  » » » » 12 months ago, # ^ |   0 Oh, I think there is some misunderstanding, I am replying to alwyn
 » 12 months ago, # |   0 how to solve C?
•  » » 12 months ago, # ^ |   0 make every city as starting point (start dfs from every city) and see how many cities you can visit for that starting point.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +7 Or if you are in mood of mememing around, you can do scc + dag condensation + bitsets (ironically which I did)
 » 12 months ago, # | ← Rev. 2 →   0 I was able to solve D just after one minute of contest end. It took me one hour to see that it is another version of subset sum problem. Can anyone tell how many of you find this observation so quickly and is there any proof for the observation?
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 I think the key observation is that for every possible subset sum i inside the range [0, sum/2], there is always a corresponding subset sum sum - i. The answer is sum - i where i is the biggest i in the range [0, sum/2] where dp[i] = true. Hope this helps.
 » 12 months ago, # |   0 Explanation and code of problem A to D .Link
•  » » 11 months ago, # ^ |   0 Thanks
 » 12 months ago, # |   0 Does anyone know why this solution fails on 3 tests? -> https://atcoder.jp/contests/abc204/submissions/23262102
•  » » 11 months ago, # ^ |   +11 Because your define int long long is not before typedef pair pii, which will lead to overflow.
•  » » » 11 months ago, # ^ |   0 Great work :D
 » 11 months ago, # |   0 Here's a problem similar to E in terms of the minimizing the function, since the proof part in the AtCoder isn't up yet, you can refer to the editorial of this problem for the proof. 1288A - Deadline
 » 11 months ago, # |   0 While solving F, I got dp with broken profile vibes. But the state mapping was simpler.
 » 11 months ago, # | ← Rev. 4 →   0 My code for E — Rush Hour 2 is getting TLE on one case. This is my code-Submission Can somebody point out the error please?Edit 1: The same solution with set instead of Priority Queue is giving AC. Submission I can't understand the reason.Edit 2: I understood the reason
 » 11 months ago, # |   0 In problem D, why doesn't greedy works here? I can't understand it intuitively.
•  » » 11 months ago, # ^ |   0 Yup, same doubt, only after getting WA in greedy I went for DP, and if constraint weren't giving a hint for dp, I would have continued finding bug in my DP, someone please explain why greedy doesn't work (don't say try this example, please give an argument)
 » 4 weeks ago, # |   0 The question D which name is $"cooking"$ is easy. Use $\huge\texttt{DP}$ can solve.