[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Startup  XML
Forum Index » Задачи од меѓународни натпревари
Author Message
MODDI



Joined: 27/12/2017 18:17:00
Messages: 39
Offline


Кодов ми работи на првите 8 случаеви, на останатите ми паѓа на време, како да го убрзам кодов?

This message was edited 1 time. Last update was at 17/06/2019 12:23:45

longhi



Joined: 16/01/2019 22:52:02
Messages: 15
Offline

MODDI wrote:Кодов ми работи на првите 8 случаеви, на останатите ми паѓа на време, како да го убрзам кодов?

Твојот алгоритам има преголема сложеност. Оваа задача може да се реши во линеарно време O(N). Така да, не може секогаш да се "убрза" некој почнат код, и треба да се внимава да направиме анализа на алгоритамот пред да почнеме да решаваме (за да не изгубиме време на пишување на решение кое нема да освои онолку поени колку што очекуваме, па да почнеме од почеток со куцање на нешто друго).

Е сега, во однос на задачата. Размисли дали можеме да пресметаме неколку работи однапред, за да не ги правиме при секоја ротација. Еве еден начин како може да се реши задачава со тој пристап:
    Нека имаме низа frontSum[i] која што ни го памети збирот на првите i броеви - т.е. A[1] + A[2] + A[3] + ... + A[i].
    Нека имаме низа backSum[i] која што ни го памети збирот на сите броеви од i-тиот до N-тиот - т.е. A[i] + A[i+1] + ... + A[N]
    Нека имаме низа frontMin[i] која што го памети најмалиот збир од последователни броеви завршувајќи со i - т.е. min(A[1], A[1]+A[2], ... A[1] + A[2] + ... + A[i])
    Нека имаме низа backMin[i] која што го памети најмалиот збир од последователни броеви почнувајќи со i - т.е. min(A[i], A[i]+A[i+1], A[i]+A[i+1]+A[i+2], ...)


Со овие низи, проверките се доста едноставни за секоја ротација. На пример, ако решиме да ја разгледуваме i-тата ротација (онаа која почнува со i-тиот број), треба само да провериме дали се исполнети овие два услови:
    1) backMin[i] >= 0 (со ова го проверуваме потребниот услов за сите броеви од i-тиот до N-тиот, т.е. дали A[i] >= 0, дали A[i] + A[i+1] >= 0, итн)
    2) backSum[i] + frontMin[i-1] >= 0 (ако ротацијата почнува од i-тиот елемент, тогаш таа по броевите A[i], A[i+1], ... A[N] ќе заврши со броевите A[1], A[2], А[i-1], па со овој чекор го проверуваме условот за тие следни броеви. Види како истиот е сличен на првиот, но додаваме backSum[i]).

За првата ротација не мора да го проверуваме вториот услов, бидејќи таму нема прелевање (т.е. броевите се A[1], A[2], ... A[N]). Еве и код ако уште не е јасно:

 
Forum Index » Задачи од меѓународни натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team