chokudai's blog

By chokudai, 9 months ago, In English

We will hold AtCoder Beginner Contest 164.

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

We are looking forward to your participation!

Addition: About the Unrated ABC163

We are sorry for the inconvenience.

The server down during the last contest was caused by a sudden access to the ALB, and we found that we could solve this problem by doing Pre-Warming.

Also, the bug where the problem statement does not show up has been resolved by changing the caching algorithm. The problem with submissions showing up as IE (Internal Error) was due to the Judge server's scoring algorithm being different than in the past. This too has already been fixed.

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

»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Just out curiosity, rating 1999 in Atcoder is roughly how much in CF?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    2200-2300

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +75 Vote: I do not like it

      Damm 2200 is a beginner

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it -41 Vote: I do not like it

      I think it's around 1800-1900 on cf

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +34 Vote: I do not like it

        I'm 1400~1500 on Atcoder.

        If 1999 on Atcoder means 1800~1900 on CF.

        Than I'm 1200~1300 on CF.

        Hello everyone I'm a beginner.

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

          Common, it might not be your saturation level (might not have attended enough contest)

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

          In AtCoder, when you participate in only a few contests your rating is much lower than your actual strength. You need to participate in at least 10 contests in order to get accurate rating.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I just participated in a few contests and now have around 1550. Are you sure what you're telling is true?

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It will need a little more contest for your rating to be converged enough to your "actual" rating, because the rating shown is actually the lower bound of ninety-something-percent confidence interval of rating. Generally it needs about 14 times of participation to rated contests until the rating shown becomes high enough. (The "provisional" hint shown on the left of your rating also suggests this)

»
9 months ago, # |
  Vote: I like it +16 Vote: I do not like it

hope everything will be fine this time!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope everyone will get full marks this round!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope it will never have problems(like 163) this time...

»
9 months ago, # |
  Vote: I like it -30 Vote: I do not like it

1000 points are enough for me !!!

»
9 months ago, # |
  Vote: I like it +59 Vote: I do not like it

I hate Matrix Construction.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I have given up.

    F is too hard to solve for me.

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

      Am I the only one who did a randomized solution for F?

      My method was like this:

      • First, decompose the matrix into 64 layers, with one layer for each bit, since bits on different layers don't affect each other.
      • Then, for each enforcement that's "AND = 1" or "OR = 0", set the corresponding row/column to 1 or 0.
      • If there are collisions (one cell set to both 1 and 0) then immediately return impossible,
      • Otherwise, for each of the cells that were neither assigned 0 nor assigned 1, randomly assign it 0 or 1.
      • Check if the resulting matrix fulfills requirements.
      • If not, randomly assign them again. If you have assigned them enough times (100000) and each time it failed, return impossible,

      Code

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

        Unfortunately your solution fails against the following test case. Your solution outputs -1, but a valid answer exists.

        Test Case

        Similar input with larger input leads to TLE too.

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

          Ah, I see — this is one of the test cases with exactly one solution? Thanks for hacking my wrong method!

          I initially expected that there would either be a lot of possible outputs or none at all. Turns out I was wrong :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I like problem F last time. But I have to give up this time.

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

How did you think of D?

»
9 months ago, # |
Rev. 2   Vote: I like it -94 Vote: I do not like it

E is much difficult

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Don't you realize you calculate the same pair twice

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1-indexed, for

    $$$1 \leq i \leq j \leq |S|$$$

    instead of

    $$$0 \leq i \leq j \le |S|$$$

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

    Usually the discussion starts after the contest finished.

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

    Haven't you seen the restrictions?

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

      oh by mistake i have get the result with bruteforce with array starting indexing convention . so sorry for that

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

My first Atcoder contest...wow, this is beginner? I'm stuck on D. Feel like an idiot.

»
9 months ago, # |
  Vote: I like it +17 Vote: I do not like it

