Блог пользователя chokudai

Автор chokudai, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      were there any corner cases?

      spoiler

      I was getting runtime error for this assert.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится +72 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve F?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        Nice, with that the code is just 40 rows:

        code
  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Problem E & F ???

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Nice approach!

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Plz help with E.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        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 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Is there any proof of this solution?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Thanks to the Atcoder team for another fun contest!

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Thank your guys for preparing a good contest.