Zadanie las

Zadanie las
Suchy702
S7
Suchy702
S7
  • Rejestracja:prawie 5 lat
  • Ostatnio:5 dni
  • Postów:354
0

Mam takie zadanie:
Bajtocy posiada spory teren lasu podzielony na n × n kwadratowych pól (ułożonych po n wierszy i n kolumn). Na każdym polu rośnie dokładnie jedno drzewo. Możemy założyć, że znamy wiek każdego drzewa. Bajtocy chce zbudować dom składający się z d kwadratowych pól, jednak w tym celu musi wyciąć część swoich drzew (dokładnie d drzew). Zakładamy, że dom powinien być spójny, czyli z każdego miejsca w domu powinno dać się dojść do każdego innego miejsca. Pomóż Bajtocemu wybrać miejsce budowy domu, tak aby najstarsze drzewo ze wszystkich wyciętych było możliwie najmłodsze.
Wejście
W pierwszym wierszu wejścia są dwie liczby całkowite n i d (1 <= d <= n <= 1 000) oznaczające odpowiednio wielkość terenu oraz rozmiar domu, który chce zbudować Bajtocy. Kolejnych n wierszy zawiera po n liczb całkowitych wi,k (1 <= wi,k <= 10^9) oznaczających wiek drzewa rosnącego na polu w i-tym wierszu i k-tej kolumnie.
Wyjście
Jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnemu wiekowi najstarszego drzewa ze wszystkich wyciętych.
Przykład:
Dla:
5 6
3 4 1 2 4
3 1 2 4 6
6 9 1 1 7
1 7 9 4 1
1 1 1 1 6
Poprawny wynik to:
2

No i wymyśliłem że można dla każdego drzewa zrobić optymalne rozwiązanie tzn dla każdego drzewa dodawać do kolejki priorytetowej jego sąsiadów których nie użyliśmy do budowy domu i brać zawsze tego optymalnego i stworzyłem taki kod

Kopiuj
#include "bits/stdc++.h"
using namespace std;