How to solve E?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    it's easy to show that $$$5000$$$ silver coins is enough to go to every city,because you can go through every edge with them.so just break one city into $$$5000$$$ points $$$(city,money)$$$ and use dijkstra.

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

      isnt the maximum 2500

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      actually $$$2450$$$ is enough because the longest shorest path is not longer than $$$49$$$.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but i was silly so i used $$$5000$$$ XD

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

        How Can u say that Longest Shortest Path will no longer than 49?

        Also Explain How complexity is Calculated in editorial? TIA

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If there are at most 50 nodes then the the longest shortest path from vertex 1 (source) to any other vertex can be at most 49. If the weight is at most 50 then the total number of silver coins is 49 * 50 = 2450.

          The complexity is given by the running time for Djikstra's using an adj. list representation of a graph. More here: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time

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

      Just to be safe, I used up to 10000 silver coins, then did a state dijkstra.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        10000 got AC? At first I also wrote 2 * sum of edges (10000 at worst) to be safe but got TLE, then changed to sum of edges and got accepted.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The edges will be of the order N*5000*5000 when all c[i] are 1. Will dijksta run in time for this number of edges?

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 4   Vote: I like it +32 Vote: I do not like it

        You don't need that many edges. Just connect (node, coins) -> (node, coins + c[i])

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        No, the problem specifically says that the maximum number of edges is 100. Therefore, in the state graph the maximum number of edges is 100*5000 = 500000.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why so many edges?only $$$5000\times(n+2m)$$$ edges needed

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But can $$$O(n^4 logn)$$$ pass???

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "so just break one city into 5000 points"

      What do you mean by that ?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shortest path -> state [N][K] -> minimum time to reach node N with silver coin K. we can take Maximum K as 2500. since the max cost of an edge is 50. and we will at most take N-1 edges to reach target.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    I think my E is $$$O(A_{max}^2 * N^3)$$$. link to submission

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

    could someone spot the mistake in my code for E? been losing sleep over it submission

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nvm, fixed it.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how did you fix code? i met the same WA.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          my INF was too small

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            strange, i just used 9e10, but still failed in line_2.txt. which value you set for INF?

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I just tried 9e20 and AC. :)

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            thanks!

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D ?

»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

The English Commentary for Problem D: Multiples of 2019 is here

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot! That explanation helped me.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There must be simpler way, this is not level of D.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for a string 2114 pref[0] would give us 4%2019 pref[1] would give 14%2019 pref[2] would give 114%2019 and pref[3] would give 2114%2019. right? then you afterwards what you implemented using map is unclear to me. please explain this.

        map<ll,ll>mp;
        ll ans = 0;
        for(ll i=0;i<n;i++)
        {
            if(pref[i]==0)ans++;
            ans+=mp[pref[i]];
            mp[pref[i]]++;
        }
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It is just prefix sum logic.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am also not able to understand this part. Why adding ans += mp[pref[i]]; mp[pref[i]]++; Can any please explain?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    rep(j,0,2019){
                if (dp[j] > 0){
                    ll rem = (10*j + d)%2019;
                    if (rem == 0) ans+=dp[j];
                    tdp[rem]+=dp[j];
                }
            }
    

    can u please explain me this step and guide me how to develop these approaches efficiently?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi @archit_akg, The idea is whenever we get any remainder which has a frequency > 0, we will compute the remainder when we add the digit d to its end. Finally, in the array tdp, we are storing the frequency of remainders for the current index.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro i had a time complexity doubt since 10^8 takes 1 sec ,so 2019*2e5 =403800000 which should take 4 sec but soln is accepted.Can u explain ?

»
9 months ago, # |
  Vote: I like it -8 Vote: I do not like it

How you solve D? I used brute force but it gave me TLE? Do you have any ideas?

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    Just construct number from start contiguously and store frequency of remainder. If $$$n$$$ is length of string at stage $$$i$$$ number will be $$$\,\,\,N\,= \,d_0*10^{n-1}+d_1*10^{n-2}+...+d_{i-1}*10^{n-i-1}$$$

    let $$$R_i= N\mod2019$$$

    So at any stage if remainder is $$$R_i$$$ see how many time this remainder has occurred previously excluding current one and add this to final result. For this you ca just use an array or Map whatever.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That is nice explanation, thanks!

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I can't understand the logic that if for an index i,if the remainder is equal to the remainder at any other index j,then how the number formed by the elements between i& j would be divisible by 2019? Can someone please explain.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please provide me the code of this approach, I'm getting WA.

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

        Sure.this.

        And to explain his doubt. let's say remainder $$$r$$$ is same for two indices $$$i\,and\,j\,(i<j)$$$ so number formed at index $$$i\,and\,j$$$ will be of the form $$$N_i=2019*k_1+r\,\, and\, N_j=2019*K_2+r$$$ so number between segment $$$[i,j]$$$ will be $$$(N_j-N_i)$$$ whose remainder got canceled out and we got $$$2019*(K_2-K_1)$$$ which is clearly divisible by 2019.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain why your code to this input 12019 gives this output 2, but 12019 mod 2019 != 0?

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 6   Vote: I like it +9 Vote: I do not like it

      My explanation + code

      Take for example divisor = 13 and S = 39262.

      1. Reminder of 2 / 13 is 2, save it.
      2. Reminder of 62 / 13 is 10, save it.
      3. Reminder of 262 / 13 is 2, but we have already seen this reminder. What does it mean?

      (262 - 2) % 13 = 260 % 13 = 0, so 260 is a multiple of 13. But we are interested only in 26. Turned out if x * (any power of 10) mod divisor = 0, then x % divisor = 0 if divisor isn't 2 or 5.

      1. For 39262 / 13 reminder is again 2 and we have seen it two times: (39262 - 262) % 13 == 0 and (39262 - 2) % 13 == 0, so add them both.
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nice Explanation.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey, thanks for the detailed explanation. This problem is similar to ABC(atcoder beginner contest) 158E but I'm getting WA in 158E problem which is a general case. Here's my code Can you help in that?

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

          1st test is for P = 2 (you can see all test cases here). And for 2 and 5 "if x * 10^k % divisor = 0$, then x % divisor = 0" doesn't work. For example, 7 * 10 % 2 = 0, but 7 % 2 = 1.

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            So what how should I check divisibility for p=2 and p=5?

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              for case when divisor is 2 or 5 algorithm is just much easier:

              S = 3214, divisor = 2, skip 3, for 2 we have 2 and 32, skip 1, for 4 we have 4, 14, 214, 3214. We sum indices of digits that are divisible by our divisor.

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              A number is divisible by 2 if and only if its lowest digit is even.

              A number is divisible by 5 if and only if its lowest digit is 0 or 5.

              Storing a prefix counter of the appearances of $$$S_i$$$ such that $$$S_i == 0 \; (mod \; P)$$$ for $$$P = 2$$$ or $$$P = 5$$$ is enough.

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

        you considered all the numbers having the last digit as last character of s,what about the other numbers which do not have last character what i mean to say is - s=39262 you considered 2,62,262,9262,39262 what about 39,92,392 etc... Also why do we have to reverse the digits

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what do you mean by add them both? Thanks in advance

