chokudai's blog

By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 208.

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

We are looking forward to your participation!

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

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it -100 Vote: I do not like it

downvote if you have tiny pp.

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

    I really don't see which part of D's statement is ambiguous. Also, you should ask for the clarification on the atcoder site if you're unsure about something, not on CF.

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

    Guys like you are like a mad rabid dog who needs to be put to sleep legally

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

I am pretty sure the solution of F uses some pretty advanced stuffs, because for $$$M=1$$$, it reduces to 622F - The Sum of the k-th Powers

Lagrange polynomials in a "Beginner Contest".

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

Floyd-Warshall algo without modifications in D, problemsetters are you serious?

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

    How to solve D?

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

    Why not? It's ABC meant to be educational.

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

      Maybe just copy pasting the algorithm is not a good idea . There should have been something additional , anyways maybe I am not qualified to answer as I was even unable to solve this .

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

      educate to google and copypaste? when one has to modify an algorithm, he/she has to fully understand it, but probably on the contest, most people, who didn't know and managed to find this algo just copypasted, even if this algo is simple and has nothing that hard to understand. But in general, there would be more complex algos which can be copypasted w/o understanding

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

    I think it is very adequate for a Beginner Contest. You need to understand the algorithm and understand where to insert the new code inside a known algorithm. My brother got to know Floyd-Warshall for the first time and even I learned how FW works more in detail. I am really positive that I won't mistakenly put $$$i$$$,$$$j$$$,$$$k$$$ in the wrong order from now on, knowing which invariant $$$k$$$ creates. :D

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

    wait, was'nt the extra summation over k a modification? if I didn't understand Floyd-warshall, I don't think I could have solved it.

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

    D was not graphs, it was just dp.

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

    So what do you expect in a "beginner's" contest? Problems like F?

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

      problems, where I have to think(also, don't forget, it's D for 400 points)

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

        Well, if you didnt know the working of FW, you would have to spend some time with the algorithm.

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

    Actually that algorithm is just a greedy observation.

    When I solved that problem I didn't even knew that such a algorithm exists.

    Coincidentally I wrote the exact algorithm without even knowing about it.

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

In F, $$$O(MKlog(mod))$$$ was giving TLE. Were you expecting $$$O(M*K + (M+K)log(mod))?$$$ The TL was too strict.

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

    .

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

    You would only need one inverse if you compute factorials properly.

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

      In lagrange Interpolation, you need to take modular inverse $$$(10^9 + 7)$$$. So log(mod) because of that. $$$O(M*K)$$$ because I am doing interpolation that many times.

      Although I know, that we can do it in single interpolation by some-precomputation but $$$K$$$ was too high and problem setters should have allowed $$$O(MKlog(mod))$$$ AC. What's your code complexity?

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

        Mine is O(MK + M + K)

        Because you only need one inverse. But TL is still a little bit strict.

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

          How? If I am not wrong, this problem is just and extension of this whose complexity is $$$O(klog(mod))$$$. Are you doing something different?

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

            Because for inverse factorials you should do this.

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

I solved F by using the fact that f(x, M) is a polynomial with degree (K + M). I used linear complexity (O(degree)) interpolation. Is this intended? K = 2.5e6 is kinda large, my code took 1.7s to run.

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

    Why is it polynomial of degree (K+M)? Since f(n, m) defined as sum of some number of zeros and (n^k) for n from 1 to N, then: f(N, M) = b1 * 1^k + b2 * 2^k + b3 * 3^k + ... bn * N^k — (with b_i — some unknown integers) and that makes if polynomial (of variable n) of degree (K+1), because we can turn this expresion into f(N, M) = b1*(N-(N-1))^k + b2*(N-(N-2))^k+ ... + bn*N^k = a0 + a1*n^1+a2*n^2+..+ak*n^k. No?

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

Can someone please explain E in more simple words?

