When the value domain is narrow (narrowed by problem constraints) or the definition domain is excessively wide (such as the whole subset 2^2000), problem transformation to exchange the value domain and the definition domain is effective in some cases.
- [[Fennic tree]]
- Represent a set of values as an array where the subscripts are the values and 1 stands for 1.
- [[dynamic programming]]
- When the value range is narrower than the definition range, instead of finding the largest value in the definition range, find the largest subscript in the value range that satisfies the constraint
- [[DP E]]
-
gcd for a subset of a set of 2000 elements, the domain is 2^2000, but the value range is smaller with a set of 2000 divisors
-
Functions with a narrower value range than the definition range
This page is auto-translated from /nishio/値域と定義域の交換 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.