chokudai's blog

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

»
4 months ago, # |
Rev. 3   Vote: I like it -100 Vote: I do not like it

downvote if you have tiny pp.

  • »
    »
    4 months 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.

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

    jisne downvote mara uski maa ramdi

  • »
    »
    4 months 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

»
4 months 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".

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

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

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

    How to solve D?

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

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

    • »
      »
      »
      4 months 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 .

    • »
      »
      »
      4 months 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

  • »
    »
    4 months 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

  • »
    »
    4 months 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.

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

    D was not graphs, it was just dp.

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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)

      • »
        »
        »
        »
        4 months 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.

  • »
    »
    4 months 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.

»
4 months 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.

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

    .

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

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

    • »
      »
      »
      4 months 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?

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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?

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

            Because for inverse factorials you should do this.

            Inverses
»
4 months 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.

  • »
    »
    4 months 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?

»
4 months 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

  • »
    »
    4 months 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

  • »
    »
    4 months 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.

  • »
    »
    4 months 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++)

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

      Almost understood all except the "st" part, can you elaborate little more??

      upd: Got it !

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

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

Problem D was very nice!

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

My D solution passed example test cases and some of the hidden test cases. But still can't figure out why it gave WA. I used DP. Can anyone help me figure out what is error in my code. Here is my submission Submitted Code

»
4 months 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))$$$

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

    Yes, but how to calculate that for a huge N

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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$$$).

      • »
        »
        »
        »
        4 months 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!

»
4 months ago, # |
  Vote: I like it -20 Vote: I do not like it

ABC in 25 minutes then waiting for contest to end tried F with vey bad and illogical medthod if n>30 n=30 and then dp but it passes 11/35 only can anyone explain problem D ??

»
4 months 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 ?

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

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

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

      Yes. Is there a convincing proof of this thing ?

      • »
        »
        »
        »
        4 months 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)

        • »
          »
          »
          »
          »
          4 months 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 ?

          • »
            »
            »
            »
            »
            »
            4 months 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,

            • »
              »
              »
              »
              »
              »
              »
              4 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months 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 !

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

Is there a way to interpolate using the Atcoder library?

»
4 months 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
  • »
    »
    4 months 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

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

      thank you. learned a new thing today

    • »
      »
      »
      4 months 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)$$$).

»
4 months 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?

  • »
    »
    4 months 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 months 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 months 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 months 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.