chokudai's blog

By chokudai, history, 2 months ago, In English,

We will hold AtCoder Beginner Contest 159.

We are looking forward to your participation!

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

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

How to solve E?

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

    brute force over all possible lines for the rows. Then solve greedily for columns.

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

      What is the greedy for columns?

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

        For every "block" (rows between two horizontal cuts), maintain count of 1's for each column.

        So if you had something like:

        1 1 1 1
        1 0 1 0
        0 0 1 0
        0 1 1 1
        

        Let's say currently you're making cuts under rows 1 and 3 (1-based), so it'd be something like:

        1 1 1 1    first block
        --------------
        1 0 1 0
        0 0 1 0    second block
        --------------
        0 1 1 1    third block
        

        Now maintain count of 1's for each block at each column:

        1 1 1 1
        --------------
        1 0 2 0
        --------------
        0 1 1 1
        

        You know that if in any block, any count is bigger than k, than this horizontal cut setup is impossible, so you can just try the next mask.

        But in this case, let's say $$$k=2$$$. Now iterate through each column and each block and maintain one horizontal sum for each block, if at any index $$$i$$$ $$$\text{horizontal sum of some block} > k$$$, than you have to make a cut, and sum in each block becomes the i-th element in that block.

        So in the first block and second block, sum of the first three elements will exceed k, so you will make a cut there and sum will reset ($$$sum[1] = 1, sum[2] = 2, sum[3] = 1)$$$.

        1 1 | 1 1
        ----|----------
        1 0 | 2 0
        ----|----------
        0 1 | 1 1
        

        Welp, hope that explanation wasn't terrible haha.

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

          Thanks a lot, you explained far better than the editorial.

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

        Go through the array column by column. If the group size exceeds k for any of the groups in a column, we draw a line before the column and update the size of each group.

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

        Another way to understand greedy is to solve the 1-D problem; A = [1 1 0 0 1 ... etc]. In this case you will obviously keep going as far as possible until you need to make a cut. "As far as possible" means until your current sum exceeds K. Then extending this idea to the columns is easy.

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

    For splits across rows, try out all 2^r (actually 2^(r-1)) splits, for e.g using bit masks. Then greedily perform splits across the columns.

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

    Why should I go over 0 to 2^(h-1). Can anyone explain this in detail please :(

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

      Coz you are checking all possible combination. Suppose you have 3 rows, then row-wise you have 2 possible lines to cut the bar ( one line between 1st and 2nd row, and another between 2nd and 3rd row ), generally speaking in a N row bar you have (N-1) lines to possibly cut the bar. Now you don't know which lines you should cut through to have MINIMUM value of cuts and meet the condition, so you check all possibilities. In our example, [ 0 , 2^(3-1) — 1 ] == [ 0, 3 ]. If you observe the binary representation of the numbers,

      decimal --> binary --> interpretation

      0 --> 00 --> No cut is needed row-wise

      1 --> 01 --> Cut only through the 2nd line

      2 --> 10 --> Cut only through the 1st line

      3 --> 11 --> Cut through all the lines

      If you observe carefully the binary representation of numbers from [ 0, 2^(n) — 1] actually contains all possible combination for n items as described above. It is a simple trick we use in cp.

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

        Hey makes sense to me thank you for the reply :) care to explain what to do in each and every combination.

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

    If you want to see solution, You can see my submission, if you still have any doubt. i have used naming convention related to my approch such that someone can understand it !!

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

