Zadanie Działka 9 OI

Question

Cześć,

Mam problem z zadaniem działka z 9 OI. Link: https://szkopul.edu.pl/problemset/problem/VZifqMhw2OhTWnQqv7mC5Cge/site/?key=statement

Mój pierwszy pomysł to było poprostu z każdego punktu sprawdzenie wszystkich prostokątów w O(n^4), potem zoptymalizowałem ten kod do O(n^3) naliczając statystyki ile przedmiotów w tym samym wierszu pod rząd na prawo są 0. i wtedy dla każdego punktu, których jest n^2 sprawdzam tylko po wysokosciach. Kod:

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n = 0, max_wynik = 0;

    cin >> n;

    int dzialka[n][n];
    int statystyki[n][n];

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

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (dzialka[i][j] == 1)
            {
                continue;
            }
            if (j == 0 || dzialka[i][j-1] == 1)
            {
                int licznik = 0;
                for (int k = j; k < n; ++k)
                {
                    if (dzialka[i][k] == 0)
                    {
                        licznik++;
                    }
                    else
                    {
                        break;
                    }
                }
                statystyki[i][j] = licznik;
            }
            else
            {
                statystyki[i][j] = statystyki[i][j-1] - 1;
            }
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (dzialka[i][j] == 1)
            {
                continue;
            }
            int max_wspolna_szerokosc = 100000000;
            for (int k = i; k < n; ++k)
            {
                if (dzialka[k][j] == 1)
                {
                    break;
                }
                max_wspolna_szerokosc = min(max_wspolna_szerokosc,statystyki[k][j]);
                max_wynik = max(max_wynik,(k-i+1) * max_wspolna_szerokosc);
            }
        }
    }

    cout << max_wynik << endl;
    return 0;
}

Dostałem tylko 19pkt. Znalazłem rozwiązanie w książeczce: https://www.oi.edu.pl/l/9oi_ksiazeczka/ (strona 85), jednak kompletnie nie rozumiem o co chodzi autorowi.

Z góry dziękuję za pomoc.

Answer 1

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <string>
#include <math.h>
#include <iomanip>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <iterator>

using namespace std;

typedef unsigned short int us;
typedef short int s;
typedef unsigned long int ul;
typedef long int l;
typedef unsigned long long int ull;
typedef long long int ll;
typedef string str;
typedef char c;
typedef bool b;
typedef double d;
typedef long double ld;
typedef float f;

const l INF = 1000000001;
const ll L_INF = 1000000000000000001;
const double EPS = 10e-9;

#define FOR(x, y, z) for(ll z = x; z < y; ++z)
#define FORE(x, y, z) for(ll z = x; z <= y; ++z)
#define FORD(x, y, z) for(ll z = x; z > y; --z)
#define FORDE(x, y, z) for(ll z = x; z >= y; --z)
#define REP(x, y) for(ll y = 0; y < x; ++y)

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair

l** grid;
l maxRectangle(l row, l n);

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	l n, result = 0;
	cin >> n;

	grid = new l * [n];
	REP(n, i)
		grid[i] = new l[n];

	REP(n, i)
	{
		REP(n, j)
		{
			cin >> grid[i][j];
			grid[i][j] = !grid[i][j];
		}
	}
	
	result = max(result, maxRectangle(0, n));

	FOR(1, n, i)
	{
		FOR(0, n, j)
		{
			if (grid[i][j])
				grid[i][j] += grid[i - 1][j];
		}

		result = max(result, maxRectangle(i, n));
	}

	cout << result << "\n";

	cin.ignore();
	cin.get();
}

l maxRectangle(l row, l n)
{
	stack<l> result;
	l max_area = 0, area = 0, top_val;

	l k = 0;
	while (k < n)
	{
		if (result.empty() || grid[row][k] >= grid[row][result.top()])
			result.push(k++);

		else
		{
			top_val = grid[row][result.top()];
			result.pop();
			area = top_val * k;

			if(!result.empty())
				area = top_val * (k - result.top() - 1);

			max_area = max(area, max_area);
		}
	}

	while (!result.empty())
	{
		top_val = grid[row][result.top()];
		result.pop();
		area = top_val * k;

		if (!result.empty())
			area = top_val * (k - result.top() - 1);

		max_area = max(area, max_area);
	}

	return max_area;
}

Tu jest mój kod, który kiedyś napisałem do tego zadania. Powinien być troche bardziej zrozumiały od tego z książeczki.

Ogólnie pomysł był taki, żeby dla każdego wiersza, traktować każde G[i] jako wysokość szukanego prostokąta. Wtedy trzeba tylko znaleźć ile bezpośrednio na lewo i na prawo jest takich G[j], że G[j] >= G[i] i z tego mamy pole prostokąta. Można to zrobić stosem monotonicznym, który gwarantuje że kolejne G[i] są niemalejące.

Comments

Zadanie plakatowanie można rozwiązać na kilka sposobów i jeden z nich korzysta z podobnego pomysłu co w zadaniu Działka

---

@Whistleroosh, 

Trochę mi to zajeło, żeby to pojąć. Wróciłem do tego zadania po 1,5 miesiąca po zrobieniu plakatowania i wyszło.

I teraz tak jak ktoś by się kiedyś męczył:

Zadanie plakatowanie można zrobić przynajmniej na 3 sposoby:

1 - Drzewa przedziałowe z rekurencją O(n log n)

2 - Plakatowanie od góry (set) O(n log n)

3 - I własnie ten na stos monotonniczny. O(n)

Te plakatowanie na stosie jest łatwiejsze niż działka, więc warto zrobić wcześniej. Jest omówienie w książeczce OI i w przygodach Bajtazara.

Po zrobieniu plakatowania chcąc zabrać się do działki polecam zrobić zadanie Largest Rectangle in a Histogram z SPOJ-a na stos monotonniczny. https://www.spoj.com/problems/HISTOGRA/

A zadanie działka to odpalamy algorytm Histogramowy na każdym wierszu i algorytm histogramowy działa w O(n), mamy n wierszy, więc O(n^2) - 100pkt. Musimy tylko dla kazdego wiersza znac wysokosc prostokata zaczynajacego sie w i,j idącego w górę. Dlatego można naliczyć vector 2d stat.

Co ciekawe limity w działce są tak wyśrubowane, że O(n^2 * log n) nie przechodzi. Dokladnie tym samym motywem co plakatowanie od góry w O(n log n), gdzie wchodzi na 100 z dużym zapasem.

Kody:

Dzialka: https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OI/dzialka_stosmonotonniczny100pkt.cpp

Plakatowanie Set: https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OI/plakatowanie_od_gory_set_100pkt.cpp

Plakatowanie stos monotonniczny: https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OI/plakatowanie.cpp

Myślę, że warto napisac plakatowanie od góry na secie, bo fajnie ilustruje motyw 2 setów (jeden po wartościach, drugi po idx-ach). Podobne motyw pojawił się w zadaniu: Wyprzedzanie z 1 etapu XXX OI.

Jak ktoś pierwszy raz spotyka się z takim podejsciem do stosu do życzę cierpliwości ;)

Powodzenia!

Edit: Bardzo podobne jest zadanie Marchewka z Zdalnych Warsztatów Olimpijskich Dla Juniorów 2020, polecem, mozna tym sposobem, albo tez bin searchem po wyniku.