We will hold AtCoder Beginner Contest 204.
- Contest URL: https://atcoder.jp/contests/ABC204
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210606T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: kyopro_friends
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
Similarly to the "Discuss" tab linking respective CF blogs for regular rounds, could you please consider adding one for beginner rounds as well?
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?
Take path in both and upsolve both later :)
If it's not a big secret, what's your atcoder handle? I see that you successfully participated in the codeforces contest on the same day and got a positive rating change (which means that your performance didn't show any signs of being degraded).
I looked at the profiles of those commenters in this blog, who mentioned that they participating in the atcoder contest. Some of them participated in the codeforces contest too, but there were a lot of people who skipped it.
Again, the biggest problem for me is that I just can't get the atcoder contest out of my head after it ends:
In the abc203 contest I got the first incorrect solution for problem E submitted only 2 minutes after the contest ended and got it accepted 13 minutes later.
In the abc204 contest I had some troubles with problem C, skipped it and managed to solve D on the last minutes of the contest. I forced myself not to think about the unsolved problem C, but this only made me disturbed and unhappy instead having a clear mind for the upcoming back-to-back codeforces contest. I tried to read the codeforces contest problem A statement and solve it. But this didn't end well, because it took me 53 minutes to get something that worked with the sample input. So I bailed out without submitting this solution.
Now a similar dilemma is going to happen again this weekend. The atcoder abc205 contest will end roughly 2 hours before the start of Codeforces LATOKEN Round 1 (Div. 1 + Div. 2). I guess, it's best for me not to be greedy and instead focus on just a single contest per day. It's great that participating in two ranked contests per day works fine for you, but apparently I'm not ready for that yet.
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.
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/23252742
this is my submission can someone tell what is wrong with my approach.
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).
that's why i have checked it in range sqrt + [-5,+5]
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.
Ah shit!
My disappointment is immeasurable and my day is ruined.
BTW thank you
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.
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?
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.
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:
So, applying this, we get
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.
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>=0
We can check for both ceil(x) and floor(x) and take the one which minimizes the total time f(x).
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
My incorrect solution of ternary search passed, in that I used r-l>500 and it worked may due to weak tests
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
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.
Hi,
Did you figure out how to do it with ternary search?
YES
D was a harder version of this
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?
For F I wrote a dp for first 2 columns and then used matrix expo. Can anyone tell me what should I change in this code to make this work or is this approach itself is
wrong?
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
you can use matrix exponentiation to reduce m term to log(m)
Why in E have to wait in city until nearly sort(d) time?
And how to solve F?
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.
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?
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.
Let's say t1, t2 are the times to reach some node A st, t1<t2 and both t1, t2 > sqrt(di). Then how will you prove that t1 will be optimal to choose?
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
Agreed. Thanks for the explanation
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.
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.
I think berlekamp massey can be used in F, am i right??
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/23248639
Here is the dp code I used to generate the terms : https://www.ideone.com/48ZQxf
Nice, I had the exact same idea but for small values I was stupidly using backtracking, should have gone for bitmask dp. thanks btw.
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 :(
Can somebody explain that why didn't ternary search work in finding the best time to move in E ?
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.
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.
It actually does work if you don't floor the second summand in the expression. My submission.
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.
Can anyone explain Task E's approach ???
can anyone recommend me a similar type of (graph)/(shortest path) problems?
I found someone else's solution using greedy for problem D.
https://atcoder.jp/contests/abc204/submissions/23253738
Why is this solution wrong?
https://atcoder.jp/contests/ABC204/submissions/23234922
Correct answer is 45, while your code outputs 48.
Weak Tests
Actual solution : 9
Solution that this submission prints : 8
Nope, this solution also gives 9
Oh, I think there is some misunderstanding, I am replying to alwyn
how to solve C?
make every city as starting point (start dfs from every city) and see how many cities you can visit for that starting point.
Or if you are in mood of mememing around, you can do scc + dag condensation + bitsets (ironically which I did)
Does anyone know why this solution fails on 3 tests? -> https://atcoder.jp/contests/abc204/submissions/23262102
Because your
define int long long
is not beforetypedef pair<int, int> pii
, which will lead to overflow.Great work :D
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 - Дедлайн
While solving F, I got dp with broken profile vibes. But the state mapping was simpler.
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