»
9 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Am I mistaken in saying that today's ABC D has an identical solution to ABC 158E? The two problems seem to be asking for exactly the same thing.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Actually today's problem is easier, for the modulo is given as 2019, which is a relatively prime of the base, 10.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I remembered that I had seen it, couldnt solve it neither then nor now.

»
9 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

Are standings hidden ?

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

    No

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is what I see during the whole contest and still it is showing the same.

      Standings

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        Click on the dropdown to the right of "Customize" and see if you have overly restrictive filters.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the approach for D ? I used the stoi and substr function , got WA.

»
9 months ago, # |
  Vote: I like it +68 Vote: I do not like it

The problem F can be easily solved by maximum-flow with lower bounds. See this submission.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +55 Vote: I do not like it

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

      Nice one :)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please elaborate more i don't understand is this graph for the first sample? i understand that you solve for each bit independently but how do you add the edges?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of this but I didn't have enough time to implement it :( Should it pass considering there can be around $$$64N^2$$$ vertices/edges?

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

      There are only $$$\mathrm O(n)$$$ edges not weighted $$$1$$$. I think the Dinic algorithm still runs in $$$\mathrm O(m+\sqrt mn)=\mathrm O(n^2)$$$ time although I can't proof it.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My approach

This is my approach which got me TLE I pre-computed all the modulo values but to find (L, R) pairs I had to use a nested for loop. Can someone please tell me how do I find the number of (L,R) pairs in O(n) time ?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please someone explain approach for D

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

My D approach
k starts from 0
Iterate from right and calculate (10^k%2019+digit at i-th index)%2019
store this in map and for every element in map calculate NC2 of that frequency

This problem is like calculating number of subarrays having sum%m as 0

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

    can you please explain why this problem is like calculating number of subarrays having sum%m as 0 ??

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are given a array you calculate prefix sum at every i-th index mod m
      Now if prefix sum at two index(suppose i & j) is same then there is a subarray from (i+1,j) whose sum will be zero. So we can store each sum in map and choose any two index having same sum in NC2 ways. In this question instead of prefix we calculate suffix sum + power of 10. And we can choose indexs in NC2 ways.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You could use vector.swap(v) instead of memcpy, which basically copies nothing but a pointer.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      indeed, the runtime would have been even smaller, but at this point, it's still very fast.

»
9 months ago, # |
  Vote: I like it +62 Vote: I do not like it

Why $$$0 <= a_{i, j} < 2^{64}$$$ in problem F? For some weird unsigned long long practice? :)

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I made me nervous that my codes were always CE. Actually,it's the "time" keyword that made this problem. Hope you all learn from my lesson.(How silly I was!) GL and HF.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain easy to implement solution for E?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$dp[i][silver]$$$ = shortest path from $$$1$$$ to $$$i$$$ such that you're left with $$$j$$$ silver coins.

    $$$silver$$$ is at most $$$2500$$$ — $$$(N * 50)$$$

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

      I am not able to understand how 2500*50 states can be minimized by n*m*2500 iterations (n is vertex). If we see bellman ford , n*n iteration is required to minimize all n vertexes.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      then what ?

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

HELP!!!

For problem E:

I used dp.

