Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Smax  (Citit de 2754 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
diac_paul
Echipa infoarena
Nu mai tace
*****

Karma: 13
Deconectat Deconectat

Mesaje: 210



Vezi Profilul
« : Septembrie 24, 2016, 06:06:17 »

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


Karma: 3
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #1 : Septembrie 25, 2016, 16:01:53 »

Care este solutia legit la aceasta problema?
Memorat
Djok
Client obisnuit
**

Karma: 10
Deconectat Deconectat

Mesaje: 71



Vezi Profilul
« Răspunde #2 : Septembrie 27, 2016, 17:46:28 »

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.
« Ultima modificare: Septembrie 27, 2016, 18:00:32 de către Valeriu Motroi » Memorat
lookingForAChallenge
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #3 : Septembrie 27, 2016, 19:39:37 »

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?
Memorat
Djok
Client obisnuit
**

Karma: 10
Deconectat Deconectat

Mesaje: 71



Vezi Profilul
« Răspunde #4 : Septembrie 27, 2016, 20:17:32 »

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).
Memorat
diac_paul
Echipa infoarena
Nu mai tace
*****

Karma: 13
Deconectat Deconectat

Mesaje: 210



Vezi Profilul
« Răspunde #5 : Septembrie 27, 2016, 21:02:43 »

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 Sad 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.
« Ultima modificare: Octombrie 01, 2016, 09:50:45 de către Paul Diac » Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #6 : Septembrie 28, 2016, 13:49:29 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines