chokudai's blog

By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 132.

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

We are looking forward to your participation!

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Copy&Pasted the e-mail announcement and forget to remove the instruction for unsubscription? LOL

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

    It's strange I did not recieve email announcement yet. I thought generally everyone recieve it at same time.

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

Do they release editorials for these rounds? Is it in english?

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

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

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

AtCoder site is terribly slow these days during the contest, it takes usually 10-15 seconds to open standing or clarification page. Please do something about it.

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

After the contest ends please tell How to solve Problem D?

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

    place red balls then choose i gaps out of n-k+1 = (n-k+1 choose i). then place k blues in these i gaps = number of positive integral solutions of a1+..ai=k = (k-1 choose i-1) multiply both coefficients.

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

      were there any corner cases?

      spoiler

      I was getting runtime error for this assert.

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

        No need to handle corner cases because all values outside range will be set to 0 which will give the required answer as 0. Code.

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

          Got it ,Thanks. I didn't handle the case where k>n in n choose k.

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

        You can use c[2001][2001] with some Precomputation.

        c[i][j] = c[i-1][j] + c[i-1][j-1] 
        base case : c[0][i] = c[i][0] = 1
        

        Use this simple property to avoid such complex computation. (no need to use Inverse Modular properties .)

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

    Let us say the number of red balls is R = N — K and blue balls is B = K.

    Consider the case where it takes i moves. So the number of ways to split B balls into i non-empty groups is choose(B — 1, i — 1) by stars and bars method.

    Now between any 2 groups there must be at least one red ball since if there was no red ball, they would be one large group instead. So the groups must occupy spaces between the red balls. The number of spaces are R + 1 and groups are i. So again, by stars and bars method number of ways is choose(R + 1, i).

    Multiplying we get ans as choose(B — 1, i — 1) * choose(R + 1, i).

    You can precompute choose values for R + 1 and B — 1 in O(N) time and answer for every i in O(1) time. So complexity is O(N + K)

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

    Use just need to use PnC to solve the stuff look if we have K blue balls . then first place N-K red balls. then we have N-K+1 places to fill blue balls. Now just think if u use i of the places to fill K balls..

    Hope This helps u. :)

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

    Let`s count dp[i][j], what means number of ways present number i with j addends (order is important).

    Then dp[i][j] = dp[i-1][j]+dp[i-1][j-1].

    And the answer for i is dp[B][i]*(dp[R][i-1] + dp[R][i+1] + dp[R][i]*2), where B — blue balls, R — red balls.

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

How to solve D?

I was thinking somewhat on the lines that x1+x2+x3+....+xi = K, so we get C(K-1, i-1) (assuming all get atleast 1), but I couldnt figure out how to arrange them :(

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

    m = n-k ans[i] = C(m+1, i) * C(k-1, i-1)

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

    You have to chose i places out of a total of (n-k)+1. (n-k) red balls so (n-k+1) places and you have to take any i of them to place your blue balls.

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

    You can arrange i blue balls by C(k-1, i-1) and the red balls with 3 options : 2 * C(n-k-1, i-1), C(n-k-1, i) and C(n-k-1, i-2). So the answer would become : (number of ways of arranging blue balls) * (sum of 3 options of arranging red balls). My code

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

    You need to distribute K blue balls among i piles such that no pile is empty which is f1=C(k-1,i-1), now there are i-1 gaps between these piles and you need to fill at least 1 red ball in each of the i-1 gaps, after filling you will be left with z=n-k-(i-1) red balls and note that there are two more gaps one on extreme left and the other on extreme right of blue ball piles so you need to distribute z balls between i+1 piles such that each get >=0 balls which will be f2=C(n-k+1,i).So your answer will be f1*f2 . You can calculate nCr using factorial and inverse array in O(1) using O(n) preprocessing. Here is the link to my submission.

    I hope this helps :)

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

      could you explain on why f2=C(n-k+1,i) ?

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

        Its because you first put (i-1) red balls between the i groups of blue balls, so the remaining red balls are N-K-(i-1). Now you have to divide them into (i+1) groups (i-1 + the 2 corner ones). So the number of solutions for: x1 + x2 + x3 + ... + x(i+1) = N-K-i+1 is C(N-K+1, i)

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

          oh i see

          N-K-(i-1) split into (i+1) groups

          C ( N-K-(i-1) + (i+1) -1 , (i+1)-1 )

          thank you ~

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

      Awesome explanation, many thanks!

      I tried to solve it using pure DP but it was hard to do it in less than n^3. Can you link to some similar Combinatorics problems?

      Most of the problems I see on Codeforces are doable with some DP so I am quite weak with Combinatorics.

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

Thanks for the contest! In case there aren't plans to write an English editorial, I wrote up my solutions to all of the problems at this link.

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

How to solve F?

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

    The basic idea is DP with square-root decomposition. For each number of terms up to K, we store the number of valid sequences satisfying these two conditions (in two separate tables) for each X up to ceil(sqrt(N)):

    • The sequence ends in X.
    • The sequence ends in a term Y such that X*Y <= N but (X+1)*Y > N.

    We then just have to deal with transitions. I outline this step in my full solution, which I linked above.

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

    Hint: naive dp — f[i][j] = sum(k=1..n/j,f[i+1][k]). This can be optimized cause many f[i][j] have same values precisely those which have n/j = n/j'. Just maintain groups(they never change) and calculate above dp- Time = O(k*num_groups) = O(k*sqrt(n));

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

    Geothermal explains the solution well, but I think I have easier code for the problem:

    code

    Notably I only have one table, and from position j in the table, you can transition to any position in range $$$[0, m-j)$$$, so the transitions can be done with just two for-loops. To calculate the sizes of every part (where if $$$x$$$ and $$$y$$$ are in the same part if $$$\left\lfloor\frac{n}{x}\right\rfloor = \left\lfloor\frac{n}{y}\right\rfloor$$$), I just maintain the smallest s such that $$$\left\lfloor\frac{n}{s}\right\rfloor = v$$$, and then binary search the next $$$s^{'}$$$ s.t. $$$\left\lfloor\frac{n}{s^{'}}\right\rfloor < v$$$. Then there are $$$s^{'} - s$$$ values in the part.

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

      You don't need the binary search — s = n/(n/s'+1) — calculate in decreasing order.

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

        Nice, with that the code is just 40 rows:

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

    Maybe I have a bit simpler solution (well, rather, interpretation) than others, which can be implemented very intuitively.

    Let's call a sequence good when

    • each element is positive integer $$$\leq N$$$, and
    • product of any two adjacent elements is $$$\leq N$$$.

    For each positive integers $$$m$$$ and $$$i$$$, let

    • $$$a^{m}_{i}$$$ be the number of good sequence of length $$$m$$$ whose last element is $$$\leq i$$$, and
    • $$$b^{m}_{i}$$$ be the number of good sequence of length $$$m$$$ whose last element is $$$\leq N / i$$$.

    For $$$m=1$$$, $$$a^1_i = \mathrm{min}(i,N)$$$ and $$$b^1_i = n/i$$$. For $$$m \geq 2$$$, it holds that

    • $$$a^m_i = a^m_{i-1} + b^{m-1}_i$$$, and
    • $$$b^m_i = b^m_{i+1} + a^{m-1}_i \cdot (\frac ni - \frac n{i+1})$$$,

    Also, it holds that $$$a^m_i = b^m_{N/i}$$$. Therefore, for each $$$m$$$, you can calculate $$$a^m_1, a^m_2, \cdots, a^m_{N/x} = b^m_x, b^m_{x-1}, \cdots, b^m_1$$$. Of course it's optimal when $$$x \approx \sqrt N$$$. The answer is $$$b^K_1$$$.

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

How to solve Problem E & F ???

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

    The idea is that we construct the graph in 3 parts (let's call them first, second and third), such that if there is an edge between u and v, then in our graph, there is an edge between u.first -> v.second, u.second -> v.third and u.third -> v.first. Now, if you run BFS on this Graph starting from vertex S.first and if you keep the destination as T.first, then you will find a path whose length is always divisible by 3, and hence you will get the answer by dividing the path length by 3. And if you cannot reach T.first, then print -1.

    My AC submission: https://atcoder.jp/contests/abc132/submissions/6179681

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

      How u came up with this approach.During the contest. Have u seen such problems.I was triying to first run a dfs from start to end and checking if i reached in between all this at my end vertex if yes then i check the count of the vertices i crossed.but it didnt worked.Also i was checking if there is a loop containing vertex with length of loop%3!=0.but i got stuck in the cases and finally was unable to figure out the sol...Plz tell am thinking in right direction or i m completely wrong

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

      Nice approach!

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

      Thx. I understood. But how to solve Problem F??

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

Plz help with E.

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

    See the link I posted above. A copy of my write-up of E is below:

    Create a graph of 3*N vertices, where the first N vertices represent reaching a vertex before starting a ken-ken-pa, the second set of N vertices represent reaching a vertex after one of the three actions in a ken-ken-pa, and the third set of N vertices represent reaching a vertex after two actions in a ken-ken-pa. An edge from A to B in our original graph is then equivalent to three edges: one from A to B+N, one from A+N to B+2N, and one from A+2N to B.

    The advantage of this approach is that once we read in the data, the solution itself is very easy to implement, as we now simply want to find one-third the distance from S to T (where the distance between two nodes is the number of edges we must traverse to reach one from the other). We can compute this using a standard BFS algorithm, which can also tell us whether T can be reached from S at all.

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

      why do create a graph of 3*N vertices ??,this confused

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

        Think of it like every vertex is being split into three vertices, let's say vertex u is being converted into three copies of vertices u0,u1,u2 where u0 denotes the vertex copy of u if u is reachable with distance equal to 0 modulo 3 from some source vertex ,and similarly u1 denotes the vertex if you can reach u with distance modulo 3 as 1 from some source vertex , similarly for u2 , so that's why for every u->v edge it is equivalent to u0 -> v1 , u1 -> v2 , u2->v0 as if you move one step from u0 then the distance modulo 3 becomes 1 as initially it was(=0%3) , so from u0 you can go to v1 , similarly for u1 if we move one more step towards v we actually reach v2 since now distance modulo 3 is 2 , .. Now we need to find the shortest distance from S0 to T0 as when we start at S our distance is 0 and when we reach at T our distance modulo 3 must be 0 which implies that we have taken steps in multiples of 3 . Initially i too didn't understand proof.

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

      Is there any proof of this solution?

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

      Can you please suggest me a similar problems to Problem E?

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

Thanks to the Atcoder team for another fun contest!

I wrote an English editorial on Codeforces, if anyone would like to read one.

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

Hi, I submitted solutions for 3 problems and they appear in 'My Submissions',however they don't reflect in 'Standings'.What did I do wrong?

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

    Are you sure your submittions were submitted before the race ended?

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

Thank your guys for preparing a good contest.