int find_min_age(int i, int j, vector<vector<int>> las, int d){
    vector<int> dirs = {0, 1, 0, -1, 1, 0, -1, 0};
    vector<vector<bool>> seen(las.size(), vector<bool>(las.size()));
    priority_queue<pair<int, pair<int, int>>> kolejka;
    int min_age, ch_i, ch_j;
    min_age = las[i][j];
    seen[i][j] = true;
    while (d){
        for (int dir = 0; dir < 8; dir += 2){
            ch_i = i + dirs[dir];
            ch_j = j + dirs[dir + 1];
            if (0 <= ch_i && ch_i < las.size() && 0 <= ch_j && ch_j < las.size())
                if (seen[ch_i][ch_j] == false)
                    kolejka.push(make_pair(las[ch_i][ch_j] * -1, make_pair(ch_i, ch_j)));
        }
        min_age = max(min_age, kolejka.top().first * -1);
        i = kolejka.top().second.first;
        j = kolejka.top().second.second;
        seen[i][j] = true;
        kolejka.pop();
        d--;
    }
    return min_age;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, d, min_age;
    cin >> n >> d;
    vector<vector<int>> las(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> las[i][j];
    min_age = 1000000000 + 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            min_age = min(min_age, find_min_age(i, j, las, d-1));  //d-1 bo już użyjemy drzewa o indeksach i, j
    cout << min_age;
return 0;
}

niestety w jednym teście dostaję błędną odpowiedź a w kilku przekraczam czas o 0.01, pomoże mi ktoś zrozumieć gdzie robię błąd?
Tutaj testuje rozwiązania, zadanie ma nazwę "Las"

Competitive Google searcher
edytowany 1x, ostatnio: Suchy702
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
enedil
enedil
enedil
enedil
  • Rejestracja:prawie 12 lat
  • Ostatnio:4 dni
  • Postów:1027
0

Nie wiem co jest w tym kodzie źle, ale algorytm z pewnością można poprawić, bo mam w głowie taki o niższej złożoności (i czasowej, i implementacyjnej :P)

S7
Błędem może być cały mój algorytm :D
enedil
Hmm, w sumie może jest on tylko nieco lepszy - użycie struktury Find and Union, która dodatkowo pamięta rozmiar spójnych składowych.
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
enedil
enedil
enedil
enedil
  • Rejestracja:prawie 12 lat
  • Ostatnio:4 dni
  • Postów:1027
1

A nie jest tak czasem, że przed wstawieniem sprawdzisz, czy element był odwiedzony, ale nie sprawdzisz, czy już jest na kolejce do odwiedzenia, i w ten sposób zdejmiesz dwa razy ten sam element? Ja przed zaznaczaniem, że odwiedzam element, bym jeszcze sprawdził, czy nie był odwiedzony.

edytowany 1x, ostatnio: enedil
S7
o kurde masz racje, musiałbym zrobić drugą tablicę seen żeby to sprawdzać albo jakiś set O_o
S7
Jak zmieniłem tak że seen zaznacza te które dodałem do kolejki to wszystko działa poprawnie ale za długo trwa :(
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
Suchy702
S7
Suchy702
S7
  • Rejestracja:prawie 5 lat
  • Ostatnio:5 dni
  • Postów:354
0

Ogólnie autor dał takie rozwiązanie:
Las
• Zadanie można rozwiązać siłowo w czasie O(n^4) lub sprytniej, w czasie O(n^2 log n).
• Dla każdego drzewa zakładamy, że jest ono najstarsze i wykonujemy przeszukiwanie grafu wszerz po drzewach o takim samym wieku bądź młodszych.
W ten sposób uzyskamy rozwiązanie O(n^4).
• Wynik możemy wyszukiwać binarnie. Zauważmy, że jeżeli można zbudowaćdom, taki że najstarsze drzewo ma wiek co najwyżej x, to można także zbudować taki dom dla każdej wartości większej od x. Przeciwnie, jeśli nie możemy zbudować domu, to również nie będziemy mogli zbudować domu dla każdej wartości mniejszej od x.
• Zauważmy, że wiek najstarszego drzewa musi być wiekiem jednego z drzew, więc możemy posortować wszystkie liczby oznaczające możliwy wiek drzew i w takiej tablicy wyszukiwać binarnie. Wykonujemy algorytm BFS lub DFS, zaczynając od każdego nieodwiedzonego pola, i jeśli którykolwiek z nich pokryje większy obszar niż dom Bajtocego, to da się zbudować dom o rozpatrywanej wielkości.

Competitive Google searcher
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
nalik
nalik
nalik
nalik
  • Rejestracja:ponad 9 lat
  • Ostatnio:24 dni
  • Postów:1039
0
Suchy702 napisał(a):

Ogólnie autor dał takie rozwiązanie:
Las
• Zadanie można rozwiązać siłowo w czasie O(n^4) lub sprytniej, w czasie O(n^2 log n).
• Dla każdego drzewa zakładamy, że jest ono najstarsze i wykonujemy przeszukiwanie grafu wszerz po drzewach o takim samym wieku bądź młodszych.
W ten sposób uzyskamy rozwiązanie O(n^4).
• Wynik możemy wyszukiwać binarnie. Zauważmy, że jeżeli można zbudowaćdom, taki że najstarsze drzewo ma wiek co najwyżej x, to można także zbudować taki dom dla każdej wartości większej od x. Przeciwnie, jeśli nie możemy zbudować domu, to również nie będziemy mogli zbudować domu dla każdej wartości mniejszej od x.
• Zauważmy, że wiek najstarszego drzewa musi być wiekiem jednego z drzew, więc możemy posortować wszystkie liczby oznaczające możliwy wiek drzew i w takiej tablicy wyszukiwać binarnie. Wykonujemy algorytm BFS lub DFS, zaczynając od każdego nieodwiedzonego pola, i jeśli którykolwiek z nich pokryje większy obszar niż dom Bajtocego, to da się zbudować dom o rozpatrywanej wielkości.

No to by było coś takiego:

Kopiuj

int max_continus_fields_with_value_limit(
    const vector<vector<int>> &grid, vector<vector<int>> &visited,
    int iteration, int max_val, tuple<int, int> pos)
{
    static const auto directions = array<tuple<int, int>, 4>{
        tuple<int, int>{1, 0}, {-1, 0}, {0, 1}, {0, -1}
    };
    const auto num_rows = grid.size();
    const auto num_columns = grid.at(0).size();
    auto [row, col] = pos;
    visited[row][col] = iteration;

    auto covered = 1;
    for (auto &direction : directions) {
        auto [dr, dc] = direction;
        auto child = make_pair(row + dr, col + dc);
        auto [child_row, child_col] = child;

        auto range_ok = (0 <= child_row && child_row < num_rows) &&
                        (0 <= child_col && child_col < num_columns);
        if (!range_ok ||
                (visited[child_row][child_col] == iteration) ||
                (grid[child_row][child_col] > max_val)) {
            continue;
        }
        covered += max_continus_fields_with_value_limit(
            grid, visited, iteration, max_val, child);
    }
    return covered;
}

bool k_continus_fields_with_max_value(
    const vector<vector<int>> &grid, vector<vector<int>> &visited,
    int iteration, int max_val, int k)
{
    const auto num_rows = visited.size();
    const auto num_columns = visited.at(0).size();

    for (auto row = 0; row < num_rows; row++) {
        for (auto col = 0; col < num_columns; col++) {
            if ((visited[row][col] == iteration) || (grid[row][col] > max_val))
                continue;
            auto pos = make_pair(row, col);
            auto max_continus = max_continus_fields_with_value_limit(
                grid, visited, iteration, max_val, pos);
            if (max_continus >= k) {
                return true;
            }
        }
    }
    return false;
}

int k_continus_fields_min_value(vector<vector<int>> &grid, int k) {
    const auto num_rows = grid.size();
    const auto num_columns = grid.at(0).size();

    vector<vector<int>> visited(num_rows, vector<int>(num_columns, 0));
    vector<int> values;

    values.reserve(num_rows * num_columns);
    for (auto &row : grid) {
        copy(row.begin(), row.end(), inserter(values, values.end()));
    }
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());

    auto iteration = 0;
    auto start = size_t(0);
    auto end = values.size();
    auto len = values.size();
    while (len > 0) {
        iteration++;
	    auto mid = start + len / 2;
        auto can_cover_k_fields = k_continus_fields_with_max_value(
            grid, visited, iteration, values[mid], k);
        if (can_cover_k_fields) {
            end = mid;
        } else {
            start = mid + 1;
        }
        len = end - start;
    }
    return values[start];
}
edytowany 2x, ostatnio: nalik
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.

Utwórz konto