chokudai's blog

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

»
7 weeks 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?

»
7 weeks 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?

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

    Take path in both and upsolve both later :)

    • »
      »
      »
      7 weeks 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.

»
7 weeks 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.

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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).

      • »
        »
        »
        »
        7 weeks 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]

        • »
          »
          »
          »
          »
          7 weeks 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.

          • »
            »
            »
            »
            »
            »
            7 weeks 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

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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?

      • »
        »
        »
        »
        7 weeks 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.

      • »
        »
        »
        »
        7 weeks 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.

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

          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; $$$
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is better than editorial, just take derivate :)

  • »
    »
    7 weeks 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).

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks 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.

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

D was a harder version of this

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

    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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How was D different? I couldn't understand that

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it +13 Vote: I do not like it
    Easy D Solution
»
7 weeks 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?

»
7 weeks 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?

»
7 weeks 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

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

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey! I_love_Alice, from where you learned can you please share, I understood

    Unable to parse markup [type=CF_MATHJAX]

    but not the matrix expo algo, how initial matrix is calculated, why this works etc.

    Thanks!

»
7 weeks 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?

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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?

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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?

          • »
            »
            »
            »
            »
            »
            7 weeks 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

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Agreed. Thanks for the explanation

      • »
        »
        »
        »
        7 weeks 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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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; $$$
  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
7 weeks 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 ?

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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.

»
7 weeks 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?

»
7 weeks 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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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)

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

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?

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

    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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Explanation and code of problem A to D .Link

»
7 weeks 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

  • »
    »
    7 weeks 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.

»
7 weeks 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

»
7 weeks 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.

»
7 weeks 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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, why doesn't greedy works here? I can't understand it intuitively.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)