[Tutorial] Product trick

Правка en4, от TheScrasse, 2022-01-03 01:28:59

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

abc214_g (rating: 2893) (suggested by __hermit__)
abc225_h (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 - Карты).

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!

Теги tutorial, combinatorics, dp, trick

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский TheScrasse 2023-06-25 14:59:37 21 Tiny change: '5])<br>\n[IOI' -> '5])<br>\n[problem:1842G]<br>\n[IOI'
en7 Английский TheScrasse 2022-09-05 08:19:42 129
en6 Английский TheScrasse 2022-09-04 19:47:33 255 Added two problems
en5 Английский TheScrasse 2022-01-03 02:00:00 2
en4 Английский TheScrasse 2022-01-03 01:28:59 230 Tiny change: 'r:Hermit])\n[abc225_' -> 'r:Hermit])<br>\n[abc225_'
en3 Английский TheScrasse 2022-01-02 22:32:29 2 Tiny change: '{a_i^2(a_i-1)}{2} - \' -> '{a_i^2(a_i+1)}{2} - \'
en2 Английский TheScrasse 2022-01-02 21:42:13 16
en1 Английский TheScrasse 2022-01-02 21:30:58 8962 Initial revision (published)