TheScrasse's blog

By TheScrasse, history, 3 years ago, In English

Hello everyone,
in this tutorial we will see a trick that can be useful in combinatorics and/or DP tasks. In particular, you can use it when the statement says something similar to "the score of an array is the product of its elements, find the sum of the scores over all the possible arrays".

Prerequisites: basic combinatorics and DP

The trick

The trick is very simple.

"The score of an array $$$a$$$ is $$$\prod_{i=1}^n a_i$$$" can be rephrased as "if there are $$$n$$$ boxes, and the $$$i$$$-th box contains $$$a_i$$$ distinguishable balls, the score of $$$a$$$ is equal to the number of ways to color a ball for each box".

This is quite obvious, but it can be extremely powerful. Let's see some problems that are trivialized by this trick.

Dwango Programming Contest 6th, problem C (rating: 2618)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Implementation (C++)

abc231_g (rating: 2606)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Bonus

Implementation (C++)

arc124_e (rating: 3031)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

Other problems

arc147_d - Sets Scores (rating: 2145)
abc214_g - Three Permutations (rating: 2893) (suggested by __hermit__)
agc013_e - Placing Squares (rating: 3455) (zscoder)
1842G - Tenzing and Random Operations
IOI 2022/4 - Digital Circuit
abc225_h - Social Distance 2 (rating: 3061) (__hermit__)

Conclusions

We've seen that "product trick" is very useful to find a DP that solves the problem. There exist similar counting tricks: for example, "The score of an array $$$a$$$ is $$$\sum_{i=1}^n a_i^2$$$" can be rephrased as "if there are $$$n$$$ boxes, and the $$$i$$$-th box contains $$$a_i$$$ distinguishable balls, the score of $$$a$$$ is equal to the number of ordered pairs of balls belonging to the same box" (you can try to use it in 1278F - Cards).

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems where you can use this trick.

I hope you enjoyed the blog!

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

»
3 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for your tutorial.

By the way, in 1278F - Карты, I have seen a solution which can solve it in $$$\mathcal O(k)$$$

You can see This one, however, it is not in English.

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

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

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

https://atcoder.jp/contests/agc013/tasks/agc013_e

This problem also uses product trick iirc

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

This ARC problem is an application of this trick as well.

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

    Would you mind explaining how we can apply this into that problem? I have read the editorial but still couldn't see how to use this trick.

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

      In how many ways can you choose sets and highlight exactly one copy of $$$1, \dots, m$$$?

      First, distribute highlighted elements ($$$n^m$$$ ways).

      Then, for $$$2 \leq i \leq n$$$, choose the element that either appears or disappears ($$$m^{n-1}$$$ ways), and $$$s_1$$$ is uniquely determined.

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

Another one: link