Smax

[•diac_paul]

Aici se pot pune întrebări legate de problema Smax

[•lookingForAChallenge]

Care este solutia legit la aceasta problema?

[•Djok]

Daca fixam o celula (i,j), observam celulele la distanta cel mult D formeaza un romb. In O(D^2) putem parcurge acest romb si alege maximul dorit. Pentru a intra in timp este nevoie sa construim cate un RMQ pentru fiecare linie si sa alegem maximul in O(D). Complexitatea finala este O(D * N^2). Dar nu-s sigur daca e solutia dorita.

[•lookingForAChallenge]

Aceasta solutie am gasit-o si noi in concurs, dar lua TLE.

Din ce am vazut, majoritatea solutiilor se bazeaza pe urmatoarea idee: se sorteaza descrescator celulele dupa valoare. Sa notam vectorul celulelor cu v. Apoi se aplica urmatorul algoritm.

Cod:

int ans = 0;
for (int i = 0; i < v.size(); i++) {
    for (int j = i + 1; j < v.size() && v[j] + v[i] > ans; j++) {
        if (celulele i si j respecta conditia manhattan) {
            updateaza_ans();
         }
     }
}

Solutia aceasta ia ~300ms pe testele actuale, dar cred ca poate fi combatuta usor de un test in care D-ul e mic (2 sau 3). Totusi chiar si asa, daca D-ul este mic atunci suma maxima se poate afla brut.

Este asta solutia dorita si de comisie sau exista si o alta rezolvare?

[•Djok]

Nu, e clar ca soluția cu sortare e greșită. Eu încă n-am implementat chestia cu RMQ, dar încearcă să adaugi mici optimizări, de genul, dacă a[ i ][ j ] + X <= ans_now atunci nu mai controlezi daca gasesti un nou raspuns (Unde X este valoare maxima din matrice).

[•diac_paul]

Solutia mea este urmatoarea:
Pentru fiecare pozitie x din matrice, putem precalcula maximul de deasupra (pe o linie cu indice strict mai mic) ce e la distana manhattan maxim orice putere a lui 2. Se formeaza o ‘piramida’ de genul:
000000000000
000010000000
000111000000  -> ‘1’ - casute la distanta maxim 4 fata de ‘x’
001111100000
011111110000
0000x0000000
O ‘piramida’ cu 2^k linii este reuniunea a alte 6 piramide cu 2^(k-1) linii. (stanga, dreapta, sus, una care are aceeasi baza si posibil mai raman doua zone dar care se poate deduce usor ca pot fi acoperite de alte doua 'piramide'.

Putem retine doar ‘piramidele’ cu numar de linii egal cu cea mai mare putere a lui 2 <= D, pentru fiecare casuta, apoi rezultatul se poate calcula in O(N * M * 6).
Complexitate O(N * M * log D).
Pentru elemente de pe aceeasi linie, se poate roti matricea si repeta tot algoritmul.


Din pacate au intrat solutii care nu trebuiau sa intre cu sortare sau altele, si unele din cele care aveau implementare cu RMQ / log luau TLE, desi am dublat timpul de executile al sursei mele.

[•wefgef]

Problema admite solutie in O(N*M). Rotesti planul si faci niste deque-uri, asemanator cu problema Struti.