Click here to Skip to main content
14,326,871 members
Rate this:
Please Sign up or sign in to vote.
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

1 4

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
3 3

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
Updated 29-Apr-18 9:20am
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
Rate this:
Please Sign up or sign in to vote.

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:
Please Sign up or sign in to vote.

Solution 2

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
  buy weapons
  remove the level from pool
display total cost

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

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100