editorial is not quite clear to me

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

    I used 5 states DP to solve it , I am presuming that you know basic Digit DP.
    map<lli,lli> dp [leading_zero][tight][product_is_zero][no_of_digit]; except no. Of digit all other states will be 0 or 1 . I am using Map as I don't know exactly how many values of K will be there ( Hoping that someone will tell me the upperbound on no. of K for each state ). Tight represents that whether the current no. through which I came here is till now equal to N or not.Then just some digit DP stuffs.
    code

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

    I did this DP from least significant digit to most significant digit. Submission link. As far as I can tell, there's no need to have the optimization they mention in the editorial where products greater than K are indistinguishable, so I'll ignore that.

    The DP state I use only needs to store two values — the maximum possible value that the number can take on given the digits we already have, and the product attained so far from the digits we have already used. The starting state is therefore $$$(N, 1)$$$.

    The base case for this DP is if the maximum possible value that the number can take on is zero — in this case, we can't add any more digits, so we simply check if our attained product is less than or equal to $$$K$$$.

    If we are not in the base case, then we can append digits to the left. The transitions are therefore adding the digits from zero to nine (or $$$N$$$, if $$$N < 9$$$) to the left of the number we have built so far. Adding the nonzero digits is straightforward, the product just scales by the digit we added, and the maximum value goes from $$$v$$$ to $$$\left \lfloor \frac{v-d}{10} \right \rfloor$$$ if we just appended a digit $$$d$$$. The interesting transition is when we add a zero.

    There are two cases — either all the digits will be zero from here to the most significant digit, or there will be a digit to the left that is nonzero. In the former case, the number we have built so far is evaluated to see if it is valid. In the latter case, we mark the current product as being equal to "zero", except that it is not valid if we run into the base case. This is necessary to avoid overcounting. If we multiply this "zero" by any non-zero digit, then the product becomes exactly zero. In my code, the sentinel ZERO is used as a placeholder for this fake zero.

    Note that in the above, we cleanly handle numbers where the length is less than or equal to the length of $$$N$$$. This avoids a typical issue in digit DP where we have to keep track of when the number is "initialized", if the DP is done from most significant digit to least significant digit.

    This DP also counts zero, so you'll need to decrease the answer by one at the end.

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

    4D dp is sufficient for solving the problem (use map for storing dp) The dp will look something like this :- ~~~~~

    map<pair<pair<int,int>,pair<bool,bool> >,int>dp; // {{pos,prod},{tight,st}}

    pos : current pos in the number 
    prod : current product of digits so far 
    tight : tells whether current no is smaller than N or not 
    st : tells does the number has leading zeros or not.
    

    ~~~~~

    So if u know basics of digit dp , this problem can be solved :) For reference : My Accepted Code(c++)

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

    I think the easiest way is to iterate over the most significant digit that differs, and then use the naive $$$dp[i][j] :=$$$ number of $$$i$$$-digit numbers with product $$$\leq j$$$. Since every $$$j$$$ will be of the form $$$\left \lfloor{K/x}\right \rfloor$$$ for some $$$x$$$, $$$j$$$ can take on at most $$$2\sqrt{K}$$$ distinct values. I think the editorial proves a tighter bound, but $$$O(18\cdot 2 \cdot \sqrt{K})$$$ is already good enough. (There is a small edge case with trailing 0s, but you can use the same DP to handle that.)

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

Problem D was very nice!

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

    Unluckily,somebody have seen this thick.....

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

A simple solution for F with interpolation.

We know that,for a function $$$f$$$ on $$$\mathbf{N}$$$ with $$$\deg(f)=k(k>0)$$$,denote $$$g$$$ as the prefix sum function of $$$f,$$$ $$$\deg(g)=k+1$$$ holds.

Consider $$$(i,j)$$$ of the chart as $$$f_j(i)$$$,then $$$\deg(f_j)=\deg(f_{j-1})+1=k+j$$$

Calculate $$$f_j(1...m+k)$$$ and use interpolation to solve it.$$$O(m\log k+m(m+k))$$$or $$$O(m\log k+m+k)$$$ in total.

Bonus:How about $$$10^5$$$ queries($$$m,k$$$ are the same)? Just use fast evalution on polynoimal,$$$O(m\log k+Q\log^2(m+k))$$$

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

Isn't this the answer for $$$f(n, m)$$$ when $$$n > 0$$$ in problem F?

