chokudai's blog

By chokudai, history, 3 years ago, In English

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!

  • Vote: I like it
  • +42
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Similarly to the "Discuss" tab linking respective CF blogs for regular rounds, could you please consider adding one for beginner rounds as well?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Take path in both and upsolve both later :)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        that's why i have checked it in range sqrt + [-5,+5]

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Ah shit!

            My disappointment is immeasurable and my day is ruined.

            BTW thank you

  • »
    »
    3 years ago, # ^ |
    Rev. 7   Vote: I like it +11 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 4   Vote: I like it +11 Vote: I do not like it

        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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My incorrect solution of ternary search passed, in that I used r-l>500 and it worked may due to weak tests

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

D was a harder version of this

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +13 Vote: I do not like it
    Easy D Solution
»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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?

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

CODE (doesn't even pass the samples)

wrong?

»
3 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you can use matrix exponentiation to reduce m term to log(m)

»
3 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Why in E have to wait in city until nearly sort(d) time?

And how to solve F?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think berlekamp massey can be used in F, am i right??

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 :(

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can somebody explain that why didn't ternary search work in finding the best time to move in E ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    It actually does work if you don't floor the second summand in the expression. My submission.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain Task E's approach ???

can anyone recommend me a similar type of (graph)/(shortest path) problems?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found someone else's solution using greedy for problem D.

https://atcoder.jp/contests/abc204/submissions/23253738

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    make every city as starting point (start dfs from every city) and see how many cities you can visit for that starting point.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      Or if you are in mood of mememing around, you can do scc + dag condensation + bitsets (ironically which I did)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know why this solution fails on 3 tests? -> https://atcoder.jp/contests/abc204/submissions/23262102

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Because your define int long long is not before typedef pair<int, int> pii, which will lead to overflow.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

While solving F, I got dp with broken profile vibes. But the state mapping was simpler.

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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