算法题:翻转列

发布于 11-30 11:52 字数 215 浏览 2 评论 0原文

假设我们有一个由 0 和 1 组成的 mxn 网格,并且想要转换该网格,以便最大行数仅由 1 组成。我们被允许在网格上执行的唯一操作是选择某个列并翻转该列中的所有零和一。我们还得到了一些整数 k,并且必须精确执行 k 列翻转。给定网格和 k 值,我们如何确定翻转哪些列以最大化全为 1 的行数?

我认为需要做一些动态的事情,但我无法得出一个好的答案。有人可以帮忙吗?

Suppose that we are given an m x n grid of zeros and ones and want to transform the grid so that the maximum number of rows are composed solely of ones. The only operation we are allowed to perform on the grid is picking some column and flipping all of the zeros and ones in that column. We are also given some integer k and must perform exactly k columns flips. Given the grid and the value of k, how do we determine which columns to flip to maximize the number of rows that are all ones?

I'm thinking something dynamic would need to be done, but I'm not able to arrive at a good answer. Can someone help out?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

终止放荡2024-12-07 11:52:40

让我们首先考虑问题的一个重要细节:如果两行包含行间不同的列(例如,在一行中它是零,在一行中它是一),那么就没有可能的方法使两行都是 1。为了看到这一点,假设 x 行在某列中有一个 0,而 y 行在该列中有一个 1。然后,如果我们不翻转该列,则行 x 不能全为 1,如果我们翻转该列,则行 y 不能全为 1。因此,如果我们查看原始矩阵并尝试考虑哪些行全部为 1,我们本质上只是选择一些彼此相等的行集。我们的目标是选择尽可能大的一组相同的行,并且可以使用恰好 k 次翻转将其变成所有行。假设可以使用恰好 k 次翻转将其变成所有行的行是“候选行”。那么我们只需要找到矩阵中出现次数最多的候选行即可。

执行此操作的实际算法取决于是否允许我们将同一列翻转两次。如果不是,那么候选行就是其中正好有 k 个零的行。如果我们可以多次翻转同一列,那么这就有点棘手了。为了使该行全为 1,我们需要将每个 0 转换为 1,然后需要继续花费剩余的翻转次数来翻转同一列两次,以避免将任何 1 更改为 0。如果 k 与行中零的数量之间的差是非负偶数,则这种情况成立。

使用它,我们得到以下算法:

  1. 维护从候选行到其频率的映射的哈希表。
  2. 对于每一行:
    1. 计算该行中的数字或零。
    2. 如果 k 与该数字之间的差是非负偶数,则通过增加该特定行的频率来更新哈希表。
  3. 查找哈希表中总频率最大的候选行。
  4. 输出该行的频率。

总的来说,在 mxn 矩阵(m 行,n 列)上,我们每行访问一次。在访问期间,我们执行 O(n) 工作来计算零的数量,然后执行 O(1) 工作来查看它是否有效。如果是这样,则更新哈希表需要预计的 O(n) 时间,因为哈希步骤需要 O(n) 时间来哈希该行。这意味着我们花费 O(mn) 时间填写表格。最后,最后一步需要时间 O(m) 来查找最大频率行,净运行时间为 O(mn),与输入大小呈线性关系。此外,这是渐近最优的,因为如果我们花费的时间少于这个时间,我们就无法查看矩阵元素!

希望这有帮助!这是一个很酷的问题!

Let's begin by thinking about an important detail of the problem: if two rows contain a column that differ across the rows (for example, in one row it's a zero and in one row it's a one), then there is no possible way to make both rows all ones. To see this, suppose that row x has a zero in some column and row y has a one in that column. Then if we don't flip that column, row x can't be all ones, and if we do flip the column then row y can't be all ones. Consequently, if we take a look at the original matrix and try to think about what rows we are going to make all ones, we are essentially just going to pick some set of rows that are all equal to one another. Our goal is then to pick the set of identical rows that is as large as possible and can be made into all ones using exactly k flips. Let's say that a row that can be made into all ones using exactly k flips is a "candidate row.". Then we just need to find the candidate row in the matrix that appears the greatest number of times.

The actual algorithm for doing this depends on whether or not we are allowed to flip the same column twice. If we aren't, then a candidate row is one that has exactly k zeros in it. If we can flip the same column multiple times, then this is a bit trickier. To make the row all ones, we would need to convert each zero to a one, then would need to keep spending the remaining flips flipping the same column twice to avoid changing any one to a zero. This is true if the difference between k and the number of zeros in the row is a nonnegative even number.

