14,326,871 members
Rate this:
See more:
Thor is playing a game where there are N levels and M types of available weapons. The levels are numbered from 0 to N-1 and the weapons are numbered from 0 to M-1 . He can clear these levels in any order. In each level, some subset of these M weapons is required to clear this level. If in a particular level, he needs to buy x new weapons, he will pay x^2 coins for it. Also note that he can carry all the weapons he has currently to the next level . Initially, he have no weapons. Can you find out the minimum coins required such that he can clear all the levels?

Input Format The first line of input contains 2 space separated integers: N = the number of levels in the game M = the number of types of weapons

N lines follows. The ith of these lines contains a binary string of length M. If the jth character of this string is 1, it means we need a weapon of type j to clear the ith level.

Constraints 1 <= N <=20 1<= M <= 20

Output Format Print a single integer which is the answer to the problem.

Sample TestCase 1

Input
1 4
0101

Output 4

Explanation There is only one level in this game. We need 2 types of weapons - 1 and 3. Since, initially, Thor has no weapons he will have to buy these, which will cost him 2^2 = 4 coins.

Sample TestCase 2
Input
3 3
111
001
010

Output 3

Explanation There are 3 levels in this game. The 0th level (111) requires all 3 types of weapons. The 1st level (001) requires only weapon of type 2. The 2nd level requires only weapon of type 1. If we clear the levels in the given order(0-1-2), total cost = 3^2 + 0^2 + 0^2 = 9 coins. If we clear the levels in the order 1-2-0, it will cost = 1^2 + 1^2 + 1^2 = 3 coins which is the optimal way.

What I have tried:

I know this can be done using distance algorithms any help would be appreciated
Posted
Updated 29-Apr-18 9:20am
v2
PIEBALDconsult 29-Apr-18 10:21am

Good luck with that.
I'd use brute force.
Patrice T 29-Apr-18 11:02am

And you can tell us which site is doing that 'competitive challenge' ?
RaviManna 29-Apr-18 14:52pm

https://stackoverflow.com/questions/49772462/competitive-coding-clearing-all-levels-with-minimum-cost-not-passing-all-tes

Rate this:

## Solution 1

This is - as you say - "Competitive programming". Which means that any help we give you disavantages your fellow competitors, as well as (at least morally, if not necessarily legally) cheating.

Research by all means, ask if you are stuck at a specific point. But to just copy'n'paste the question and say "help me" is the same as trying to get us to do your homework, and we don't do that.
RaviManna 29-Apr-18 13:08pm

The competition is over, I was curious to know the solution. Thanks for your help anyways!
Rate this:

## Solution 2

Quote:
I know this can be done using distance algorithms any help would be appreciated

I must be missing big, because I do not even see what is the difficulty of this problem. Even with 200 weapons and levels.
The solution is brut force
```Make an array of weapons you have
Make a pool of the levels
As long as some levels remain
Check cost of all levels and remember cheapest
remove the level from pool
display total cost```

Looks like my brut force algorithm is also a Greedy algorithm.
v3