$$$\sum\limits_{i = 1}^n ( \binom{n + m - i - 1}{m - 1} \cdot i^k )$$$
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, but how to calculate that for a huge N

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

    Yeah, I caught this series pretty quick, but I tried for like 90 mins on how to get this sum and failed. Bad decision skipping E and going for F.

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

      Bad decision skipping E and going for F.

      Bad decision starting with F. lol

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

    UPD: No, my calculation is just plain wrong.

    Oh, I got

    $$$\sum\limits_{i = 1}^n ( \binom{(m - 1) \cdot ( i- 1)}{m - 1} \cdot i^K )$$$

    You count the paths from $$$f(n,m)$$$ to $$$f(i,0)$$$ and multiply by $$$i^K$$$ for all $$$i$$$. Is that the same?

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

      No, just plug in random small values of n and m, your formula will give incorrect answers (i.g. $$$f(2, 5) = 5 + 2^k$$$, and your formula gives $$$\binom{(5 - 1) \cdot (1 - 1)}{5 - 1} \cdot 1^k + \binom{(5 - 1) \cdot (2 - 1)}{5 - 1} \cdot 2^k = \binom{0}{4} \cdot 1^k + \binom{4}{4} \cdot 2^k = 2^k$$$).

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

        Argh, you are right, got my error. First of all I got $$$\pm 1$$$-errors galore. Second of all, the formula on this site which I used as my source is wrong. It says $$$Number Of Paths=\binom{(W-1)(H-1)}{(W-1)}$$$ but this is just plain wrong, compare to the wiki article. If I replace the multiplication with addition in my formula I get your formula.

        Thanks very much, I won't make this mistake again!

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