How to solve F?

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

    Let $$$\mathrm{dp}[i][j]$$$ be the sum of left endpoints of all sequences that end at $$$i$$$ and have weight $$$j$$$. The answer is $$$\sum_{i = 1}^n (n - i + 1) \mathrm{dp}[i][S]$$$.

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

      I understand that we basically add for all i,j of subsequences the pairs of indexes including i,j. That is all where left is less or eq i, and right bg j.

      But I do not get how we find all i,j of subseqs with sum==s? And even not the sum of the i?

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

        I don't understand a word of what you just said, but I'll try to elaborate a bit. If we have a subsequence with sum $$$S$$$ that starts at $$$l$$$ and ends at $$$r$$$, its contribution to the answer is $$$l (n - r + 1)$$$. That's because it is contained in $$$f(L, R)$$$ exactly if $$$L \le l$$$ and $$$r \le R$$$.

        We can think of it like this. There are many different subsequences with left endpoint $$$l$$$ and right endpoint $$$r$$$, suppose the $$$i$$$-th of them has left endpoint $$$l_i$$$ and right endpoint $$$r_i$$$. Then the answer to the problem looks like

        $$$l_1 (n - r_1 + 1) + l_2 (n - r_2 + 1) + l_3 (n - r_3 + 1) + \cdots.$$$

        (Obviously, this sum is too large to calculate directly, it is just to help with thinking.)

        Let's look at one particular $r$ and all the summands of the form $$$l_i (n - r + 1)$$$. That part of the sum above looks like

        $$$l_1 (n - r + 1) + l_2 (n - r + 1) + l_3 (n - r + 1) + \cdots = (l_1 + l_2 + l_3 + \cdots) (n - r + 1).$$$

        So, we are interested in the sum of left endpoints of all subsequences with weight $S$ that end at $$$r$$$.

        This can be calculated through dynamic programming. As I stated above, define $$$\mathrm{dp}[i][j]$$$ as the sum of left endpoints of all subsequences with weight $$$j$$$ that end at $$$i$$$. Then we can calculate it for all $$$i$$$ like:

        $$$ \begin{align*} \mathrm{dp}[i][A_i] &= i \\ \mathrm{dp}[i][j] &= \sum_{k < i} \mathrm{dp}[k][j - A_i] \text{ for all } j > A_i. \end{align*} $$$
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          Isn't this O(N*N*S) ?

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

            No, it is $$$\mathcal{O}(NS)$$$. We can calculate the last formula using standard prefix sums.

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

          Will there be illegal transitions?As dp[k][j-A[i]](k<i,j>A[i])->dp[i][j],but A[k]>A[i]. According to the problem statement, this is a illegal transition.

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

            Made a mistake reading the statement.233

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

    Hint :

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

Just one optimization, but i believe E can also be solved considering (2^(H-1)) masks.

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

    can you please explain your logic?

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

      For reducing the mask value, you could do a recursion for each row based on the assumption if ith row remains together with (i-1)th row or not after all the cuts are made.So we only do this differently (2^(H-1)) times, because 1st row doesn't have any preceding row, so it is assigned any relation with a previous row. Or simply just select (H-1) bits for masking where ith bit denotes if (i+1)th row is together with ith row or not in the final cut. Edit : 0 based indexing used here

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

For problem E, does some fail in test6 and pass at last? I've been struggling for quite a while, my code status.Thanks in advance.

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

Supplementary editorial for questions 2, 4, 5, 6 AtCoder ABC 159

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

Hey guys, does any of you got to read the editorial for problem F and can help me understand the transitions for the DP? It seems quite interesting.

I don't understand why at this point when we calculate dp[i+1][j+a[i]][2] we have to include dp[i][j][0], why should we add R without actually adding the L ?

Thank you in advance for help.

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

    Can you tell the meaning of Adding Only L , not adding L and R , adding both L and R ?? TheRedLegend

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

      As far as I understand it, we can start a new interval at each i, where 1 <= i <= n , this means that we set L (t = 1) to mark the beginning, then we can stop and interval meaning that we set R (t = 2) (but when setting R we need to have set L before, I understand this as transition between t = 1 to t = 2). We can set R at any position from [i..n]. And being between L and R we can add elements to the partial sum.

      When you think about this for a while you can easily notice that we will have L at any position and then R after L so L <= R, this meaning that we will iterate through all the possible L and R.

      I think this is the logic but I am not 100% sure. Still I don't understand why when computing dp[i+1][j+a[i]][2] we have to include dp[i][j][0].

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

    As far as I see, dp[i][j] is the answer for the first $$$i$$$th number if the required sum is $$$j$$$.

    When we are processing the new number $$$x$$$, obviously the previous sequence could be reused. Now consider how the new number could contribute to answer: First, itself could be a sequence so dp[i][x]=i. Then it could also form a sequence with previous sequences so dp[i][j]+=dp[i-1][j-x] for all $$$j\ge x$$$

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

where can I find solutions in English?

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

what is the logic for D?