Representing discrete functions with the most frequent value and differences from it

Правка en1, от bati06, 2018-04-26 16:48:39

I just solved the problem Facebook Hacker Cup 2015 — Round 1 — D. Corporate Gifting
My solution used "dp on tree" technique. The naive version would have used entire arrays in nodes that represents a discrete functions with its values. Because for every function all the function values are the same except one value, I can represent it with the common value, index of the difference, and the difference itself. Using this simpler representation the calculation of the sum of the functions will have lower complexity.
I wonder if this technique (of representing discrete functions this way) has some other useful applications. Is there any reading about this topic?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский bati06 2018-04-26 16:48:39 861 Initial revision (published)