Can someone please give a rigorous proof of upper_bound for E's naive top down solution's complexity ?

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

    Do you mean why the number of distinct products fits in constraints?

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

      Yes. Is there a convincing proof of this thing ?

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

        Ah, i dont have a "proof", but i have some combinatorics.

        It's obvious that the product is independent of the order of the digits, to we don't care about permutations. We only consider different combinations for distinct products.
        If i consider for n=1e18, i have 18 digits, to choose from digits [1,9] (let's ignore 0). This can be given by stars and bars as, (n+r-1)C(r-1). that is choosing a non zero value for (x1+x2+x3....x9) = 18 where x1 -> number of digits '1', and so on. This number comes out to be around 1e6 when i computed it. you can similarly compute it for 1,2,3,..18 and i'm sure it won't exceed 1e7. rest of the states are pretty small so we can squeeze them in the given constraints.
        (P.S. I'm really bad with numbers so i might've made some mistakes but you get the idea)

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

          Woah, I was looking for a upper_bound too. I have 2 doubts now

          This number comes out to be around 1e6 when i computed it. you can similarly compute it for 1,2,3,..18 and i'm sure it won't exceed 1e7.

          Why would you also computer for upto 18, if I understood it properly x(digit) stands for no of that particular digits used and 9 is the biggest digit ?

          rest of the states are pretty small so we can squeeze them in the given constraints.

          If you see my submission, its running in about 290 ms. Which is pretty low for 20 * 2 * 2 * 1e6 * log ? Is there a reason here ?

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

            Answer to first doubt.
            (it's actually 17, not 18, my bad) x1+x2+....x9 = 17 so if i have x1=15 and x2=2, and rest zero, I get the number 11111111111111122. (or any permutation of it). The number can be of 17 digits, since n<=1e18 and i have to choose digits [1,9] to fill these 17 vacancies.

            Second doubt:
            I think the answer lies with the fact that not all dp states are calculated. 20*2*1e16*log would be the very worst case which doesn't happen in most problems. Well, honestly i have no good answer to why the size of the map is the order of 1e5 when you print it in the the third sample, but i think what i mentioned has something to do with it,

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

              Yeah, seems that the actual values getting hit as states in the problems are still very few than the above upper bound. Anyways, thanks, that helped.

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

                Also something i missed, the number of distinct products is even lesser than what i mentioned bcoz i only counted the combinations. but few combinations can give same products. prod(14) = prod(22). so it's way lesser than what i mentioned.

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

                  Ok, now its pretty satisfactory that why the distinct values are pretty low. Thanks a lot !

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

Is there a way to interpolate using the Atcoder library?

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

I tried this solution for problem B.

can someone please tell me why this code is not giving any output for large inputs(i.e input greater than 30000? for small inputs, it is giving correct output

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

    Declare your 'dp' array globally. Size of the array is too large (10^8) to be declared locally

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

      thank you. learned a new thing today

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

      For later, if you're doing a coin change dp, do something like this:

      You only need 1D dp

      Also if there were more than one test case, it'd be much better to pre-calculate it outside the test case loop (because otherwise you'd have a complexity of $$$O(T * 10^8)$$$).

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

Can someone prove how the number of states is limited in this(the code is clean) solution?

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

    Obviously, the numbers of possible x, z, and w are $$$d :=log N$$$ (the number of digits in $$$N$$$), $$$2$$$, and $$$2$$$, respectively. The non-trivial part is y. How many possible "products of digits" are there? Actually, every product of digits has only factors 2, 3, 5, and 7. Plus, the upper bound of the product is $$$9^d$$$, or more loosely $$$10^d \simeq N$$$. Now every product except for $$$0$$$ can be expressed in a form of $$$2^a 3^b 5^c 7^d$$$ for some non-negative integers $$$(a, b, c, d)$$$, and the product is $$$\leq N$$$. Applying logarithmic function we obtain $$$a \log 2 + b \log 3 + c \log 5 + d\log7 \leq \log N$$$. How many tuples of integers are there that satisfies this inequality? It is equal to the number of grid points in a certain "pyramid" on a 4-dimensional space (which is technically called a simplex). Since the number of grid points is approximately equal to the volume, we can estimate the number as $$$\dfrac{\log N}{\log 2} \cdot \dfrac{\log N}{\log 3} \cdot \dfrac{\log N}{\log 5} \cdot \dfrac{\log N}{\log 7} \cdot \dfrac{1}{4!} \simeq 51555$$$.

    Alternatively, with the observation of prime factors being $$$2, 3, 5, 7$$$, one can just write a simple code to verify the number is small enough:

    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    
    int main() {
      ll cnt = 0;
      ll n = 1'000'000'000'000'000'000LL;
      for(ll a = 1; a <= n; a *= 2) {
        ll na = n / a;
        for(ll b = 1; b <= na; b *= 3){
          ll nb = na / b;
          for(ll c = 1; c <= nb; c *= 5){
            ll nc = nb / c;
            for(ll d = 1; d <= nc; d *= 7){
              cnt++;
            }
          }
        }
      }
      cout << cnt << endl;
    }
    
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, one doubt, why divide by 4! for estimation?

      I know that we should divide by something because we have multiplied the maximum values of a, b, c, d by why 4!, how did you estimated that ?

      Thanks!

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

        Consider the one-dimensional object

        $$$ 0 \leq x;\quad x \leq 1 $$$

        (it is actually a segment). Its "volume" (i.e. its length) is obviously $$$1$$$.

        Then consider the two-dimensional object

        $$$ 0 \leq x, y;\quad x + y \leq 1$$$

        (it represents a triangle). Its "volume" (i.e. its area) is 1/2.

        Now consider the three-dimensional object

        $$$ 0 \leq x, y, z; \quad x + y + z \leq 1$$$

        (it looks like a pyramid). Its "volume" (yes, literally volume!) is 1/6 = 1/(3!).

        Analogously, the four-dimensional object

        $$$ 0 \leq x, y, z, w; \quad x + y + z + w \leq 1 $$$

        (which I referred to as a "pyramid" in the comment above, or formally a "simplex") has the volume 1/(4!).

        One can prove that the simplex's volume is actually $\dfrac{1}{4!}$$$ by $$$$$$ \displaystyle V = \int_0^1 dx \int_0^x dy \int_0^y dz \int_0^z dw = \int_0^1 dx \int_0^x dy \int_0^y dz\; z = \int_0^1 dx \int_0^x dy\; \frac{1}{2}y^2 = \int_0^1 dx\; \frac{1}{2} \cdot \frac{1}{3} x^3 = \frac{1}{2} \cdot \frac{1}{3} \cdot \frac{1}{4} = \frac{1}{4!}. $$$

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

          Thanks a lot for taking time and writing this, finally got it, it is absolute beautiful that how we can arrive at non trivial results from absolute basic stuff.

          Thanks again.