3

На сайте codeforces не могу решить задачу.

В коде представлено 2 решения: minHeight и minHeight2. Оба мои варианта решения превышают ограничение по времени и вроде вторая версия работает хуже.

#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
using uint = unsigned int;

struct Point {
    uint value;
    set<uint> hLess = {};
    set<uint> hMore = {};
    set<uint> vLess = {};
    set<uint> vMore = {};
};

vector<vector<uint> > minHeight(vector<vector<uint> > vec) {
    vector<vector<uint> > result;
    for (uint i = 0; i < vec.size(); ++i) {
        result.push_back(vector<uint>());
        for (uint j = 0; j < vec.at(0).size(); ++j) {
            Point p;
            p.value = vec.at(i).at(j);
            for (uint h = 0; h < vec.at(0).size(); ++h) {
                if (h == j) {
                    continue;
                }
                uint v = vec.at(i).at(h);
                if (v > p.value) {
                    p.hMore.insert(v);
                } else if (v < p.value) {
                    p.hLess.insert(v);
                }
            }
            for (uint vert = 0; vert < vec.size(); ++vert) {
                if (vert == i) {
                    continue;
                }
                uint v = vec.at(vert).at(j);
                if (v > p.value) {
                    p.vMore.insert(v);
                } else if (v < p.value) {
                    p.vLess.insert(v);
                }
            }
            uint res = max(p.hLess.size(), p.vLess.size()) + max(p.hMore.size(), p.vMore.size()) + 1;
            result.at(i).push_back(res);
        }
    }
    return result;
}

vector<vector<uint> > minHeight2(vector<vector<uint> > vec) {
    vector<vector<uint> > result;
    vector<set<uint> > sets[2];
    for (uint i = 0; i < vec.at(0).size(); ++i) {
        sets[0].push_back(set<uint>());
        for (uint j = 0; j < vec.size(); ++j) {
            sets[0][i].insert(vec[j][i]);
        }
    }
    for (auto row: vec) {
        sets[1].push_back(set<uint>(row.cbegin(), row.cend()));
    }
    for (uint i = 0; i < vec.size(); ++i) {
        result.push_back(vector<uint>());
        for (uint j = 0; j < vec.at(0).size(); ++j) {
            uint value = vec.at(i).at(j);
            uint hLess = 0, hMore = 0;
            for (auto v: sets[0][i]) {
                if (v < value) {
                    ++hLess;
                } else if (v > value) {
                    ++hMore;
                }
            }
            uint vLess = 0, vMore = 0;
            for (auto v: sets[1][i]) {
                if (v < value) {
                    ++vLess;
                } else if (v > value) {
                    ++vMore;
                }
            }
            result.at(i).push_back(max(hLess, vLess) + max(hMore, vMore) + 1);
        }
    }
    return result;
}

void print (vector<vector<uint> > v) {
    for (auto row: v) {
        for (auto value: row) {
            cout << value << " ";
        }
        cout << endl;
    }
}

int main()
{
    unsigned int n, m;
    cin >> n >> m;
    vector<vector<uint> > vec;
    for (unsigned int i = 0; i < n; ++i) {
        vec.push_back(vector<uint>());
        for (unsigned int j = 0; j < m; ++j) {
            uint t;
            cin >> t;
            vec[i].push_back(t);
        }
    }
    auto r = minHeight2(vec);
    print(r);
    return 0;
}

2 ответа 2

1

Для каждой строки посчитать ранги элементов и максимальный ранг (max_r_rows[]).
Сделать то же самое для столбцов (max_r_cols[]).
Для каждого пересечения взять ранг этого элемента в строке r_row, в столбце r_col, и посмотреть, что больше.
Если больше ранг в столбце, тогда результатом для данного пересечения будет

max(max_r_cols[col], max_r_rows[row] + r_col - r_row)
-1

Прошу прощения за небольшой оффтоп.

Заинтересовался задачей, и попробовал написать алгоритм решения на Python3.x:

import copy 


in_str = """
2 2
17 56
12 8
""";

print("In str:\t", in_str, end = "------------------\n")





rows = in_str.split('\n');
rows = list(filter(lambda x: x != '', rows));
n, m = list(map(int, rows.pop(0).split(' ') ));

grid = [];

for row in rows:
    tmp = list(map(int, row.split(' ') ));
    grid.append(tmp);

t_grid = list(map(list, zip(*grid)));
out_grid = copy.deepcopy(grid);

for i in range(n):
    for j in range(m):
        x = grid[i][:];
        y = t_grid[j][:];


        # Algo

        dx = len(x) - len(set(x));
        max_x = len(x) - dx;
        #dy = len(y) - len(set(y));  # Рудимент
        #max_y = len(y) - dy;        # Рудимент
        H = max_x;

        count_largers = count_smaller = 0;
        for k in range(len(y)):
            if ( y[k] > x[j] ):
                count_largers += 1;
            if ( y[k] < x[j] ):
                count_smaller += 1;


        reserv_right = max(x) - x[j];
        reserv_left = x[j] - min(x);

        if ( reserv_right - count_largers < 0 ):
            H += count_largers;
        if ( reserv_left - count_smaller < 0 ):
            H += count_smaller;

        # /Algo

        out_grid[i][j] = H;





print("\nres:");
print("In  grid:");
for row in grid:
    print("\t\t\t", end = "");
    for col in row:
        print(col, end = "\t");
    print();


print("Out grid:");
for row in out_grid:
    print("\t\t\t", end = "");
    for col in row:
        print(col, end = "\t");
    print();

Вывод:

In str:  
2 2
17 56
12 8
------------------

res:
In  grid:
            17  56  
            12  8   
Out grid:
            3   2   
            3   2   
[Finished in 0.1s]

Потестил с десяток небольших входных данных с сайта, вроде правильно решает.

Но боюсь с большими матрицами будут проблемы - транспонирование, полное копирование, копирование строк/столбцов (столбец -> строка из транспонированной матрицы) - боюсь займёт много времени.

Но зарегистрируюсь и проверю позже, итак почти 2 дня потратил на выдумки :). Даже самому интересно, выдержит ли временные рамки. Если нет, надо будет что-то с матрицами попроще придумать.

UPD0:

Быстренько составил файл с матрицей 1000*1000, решает долго.. И дело как оказалось не в транспонировании матриц и т.п., а в самом алгоритме. Ну что ж, не силён я в этом..

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.