Алгоритмы вопроса: листать столбцы

Question

Предположим, что нам дана сетка mxn из нулей и единиц, и мы хотим преобразовать сетку так, чтобы максимальное количество строк состояло только из единиц.Единственная операция, которую нам разрешено выполнять в сетке, - это выбрать некоторый столбец и перевернуть все нули и единицы в этом столбце.Нам также дано некоторое целое число k, и мы должны выполнить точно k переворотов столбцов.Учитывая сетку и значение k, как определить, какие столбцы нужно перевернуть, чтобы максимизировать количество всех строк?

Я думаю, что нужно что-то динамическое сделать, но яне может прийти к хорошему ответу.Может ли кто-нибудь помочь?

Answer 1

Давайте начнем с размышления над важной деталью проблемы: если две строки содержат столбец, который различается по строкам (например, в одной строке это ноль, а в одной строке это единица), то нет возможности способ сделать обе строки все едиными. Чтобы увидеть это, предположим, что строка x имеет ноль в некотором столбце, а строка y - единицу в этом столбце. Тогда, если мы не перевернем этот столбец, строка x не может быть всеми единицами, а если мы перевернем столбец, то строка y не может быть всеми единицами. Следовательно, если мы посмотрим на исходную матрицу и попытаемся подумать о том, какие строки мы собираемся создать, мы, по сути, просто выберем некоторый набор строк, которые все равны друг другу. Наша цель состоит в том, чтобы выбрать набор одинаковых строк, который будет максимально большим и может быть превращен во все, используя ровно k сальто. Допустим, что строка, которая может быть преобразована во все с использованием ровно k переворотов, является «строкой-кандидатом». Тогда нам просто нужно найти строку-кандидат в матрице, которая появляется наибольшее количество раз.

Фактический алгоритм для этого зависит от того, разрешено ли нам дважды переворачивать один и тот же столбец. Если нет, то строка-кандидат содержит ровно k нулей. Если мы можем перевернуть один и тот же столбец несколько раз, то это немного сложнее. Чтобы все строки были единичными, нам нужно преобразовать каждый ноль в единицу, а затем продолжать тратить оставшиеся сальто, переворачивая один и тот же столбец дважды, чтобы не менять ни один на ноль. Это верно, если разница между k и числом нулей в строке является неотрицательным четным числом.

Используя это, мы получаем следующий алгоритм:

1. Поддерживать отображение хеш-таблицы из строк-кандидатов на их частоту.
2. Для каждого ряда:
   1. Подсчитать число или нули в строке.
   2. Если разница между k и этим числом является неотрицательным четным числом, обновите хеш-таблицу, увеличив частоту этой конкретной строки.
3. Найдите строку-кандидат в хеш-таблице с наибольшей общей частотой.
4. Вывести частоту этого ряда.

В целом, на матрице m x n (m строк, n столбцов) мы посещаем каждую строку один раз. Во время посещения мы выполняем O (n) работу, чтобы посчитать количество нулей, а затем O (1), чтобы проверить, действительно ли это. Если это так, то для обновления хеш-таблицы требуется ожидаемое время O (n), поскольку для хэширования строки требуется шаг O (n). Это означает, что мы тратим O (mn) времени на заполнение таблицы. Наконец, последний шаг занимает время O (m), чтобы найти строку максимальной частоты, для чистого времени выполнения O (mn), которое является линейным по размеру входа. Более того, это асимптотически оптимально, так как, если бы мы потратили меньше времени, чем это, мы не могли бы смотреть на все элементы матрицы!

Надеюсь, это поможет! Это крутая проблема!

Answer 2

Если k столбцов должны быть разными, ответ прост: найдите строку с k нулями, которая встречается чаще всего, и переверните столбцы, чтобы исправить эти строки.Если вы можете перевернуть столбец более одного раза, найдите наиболее часто встречающуюся строку, число нулей которой не превышает k и имеет такую ​​же четность.

Первое решение работает, так как любой другой метод не исправит так многострок.Второй метод работает, так как вы можете отбросить любое четное число переворотов, чтобы выбрать наиболее подходящий тип строки, чтобы попытаться исправить ... сделайте это, перевернув любой неиспользуемый столбец четное число раз.

Извините, если это грубое неправильное толкование вашей проблемы.

Answer 3

Это может быть возможным код:

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;
}

Answer 4

Если кто-то скажет вам, что верхняя строка должна состоять исключительно из 1, вам нужно будет перевернуть все столбцы, которые имеют 0 в верхней части. Точно так же для каждой строки вы можете определить шаблон переворота столбцов, необходимый для того, чтобы сделать эту строку все 1 с.

Итак, определите, для каждой строки, какой порядок переворачивания столбцов требуется, и выясните, какой тип переворотов столбцов встречается чаще всего, например, сохраняя счет в хеш-таблице или выполняя сортировку / объединение шаблонов (хорошо, дороже, но если вы планируете динамическое программирование, я думаю, вы можете себе это позволить).