Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: 399 Sum2  (Citit de 17619 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #25 : Iunie 23, 2011, 12:08:43 »

Ti-am modificat sursa si acum ia 100. Ti-am trimis-o prin PM.
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #26 : Iunie 23, 2011, 16:28:59 »

Ti-am modificat sursa si acum ia 100. Ti-am trimis-o prin PM.

Ar trebui sa ii spui si ce a gresit, nu numai sa ii modifici sursa si dupa sa ii o dai. Desigur, poate ai facut asta deja dar eu doar ma asiguram.  Very Happy
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #27 : Iunie 23, 2011, 17:16:18 »

Daca are nelamuriri, va pune intrebari Smile I-am zis ca nu e destul sa obtina punctajul maxim, ci sa si inteleaga programul.
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #28 : Iulie 15, 2011, 22:46:31 »

imi poate sugera si mie cineva care poate sa fie cauza, programul meu merge corect pe toate testele din comentarii, pe testul exemplu si pe toate testele mele, dar totusi obtin numai 10 puncte cu WA pe toate celelalte Brick wall
Eu procedez astfel:
 1. tin un vector cu sume partiale maxime;
 2. tin alt vector cu lungimile de segvente din care se obtin aceste sume partiale maxime;
 3. parcurg elementele de la 1..n, si aleg elementul care are lungimea cuprinsa intre L si U, si are valoare maxima in vectorul cu sume, acest element fiind solutia. Confused
Memorat
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #29 : Iulie 15, 2011, 23:01:54 »

Nu este chiar ok solutia Sad !

Ideea e ca subsecventa de suma maxima se mai poate face si ca maximul dintre A[ i ] - cea mai mica suma partiala pe pozitii anteriaore lui i . Dupa ce observi asta poti deduce usor cum trebuie sa faci mai departe in acest caz Smile .
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #30 : Iulie 15, 2011, 23:13:58 »

poate imi explici remarca dupa exemplu dat, pur si simplu spune terog cum trebue sa procedez in cazul dat:
vectorul : 100  -100 0 -5 0 10 0 1
v. cu sum: 100 -100 0 -5 11 11 1 1
v. cu lung:  1      1   1   1 4   3  2  1
Cam asa construesc eu vectorii pe care i-am enuntat mai sus.
Memorat
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #31 : Iulie 16, 2011, 13:10:17 »

Sumele partiale sunt sumele de pe pozitia 1 la i:

vectorul: 100  -100 0 -5 0 10 0 1
vectorul cu sume: 100 0 0 -5 0 5 5 6

Subsecventa de suma maxima ce se termina pe pozitia i = 8 Smile este:
ssm[ 8 ] = Sum[ 8 ] - min(Sum[8],Sum[7] ... Sum[1]) = 6 - (-5) = 11, ceea ce si este Smile !

ssm pentru fiecare: 100 0 0 -5 0 10 10 11

Acum ar trebui sa fie usor sa deduci cum se rezolva problema Smile!
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #32 : Iulie 16, 2011, 15:22:20 »

ms mult Andrei Cristian, explicatia ta chiar m-a ajutat inca nu am luat punctaj maxim dar oricum sunt multumit ca am scapat de WA, acum sunt sigur ca merg pe o abordare corecta si trebue doar sa ma gindesc la optimizari. peacefingers
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #33 : Iulie 16, 2011, 19:01:17 »

stiu ca deja sunt plictisitor, dar mai am o ultima intrebare; mai este ceva special la aceasta problema? am facut optimizarile necesare si imi intra toate testele in timp, numai ca totusi am WA pe 3 teste, am mai vazut in surse asa situatii, cei care au rezolvat aceasta problema poate imi spuneti si mie, despre ce este vorba Brick wall
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #34 : Ianuarie 03, 2012, 17:03:14 »

Cred ca ar trebui imbunatatite testele pentru ca cu o sursa de 100 p pe testul:
3 3 3
10 -1000 10000
 imi da raspunsul 10000.
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #35 : Noiembrie 01, 2012, 20:22:56 »

Un subsir format din elemente consecutive ale sirului initial nu e o subsecventa?
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #36 : Noiembrie 01, 2012, 21:01:09 »

Ba da, dar daca o formulezi asa atunci nu mai trebuie sa explici ce e o subsecventa. Poate de aceea e scris asa.
Memorat
Theory
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 10



Vezi Profilul
« Răspunde #37 : Februarie 20, 2013, 00:47:54 »

E o mica problema cu testele. Am trimis o sursa in care nu tineam cont de lungimea minima a secventei si am luat 100 Whistle
Memorat
NicuCJ
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #38 : Martie 07, 2013, 11:43:12 »

Iau 90 puncte cu WA pe testul 8. Folosesc un multiset in care bag la fiecare pas s[i+U-1] si scot s[i+L-2] (s fiind sume partiale). Nu inteleg ce ar putea fi gresit Confused?.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #39 : Martie 07, 2013, 17:47:28 »

Nu tratezi cazul in care maximul e un numar negativ.  Tongue
Memorat
NicuCJ
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #40 : Martie 07, 2013, 17:52:45 »

Intr-adevar, dar se pare ca nu asta e problema. Am initializat maxim cu maxim=-10000000000000LL; si tot WA iau. Mersi pentru raspunsul prompt oricum Very Happy
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #41 : Martie 07, 2013, 18:04:06 »

O alta problema pe care o ai e ca tu verifici maximul doar daca poti sa adaugi un element nou in dreapta, dar nu tratezi subsecventele mai scurte. Vezi testul asta

Cod:
5 2 4
-1000 -1000 -1000 1000 1000
Memorat
NicuCJ
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 44



Vezi Profilul
« Răspunde #42 : Martie 07, 2013, 18:10:34 »

Asta era! Mersi mult Very Happy
Memorat
alecsandru
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #43 : Martie 29, 2013, 12:51:11 »

60 pe wrong answer. Aparent am uitat un caz. Brick wall Brick wall
Memorat
uvIanis
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #44 : August 11, 2019, 08:14:49 »

Nu înțeleg de ce iau doar 50p  Brick wall ....
Eu am rezolvat problema așa,  mențin suma curentă și un deque în care introduc elementele în ordinea în care le citesc. Când citesc al i-lea element îl introduc în suma curentă și în deque și urmează cazurile:
- dacă lungimea deque-ului devine mai mare ca U atunci elimin obligatoriu primul element și fac update la sumă, compar cu suma maximă;
- dacă lungimea deque-ului este fix L atunci compar cu suma maximă;
- dacă lungimea deque-ului este mai mare decât L, atunci verific dacă eliminarea primului element din deque ar aduce o îmbunătățire la sumă. dacă da atunci fac update la sumă și elimin elementul; indiferent compar cu suma maximă.

COD:
#include <bits/stdc++.h>
using namespace std;

ifstream fin("sum2.in");
ofstream fout("sum2.out");

int n, l, u, x, s{0}, smax {INT_MIN};

deque<int> dq;

int main()
{
    fin>>n>>l>>u;

    for(int i=1; i<=n; i++){
        fin >> x;

        dq.push_back(x);
        s += x;

        if(dq.size() > u) {
            s -= dq.front();
            dq.pop_front();
            if(s > smax) smax = s;
        }

        if(dq.size() == l){
            if(s > smax) smax = s;
        }

        if(dq.size() > l){
            if(s - dq.front() > s) {
                s -= dq.front();
                dq.pop_front();

            }

            if(s > smax) smax = s;
        }
    }

    fout<<smax;
}
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

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