Using this, we get the following algorithm:

  1. Maintain a hash table mapping from candidate rows to their frequency.
  2. For each row:
    1. Count the number or zeros in the row.
    2. If the difference between k and this number is a nonnegative even number, update the hash table by incrementing the frequency of this particular row.
  3. Find the candidate row in the hash table with the greatest total frequency.
  4. Output the frequency of that row.

Overall, on an m x n matrix (m rows, n columns), we visit each row once. During the visit, we do O(n) work to count the number of zeros, then O(1) work to see if it is valid. If so, it takes an expected O(n) time to update the hash table, since the hashing step takes O(n) time to hash the row. This means that we spend O(mn) time filling in the table. Finally, the last step takes time O(m) to find the max frequency row, for a net runtime of O(mn), which is linear in the size of the input. Moreover, this is asymptotically optimal, since if we spent less time than this we couldn't look at al, the matrix elements!

Hope this helps! This is a cool problem!

假装爱人2024-12-07 11:52:40

这可能是可能的代码:

int candidateRowCount=0;
void populateHash(int *input, int **hash, int col)
{
    bool found = false;
    for (int i=0; i<candidateRowCount; i++)
    {
        for (int j=0; j<col; j++)
        {
            if(input[j] !=hash[i][j])
                break;
            else
            {
                if (j==(col-1))
                {
                    found = true;
                    hash[i][col] +=1;
                }
            }
        }
    }

    if (!found)
    {   // save current candidate Row  in hash to be used for comparison in else block of above steps of this function 
        for (int i=0; i<col; i++)
        {
            hash[candidateRowCount][i] = input[i];
        }
        hash[candidateRowCount][col] +=1;
        candidateRowCount++;
    }
}

int getMaxCount(int** input, int N , int M, int K)
{
    int **hash= new int *[N];
    // an extra column to save frequency of row i
    for(int i=0; i<M+1; i++)
    {
        hash[i]= new int[M+1];
        hash[i][M] =0;
    }
    for(int i=0; i<N; i++)
        for(int j=0; i<M; j++)
            hash[i][j]=0;

    for(int i=0; i<N; i++)
    {
        int count = 0;
        for (int j=0; j<M; j++)
        {
            if(input[i][j]==0)
                count++;
        }
        if(count<=K)
        {
            int diff= K-count;
            if ((diff >= 0) && ((diff %2)== 0))
            {
                populateHash(input[i], hash, M);
            }
        }
    }

    int maxVal = 0;
    for (int i=0; i<candidateRowCount; i++)
    {
        if(hash[i][M]>maxVal)
            maxVal = hash[i][M];
    }
    return maxVal;
}

int main()
{
    freopen("input.txt", "r", stdin);
    int testcase;
    cin >> testcase;
    for (int t=0; t<testcase; t++)
    {
        int N,M,K;
        cin >> N >>M;
        cin >>K;
        int **input = new int *[N];
        for (int i=0; i<N; i++)
            input[i] = new int [M];
        for (int i=0; i<N; i++)
        {
            for (int j=0; j<M; j++)
            {
                cin >> input[i][j];
            }
        }
        int val= getMaxCount(input, N, M, K);

        cout << "Max Val" <<val << endl;
        candidateRowCount= 0;
    }
    return 0;
}

This could be possible code:

int candidateRowCount=0;
void populateHash(int *input, int **hash, int col)
{
    bool found = false;
    for (int i=0; i<candidateRowCount; i++)
    {
        for (int j=0; j<col; j++)
        {
            if(input[j] !=hash[i][j])
                break;
            else
            {
                if (j==(col-1))
                {
                    found = true;
                    hash[i][col] +=1;
                }
            }
        }
    }

    if (!found)
    {   // save current candidate Row  in hash to be used for comparison in else block of above steps of this function 
        for (int i=0; i<col; i++)
        {
            hash[candidateRowCount][i] = input[i];
        }
        hash[candidateRowCount][col] +=1;
        candidateRowCount++;
    }
}

int getMaxCount(int** input, int N , int M, int K)
{
    int **hash= new int *[N];
    // an extra column to save frequency of row i
    for(int i=0; i<M+1; i++)
    {
        hash[i]= new int[M+1];
        hash[i][M] =0;
    }
    for(int i=0; i<N; i++)
        for(int j=0; i<M; j++)
            hash[i][j]=0;

    for(int i=0; i<N; i++)
    {
        int count = 0;
        for (int j=0; j<M; j++)
        {
            if(input[i][j]==0)
                count++;
        }
        if(count<=K)
        {
            int diff= K-count;
            if ((diff >= 0) && ((diff %2)== 0))
            {
                populateHash(input[i], hash, M);
            }
        }
    }

    int maxVal = 0;
    for (int i=0; i<candidateRowCount; i++)
    {
        if(hash[i][M]>maxVal)
            maxVal = hash[i][M];
    }
    return maxVal;
}

