Distance algorithm - minimum coins required to clear all the level

Question

1.00/5 (2 votes)

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 29-Apr-18 3:01am

RaviManna

Updated 29-Apr-18 9:20am

v2

Add a Solution

Comments

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

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

OriginalGriff · Answer 1 · 2018-04-29T04:11:00

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.

Patrice T · Answer 2 · 2018-04-29T09:21:00

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

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

Distance algorithm - minimum coins required to clear all the level

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0