$$$dp[i][j][k]$$$ means now standing at the $$$i-th$$$ node ,and have $$$Min(600,j)$$$ silver coins the $$$minimal$$$ time to go to k.

We can use $$$dp[i][j][k]$$$ to update other situation as follow.

  • $$$dp[i][j][k]+d[i]$$$ to update $$$dp[i][max(j-c[i],0)][k] $$$
  • $$$dp[i][j][k]+(the—time—from—it—to—i)$$$ to update $$$dp[it][Min(600,j+(the—number—of—silver—coins—required—from—it—to—i))][k] $$$

And I used shortest path to update it,but I fail in the second test which is line(pass all of the others!),what's wrong?

https://atcoder.jp/contests/abc164/submissions/12395345

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

    I am sorry I can't help you with the issue but why 600 ?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I see

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

        I am not sure of what you see but is good to see that you can see something.

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

          I'm wrong , 600 is too small.Thank you very much.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is 600 sliver coins enough?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No ,I fix it ,but I get TLE now...

      Can you tell me if $$$O(n^4logn)$$$ can pass?

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        You can try the following :

        dp[i][j] denotes minimum time to go to the ith node with j silver coins from 1.

        Now repeatedly update this dp (n+1) times, as in bellman — ford. ( + 1 because initially I don't initialize it )

        UPD : There is a case where this gets Wrong Answer. Sorry. Theoretically it requires O(m*m) iterations.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can I see your code, thank you

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Here you go

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              thanks bro

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

              why iter n+1 times? for bellman-ford, it repeats at most n-1, plus 1 init should be n.

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

                Thanks for pointing this. I tried to figure out what went wrong and I found that my solution is wrong as it requires O(n*n) iterations.

                It passed due to weak testcase.

                Testcases where I get WA : (An extension to 3rd sample case)

                4 7 25 1
                1 2 1 1 
                1 3 2 1
                2 4 5 1 
                3 5 11 1
                1 6 50 1
                1 10000000 
                1 3000000 
                1 700000 
                1 100000 
                1 1000 
                100 1 
                1 1
                
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  thanks bro. so do you mean the iteration should be num of edges? i'm curious how you figure it out? i have tried the whole day but no clues found.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  It is O(n*n) because,

                  1) To reach node 1 to node t, You will buy coins O(n) times.

                  2) Among above O(n) cities, it takes O(n) edges to move to node where we buy the coins next.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  do you mean it should update dp n*n times? (the most outer iter: f(go,n+1) in your code) i think 2*M is enough because each edge can be shrink the time only once.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Your submission can pass with given time complexity, but you are using much memory so it increases the time.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks!

          After I change it into $$$dp[i][j]$$$ ,it got $$$AC$$$

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      3 ENOUGH FOR ME

»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

For problem F, without noticing $$$U,V<2^{64}$$$, I used long long instead of unsigned long long and got WA for 2 times.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I solve D recursively ?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone explain E & F.

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the quick English editorial !

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

my first contest at atcoder. the first three questions felt pretty easy.But got stuck on the D th problem if anyone can make a video tutorial on that.it would be a great help

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Not terribly important, but I'm just going to point out that there's a typo on English B where Takahashi's name is misspelled as Takashi once.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I would appreciate it if someone could provide all solution.QwQ

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to SOLVE A

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

If we do not consider time efficiency, is it possible to use the differential constraint system to solve the F problem? I used it but got wa

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me a hint or idea to solve problem D?

Thanks in advance

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wander why this submission on F failed in only one test

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For question E, I have a test data that let my code that Accepted in Atcoder now to output wrong answers.

Data is: 3 2 1 1 2 1 2 1 3 2 4 1000000000 1 1000000000 1 1000000000 1

my code that Accepted in Atcoder now : https://atcoder.jp/contests/abc164/submissions/12437105

If row 111~115 is uncommented, you can use this data

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does E allow SPFA to pass

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone need explanation ,code and example for problem D here

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I made video tutorial on first four problems . It may help you . Link

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

#Hi, Can anyone help me with what wrong with my code in which test case it does not work? #Problem D ****

s=input()
n=len(s)
count,index,value=0,1,0
Hashmap=dict()
while index*2019<=999999:
    value=str(index*2019)
    Hashmap[value]=1
    index+=1     

for i in range(n):
    if i+6<=n and Hashmap.get(s[i:i+6])!=None :
            count+=1
    if i+5<=n and Hashmap.get(s[i:i+5])!=None:        
            count+=1
    if i+4<=n and Hashmap.get(s[i:i+4])!=None:
            count+=1
print(count)
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell about the problem b why same number is added which is divided and subtracting minus 1.can any tell why is it needed from editorial i m referring .https://img.atcoder.jp/abc164/editorial.pdf

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I accidentally found a "hack" for F; this solution is wrong but passes: submission

Error details