int main()
{
    freopen("input.txt", "r", stdin);
    int testcase;
    cin >> testcase;
    for (int t=0; t<testcase; t++)
    {
        int N,M,K;
        cin >> N >>M;
        cin >>K;
        int **input = new int *[N];
        for (int i=0; i<N; i++)
            input[i] = new int [M];
        for (int i=0; i<N; i++)
        {
            for (int j=0; j<M; j++)
            {
                cin >> input[i][j];
            }
        }
        int val= getMaxCount(input, N, M, K);

        cout << "Max Val" <<val << endl;
        candidateRowCount= 0;
    }
    return 0;
}
じее2024-12-07 11:52:40

如果 k 列必须不同,答案很简单:找到最常出现的 k 个零的行,然后翻转列以修复这些行。如果可以多次翻转一列,请找到最常出现的行,其零个数不大于 k 并且具有相同的奇偶校验。

第一个解决方案有效,因为任何其他方法都无法修复那么多行。第二种方法有效,因为您可以放弃任何偶数次翻转,以便选择最有利的行类型来尝试修复...通过翻转任何未使用的列偶数次来实现此目的。

很抱歉,如果这是对您的问题的严重误解。

If the k columns have to be different, the answer is easy: find the row with k zeros which occurs most frequently, and flip the columns to fix these rows. If you can flip a column more than once, find the most frequently occuring row whose number of zeroes is no greater than k and has the same parity.

The first solution works since any other method will not fix as many rows. The second method works since you can throw away any even number of flips in order to pick the most favorable kind of row to try to fix... do this by flipping any unused column an even number of times.

Sorry if this is a gross misinterpretation of your problem.

悲歌长辞2024-12-07 11:52:40
#include <iostream>
using namespace std;
// Solved in O(n*m)
int count_normal(int **mat, int n, int m)
{
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        int tempCount = 0;
        for (int j = 0; j < m; j++)
            tempCount += mat[i][j];
        if (tempCount == m)
            count += 1;
    }
    return count;
}

int *rowWiseSum(int **mat, int n, int m)
{
    int *rowwisesum = new int[n];
    for (int i = 0; i < n; i++)
    {
        int tempSum = 0;
        for (int j = 0; j < m; j++)
            tempSum += mat[i][j];
        rowwisesum[i] = tempSum;
    }
    return rowwisesum;
}

int count_toggled(int *rowwisesum, int **mat, int toggle, int n, int m)
{
    int count = 0;
    for(int i=0; i<n; i++){
        if(mat[i][toggle]==1){
            rowwisesum[i]-=1;
        }else{
            rowwisesum[i]+=1;
        }
    }
    for(int i=0; i<n; i++){
        if(rowwisesum[i]==m)
            count+=1;
    }

    //resetting rowwisesum
    for (int i = 0; i < n; i++){
        if (mat[i][toggle] == 1){
            rowwisesum[i] += 1;
        }else{
            rowwisesum[i] -= 1;
        }
    }
    return count;
}

int main()
{
    int n, m, k;
    cout << "Enter the value of N : ";
    cin >> n;
    cout << "Enter the value of M : ";
    cin >> m;
    cout << "Enter the value of k : ";
    cin >> k;

    int **mat = new int *[n];
    for (int i = 0; i < n; i++)
    {
        mat[i] = new int[m];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> mat[i][j];
    }

    // for (int i = 0; i < n; i++){
    //     for (int j = 0; j < m; j++)
    //         cout << mat[i][j]<<" ";
    //     cout<<endl;
    // }
    int normalCount = count_normal(mat, n, m);
    if (k % 2 == 0)
    {
        cout << normalCount << endl;
    }
    else
    {
        int *rowwisesum = rowWiseSum(mat, n, m);
        int maxCount = normalCount, toggled = -1;
        for (int i = 0; i < m; i++)
        {
            int count = count_toggled(rowwisesum, mat, i, n, m);
            if (count > maxCount)
            {
                maxCount = count;
                toggled = i;
            }
        }
        cout << "\n\nMaxRowsWithAll1 = " << maxCount << " Upon toggling column " << toggled + 1 << ", " << k << " times" << endl;
    }

    return 0;
}
#include <iostream>
using namespace std;
// Solved in O(n*m)
int count_normal(int **mat, int n, int m)
{
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        int tempCount = 0;
        for (int j = 0; j < m; j++)
            tempCount += mat[i][j];
        if (tempCount == m)
            count += 1;
    }
    return count;
}

