All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Uchiha Brothers and Two Products

Bitmask, Dynamic Programming, Hard


This is an incident from a distant parallel universe where Itachi and Sasuke, the two brothers, are loving brothers. The brothers had gone for a very difficult training. Now they are really tired after the long training and crave for some food. Luckily they found a shop on their way.

enter image description here

The food items in the shop has weird properties to make the customer learn the difference between Logical Product($$Bitwise \space AND$$) and Arithmetic Product ($$\times$$) . Itachi being the elder brother already knows the difference and so he sends Sasuke to buy some food items from the shop and learn something new.

When Sasuke enters the shop, he notices that there is a set $$A$$ comprised of $$N$$ different food items to buy from. Each of the food item contains some of $$M$$ different nutrients. Therefore each of the food item has two attributes associated: Price and Nutrition Value. The Nutrition Value is a binary string of length $$M$$ denoting which of the $$M$$ nutrients are present in the particular food item.

Sasuke is instructed to buy a subset $$S = {i_1,i_2,i_3...}$$ of the $$A$$. The shopkeeper tells Sasuke the following rules of shopping:

  • The cost of buying the subset is the arithmetic product of price of all the food items in the subset. $$Cost(S) = Price_{i_1} \times Price_{i_2} \times Price_{i_3}..$$
  • On consuming the food items in the set $$S$$, one gets the benefits of only those nutrients that are present in all the food items in $$S$$. Define the nourishment of the set as $$Nt(S)$$ = number of nutrients one can get the benefit of if he consumes all the food items in set $$S$$.

Now to make his brother consider all the possibilities, Itachi asks him to calculate a function $$F(K) = \displaystyle\sum_{Nt(S)=K}^{S\subseteq A} Cost(S)$$.

The first line contains two integers $$N$$ and $$M$$.
The following $$N$$ lines describes all the food items of set $$X$$.
The first integer of each $$i^{th}$$ denotes $$Price_i$$.
The second string denotes its Nutrition Value. It is a $$M$$ length binary string.

Output $$M+1$$ space separated integers denoting the values $$F(0)\space F(1)\space.. F(M)$$.
Since the values can be quite large, print them $$mod\space 10^9+7$$.

$$ 1 ≤ N ≤ 10^5$$
$$ 1 ≤ M ≤ 20$$
$$ 1 ≤ Price_i ≤ 10^6$$

3 3
2 101
3 111
5 010
40 20 8 3

The 7 possible subsets are

  • 2: Cost = 2, Nt = 2
  • 3: Cost = 3, Nt = 3
  • 5: Cost = 5, Nt = 1
  • 2,3: Cost = 6, Nt = 2
  • 3,5: Cost = 15, Nt = 1
  • 2,5: Cost = 10, Nt = 0
  • 2,3,5: Cost = 30, Nt = 0

F(0) = 10 + 30 = 40
F(1) = 5 + 15 = 20
F(2) = 2 + 6 = 8
F(3) = 3

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

June Circuits

View All Notifications