竞争编码-以最小的成本清除所有级别:未通过所有测试用例 [英] Competitive Coding - Clearing all levels with minimum cost : Not passing all test cases

问题描述

当我遇到这个问题时，我正在一个竞争性的编码网站上解决问题.问题指出:
在这个游戏中，有N个等级和M种可用武器.级别从0到N-1编号，武器从0到M-1编号. 您可以按任意顺序清除这些级别.在每个级别中，都需要使用这M种武器的某些子集来清除此级别.如果在特定级别上需要购买x个新武器，则需要支付x ^ 2枚硬币.另请注意，您可以将当前拥有的所有武器带到下一个级别.最初，您没有武器.您能找出可以清除所有关卡所需的最低硬币吗?

I was solving problems on a competitive coding website when I came across this. The problem states that:
In this game 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 . You 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, you need to buy x new weapons, you will pay x^2 coins for it. Also note that you can carry all the weapons you have currently to the next level . Initially, you have no weapons. Can you find out the minimum coins required such that you can clear all the levels?

输入格式 输入的第一行包含2个以空格分隔的整数: N =游戏中的等级数 M =武器种类的数量

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行.这些行的第i个包含长度为M的二进制字符串.如果第j个字符为 这个字符串是1，这意味着我们需要一个j型武器来清除第i个等级.

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.

约束 1< = N< = 20 1< = M< = 20

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

输出格式 打印一个整数即可解决问题.

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

示例测试用例1
输入
1 4
0101

输出
4

Sample TestCase 1
Input
1 4
0101

Output
4

说明 在这个游戏中只有一个关卡.我们需要两种武器-1和3. 没有武器，他将不必购买这些武器，这将使他花费2 ^ 2 = 4枚硬币.

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

示例测试用例2
输入
3 3
111
001
010

Sample TestCase 2
Input
3 3
111
001
010

输出
3

说明 在这个游戏中有3个关卡. 0级(111)需要所有3种武器.第一层(001)仅需要类型2的武器.第二层仅需要类型1的武器.如果我们按给定的顺序(0-1-2)清除层，则总成本= 3 ^ 2 + 0 ^ 2 + 0 ^ 2 = 9个硬币.如果我们按照1-2-0的顺序清除级别，则将花费= 1 ^ 2 + 1 ^ 2 + 1 ^ 2 = 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.

方法
我能够弄清楚，通过遍历二进制字符串，我们可以在每个级别上购买最少的武器，就可以计算出最低成本.

Approach
I was able to figure out that we can calculate the minimum cost by traversing the Binary Strings in a way that we purchase minimum possible weapons at each level.

一种可能的方法是遍历二进制字符串数组，并在数组已经按照正确的顺序排列后计算每个级别的成本.正确的顺序应该是当字符串已经排序时，即上述测试用例的情况，即001、010、111.以此顺序遍历数组并汇总每个级别的成本可以得到正确的答案.

One possible way could be traversing the array of binary strings and calculating the cost for each level while the array is already arranged in the correct order. The correct order should be when the Strings are already sorted i.e. 001, 010, 111 as in case of the above test case. Traversing the arrays in this order and summing up the cost for each level gives the correct answer.

此外，在数组中运行循环以汇总每个级别的成本之前，java中的sort方法可以很好地对这些二进制字符串进行排序.

Also, the sort method in java works fine to sort these Binary Strings before running a loop on the array to sum up cost for each level.

Arrays.sort(weapons);

这种方法在某些测试用例中很好用，但是一半以上的测试用例仍然失败，我无法理解我的逻辑有什么问题.我正在使用按位运算符来计算每个级别所需的武器数量并返回其平方.

This approach work fine for some of the test cases, however more than half of the test cases are still failing and I can't understand whats wrong with my logic. I am using bitwise operators to calculate the number of weapons needed at each level and returning their square.

不幸的是，我看不到失败的测试用例.任何帮助将不胜感激.

Unfortunately, I cannot see the test cases that are failing. Any help is greatly appreciated.

推荐答案

可以通过动态编程解决.

This can be solved by dynamic programming.

状态将是我们目前拥有武器的位掩码.

The state will be the bit mask of weapons we currently own.

过渡将尝试从当前状态依次清除每个n可能的等级，获取我们需要的其他武器并支付费用. 在每个n结果状态下，我们都采用当前方法和所有先前观察到的方法的最低成本. 当我们已经有了一些武器时，某些级别实际上将不需要购买任何其他武器.这种过渡将自动被忽略，因为在这种情况下，我们到达了相同的州并支付了相同的费用.

The transitions will be to try clearing each of the n possible levels in turn from the current state, acquiring the additional weapons we need and paying for them. In each of the n resulting states, we take the minimum cost of the current way to achieve it and all previously observed ways. When we already have some weapons, some levels will actually require no additional weapons to be bought; such transitions will automatically be disregarded since in such case, we arrive at the same state having paid the same cost.

我们从m零状态开始，支付了0. 最终状态是所有给定级别的按位或"，到达那里的最低成本就是答案.

We start at the state of m zeroes, having paid 0. The end state is the bitwise OR of all the given levels, and the minimum cost to get there is the answer.

使用伪代码:

let mask[1], mask[2], ..., mask[n] be the given bit masks of the n levels
p2m = 2 to the power of m
f[0] = 0
all f[1], f[2], ..., f[p2m-1] = infinity
for state = 0, 1, 2, ..., p2m-1:
    current_cost = f[state]
    current_ones = popcount(state)  // popcount is the number of 1 bits
    for level = 1, 2, ..., n:
        new_state = state | mask[level]  // the operation is bitwise OR
        new_cost = current_cost + square (popcount(new_state) - current_ones)
        f[new_state] = min (f[new_state], new_cost)
mask_total = mask[1] | mask[2] | ... | mask[n]
the answer is f[mask_total]

复杂度是O(2^m * n)时间和O(2^m)记忆，对于大多数在线裁判来说，这对于m <= 20和n <= 20应该没问题.

The complexity is O(2^m * n) time and O(2^m) memory, which should be fine for m <= 20 and n <= 20 in most online judges.

这篇关于竞争编码-以最小的成本清除所有级别:未通过所有测试用例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！