int *rowWiseSum(int **mat, int n, int m)
{
    int *rowwisesum = new int[n];
    for (int i = 0; i < n; i++)
    {
        int tempSum = 0;
        for (int j = 0; j < m; j++)
            tempSum += mat[i][j];
        rowwisesum[i] = tempSum;
    }
    return rowwisesum;
}

int count_toggled(int *rowwisesum, int **mat, int toggle, int n, int m)
{
    int count = 0;
    for(int i=0; i<n; i++){
        if(mat[i][toggle]==1){
            rowwisesum[i]-=1;
        }else{
            rowwisesum[i]+=1;
        }
    }
    for(int i=0; i<n; i++){
        if(rowwisesum[i]==m)
            count+=1;
    }

    //resetting rowwisesum
    for (int i = 0; i < n; i++){
        if (mat[i][toggle] == 1){
            rowwisesum[i] += 1;
        }else{
            rowwisesum[i] -= 1;
        }
    }
    return count;
}

int main()
{
    int n, m, k;
    cout << "Enter the value of N : ";
    cin >> n;
    cout << "Enter the value of M : ";
    cin >> m;
    cout << "Enter the value of k : ";
    cin >> k;

    int **mat = new int *[n];
    for (int i = 0; i < n; i++)
    {
        mat[i] = new int[m];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> mat[i][j];
    }

    // for (int i = 0; i < n; i++){
    //     for (int j = 0; j < m; j++)
    //         cout << mat[i][j]<<" ";
    //     cout<<endl;
    // }
    int normalCount = count_normal(mat, n, m);
    if (k % 2 == 0)
    {
        cout << normalCount << endl;
    }
    else
    {
        int *rowwisesum = rowWiseSum(mat, n, m);
        int maxCount = normalCount, toggled = -1;
        for (int i = 0; i < m; i++)
        {
            int count = count_toggled(rowwisesum, mat, i, n, m);
            if (count > maxCount)
            {
                maxCount = count;
                toggled = i;
            }
        }
        cout << "\n\nMaxRowsWithAll1 = " << maxCount << " Upon toggling column " << toggled + 1 << ", " << k << " times" << endl;
    }

    return 0;
}
Saygoodbye2024-12-07 11:52:40

Python 中简短而清晰的实现

    t = int(input())
    
    def getMaxCount(inp_arr,N,M,K):
        hash_map = dict()
        for row in inp_arr:
            hash_map[str(row)] = 0
    
        for row in inp_arr:
            zeros = row.count(0)
            if (zeros <= k  and (k-zeros)%2==0):
                hash_map[str(row)] += 1
        
        return max(hash_map.values())
    
    
    for _ in range(t):
        n,m,k = map(int,input().split())
        inp_arr=[]
        for i in range(n):
            sub = list(map(int,input().split()))
            inp_arr.append(sub)
        
        ans = getMaxCount(inp_arr,n,m,k)

Short and Crisp implementation in python

    t = int(input())
    
    def getMaxCount(inp_arr,N,M,K):
        hash_map = dict()
        for row in inp_arr:
            hash_map[str(row)] = 0
    
        for row in inp_arr:
            zeros = row.count(0)
            if (zeros <= k  and (k-zeros)%2==0):
                hash_map[str(row)] += 1
        
        return max(hash_map.values())
    
    
    for _ in range(t):
        n,m,k = map(int,input().split())
        inp_arr=[]
        for i in range(n):
            sub = list(map(int,input().split()))
            inp_arr.append(sub)
        
        ans = getMaxCount(inp_arr,n,m,k)
丑疤怪2024-12-07 11:52:40

如果有人告诉你顶行必须完全由 1 组成,那么你将需要翻转顶部有 0 的所有列。同样,对于每一行,您都可以计算出使该行全部为 1 所需的列翻转模式。

因此,计算出每一行所需的列翻转模式,并找出最常发生的列翻转模式,例如通过在哈希表中存储计数或对模式运行排序/合并(好吧,更昂贵,但如果您计划进行动态编程,我认为您可以负担得起)。

If somebody tells you that the top row must be composed entirely of 1s, then you will need to flip all the columns which have a 0 at the top. Similarly, for every row, you can work out the pattern of column flips necessary to make that row all 1s.

So work out, for each row, the pattern of column flips required, and find out which pattern of column flips occurs most often, e.g. by storing a count in a hash table or running sort/merge on the patterns (OK, more expensive, but if you were planning on dynamic programming I reckon you can afford it).

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文