atcoder_official's blog

By atcoder_official, history, 16 months ago, In English

We will hold freee Programming Contest 2023(AtCoder Beginner Contest 310).

We are looking forward to your participation!

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

| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking forward to participating!

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

give your best

»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve D ?

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

    I used backtracking.

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

      In many of the solutions like this https://atcoder.jp/contests/abc310/submissions/43606894

      They are calling dfs by using dfs(k-1,max(top,i)) which I am not able to understand why. Whats the use of using max here ?

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

        As I understood, you must control the number of non-empty teams. This number can stay the same or increase by one if i = top + 1 (when the new player is added to the new team).

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

    I thought of it as coloring a graph using exactly t colors such that no two adjacent nodes are of same color. This can be solved using bitmask dp and inclusion exclusion.

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

      Can you give any resource of your mentioned coloring graph problem solution??

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

In F in the first sample, why is the denominator 18? Shouldn't it be 1 * 7 * 2 * 9 = 126? The probability of the results of the N dice satisfying the condition is 11/18.

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

    There are $$$77$$$ possible combinations that are good (can't list them all, sorry). There are $$$1 \cdot 7 \cdot 2 \cdot 9 = 126$$$ possible combinations in total. This means that the probability is $$$\displaystyle\frac{77}{126}$$$.

    $$$\displaystyle\frac{77}{126} = \frac{7 \cdot 11}{7 \cdot 18} = \frac{11}{18}$$$.

    The probability is shown as an irreducible fraction, because that is used in the definition of probability mod prime.

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

      i am getting only 47 possible combinations.here is the code for that

      https://ideone.com/zwityB

      what did i do wrong ?

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

        From the statement:

        There is a way to choose some (possibly all) of the $$$N$$$ dice so that the sum of their results is $$$10$$$.

        We don't need to choose all dice. For example $$$[1, 7, 2, 9]$$$ is good since $$$1 + 9 = 10$$$.

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

          yeah and that is why i have started iterating from 0 indicating they are not being considered

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

            Ah, I see, but that's still wrong. Let's look at an easier example:

            2
            10 100
            

            There are a lot of good combinations similar to $$$[10, 11], [10, 12], \dots, [10, 50], \dots [10, 99], [10, 100]$$$, but your code will not count these separately as it only counts these in $$$[10, 0]$$$.

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

bitmask dp is best dp

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

What does "the doubling technique" mean in the editorial for problem G? I've only found the solution using functional graphs.

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

Can someone explain D?

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

    First, go through all $$$2^n$$$ possible subsets of players, calculate if the subset is good and store the results in a separate array (using bitmasks as indicies). This can be easily done in $$$O(2^n \cdot n^2)$$$.

    After that, let $$$dp[i][j]$$$ equal the number of ways to pick $$$i$$$ peaceful teams of the people in $$$j$$$ ($$$j$$$ is a bitmask). The transitions should be pretty simple. If we want to calculate $$$dp[i][j]$$$ for specific $$$i$$$ and $$$j$$$, we can iterate over a bitmask $$$k$$$ representing one of the teams. Since $$$k$$$ is a team of the people in $$$j$$$, $$$k$$$ must be a submask of $$$j$$$ (i.e. $$$j | k = j$$$). If the team represented by $$$k$$$ is good (can be checked from the array calculated in the first part), the rest of the people must form $$$i-1$$$ teams and be from the set $$$j \oplus k$$$. The number of ways to do this is $$$dp[i-1][j \oplus k]$$$ by definition.

    Now, the answer will be $$$dp[t][2^n - 1]$$$, but notice that we've overcounted the answer. The statement doesn't care about the order of the teams, but our method will calculate all orders of adding the same teams as different solutions. Thus, we need to divide the answer by $$$t!$$$.

    There are $$$2^n \cdot t$$$ dp states, and for each state we need to calculate up to $$$2^n$$$ transitions. Thus, the total time complexity of the dp is $$$O(4^n \cdot t)$$$ (or $$$O(3^n \cdot t)$$$ if you know how to directly iterate over submasks). This is slower than the first part, so the total complexity of the solution is $$$O(4^n \cdot t)$$$.

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

      that's exactly what I did , can you tell me please why we can go down with O(3^n * t), because I can see O(4^n * t)

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

        Can I see your code first?

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

          Yes sure: my submission

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

            What you're doing in your recursive dp call is you're iterating over all $$$2^n - 1$$$ possible non-empty bitmasks i and checking if the current bitmask is a submask of bitmask with a loop something like this:

            for (int i = 1; i < (1 << n); i++) {
                // check if i is a submask of bitmask
                ...
            }
            

            This can be replaced by

            for (int i = bitmask; i > 0; i = (i-1) & bitmask) {
                ...
            }
            

            This iterases over all submasks of bitmask in decreasing order, and it doesn't iterate over any i that are not submasks of bitmask.

            Proof:

            Now, we can show that the time complexity of the following code is $$$O(3^n)$$$:

            for (int bitmask = 0; bitmask < (1 << n); bitmask++) {
                for (int i = bitmask; i > 0; i = (i-1) & bitmask) {
                }
            }
            
            Proof:
            • »
              »
              »
              »
              »
              »
              »
              16 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Shorter calculations:

              $$$\sum_{k=0}^n 2^k \binom{n}{k} = \sum_{k=0}^n 2^k \cdot 1^{n-k} \cdot \binom{n}{k} = (2+1)^n = 3^n$$$

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

Can someone tell me the approach to solve E?

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

in editorial of problem D

 vector dp(1U << N, vector<unsigned>(T + 1));
    dp.front().front() = 1;
    for(unsigned i{}; i < 1U << N; ++i)
        // brute-force over all possible teams that the remaining player with the minimum integer belongs
        for(unsigned c{i + 1 | i}, j{c}; j < 1U << N; ++j |= c)
            if(possible_team[j ^ i])
                for(unsigned k{}; k < T; ++k)
                    dp[j][k + 1] += dp[i][k];

can someone explain this part ? why we always taking a player with the minimum integer ?

upd: seems the answer is just dp.back().back() there is no division by (t!), is it somewhat related to always taking minimum ?

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

    Although I didn't solve it before contest ended, I think I could give some explanation.

    Suppose that we have divided players into different teams, and now we are going to find a way to uniquely distinguish each of them, in order to avoid counting the same pattern more than once.

    For each team, we sort the number of players in an increasing order, and choose the minimum one as the "leader", and then sort all teams in an increasing order of leaders. For instance, n=3, and t=2, and we have (2) and (3,1) as two teams. Then, we sort them as (1,3),(2). We can prove that this uniquely determine exactly one way to form teams. Thus, we have the solution as follows.

    First, we choose t leaders in an increasing order, which has C(n, t) ways. Then, we divide the left n-t players into t teams, and must make sure that, within each team, they can't have smaller numbers than leader and they are peaceful, which has (n-t)^t. Total complexity is C(n,t)*(n-t)^t*n.

    You can check my codes if you like https://atcoder.jp/contests/abc310/submissions/43648524