Jak przyspieszyć mój algorytm?

Odpowiedz Nowy wątek
2019-12-01 20:46
0

Cześć,
Rozwiązuję to zadanie:
https://szkopul.edu.pl/proble[...]qllCwJRK3/site/?key=statement
Kompletnie nie mam pojęcia co mogę zrobić z moim rozwiązaniem, które dostaje 80% pkt, aby było szybsze i przeszło wszystkie testy. Wygląda ono tak:
https://4programmers.net/Pastebin/14743
Jaka jest złożoność mojego algorytmu? Nie potrafię tego ocenić.
Proszę o wskazówki.

Pozostało 580 znaków

2019-12-02 01:14
3

Z podstawowych rzeczy:

  1. Używaj statycznych tablic w takich zadaniach, nie przejmuj się z reguły pamięcią. Statyczna alokacja jest zdecydowanie szybsza.
  2. Jeśli już musisz użyć dynamicznej alokacji (jak std::vector) to użyj reserve jeśli znasz wynikowy rozmiar. Pojedyncza alokacja będzie zdecydowanie szybsza niż to co masz teraz, które co jakiś czas musi realokować tablicę i kopiować wszystkie elementy.

Z pozostałych:

  1. Podziel kod na funkcje, to nie lata 80te by to spowalniało kod, a będzie się go zdecydowanie łatwiej czytało.

Co do algorytmu, to nie wgłębiałem się mocno, ale zapewne zastosowanie będą tutaj miały liczby trójkątne.

Pozostało 580 znaków

2019-12-02 03:07

Da się zrobić z kosztem pamięciowym O(1)

#include <iostream>
using namespace std;

int main()
{
   int n,s;
   cin>>n>>s;
   int minmax=(n*n-n)>>1;
   if((-minmax>s)||(s>minmax)||((minmax^s)&1)) cout<<"NIE"<<endl;
   else
   {
      cout<<0<<endl;
      for(int delta=(minmax-s)>>1,v=0;--n;cout<<v<<endl)
      {
         int dec=(delta>=n);
         if(dec) delta-=n;
         v+=1-(dec<<1);
      }
   }
   return 0;
}

https://ideone.com/gJoyhR
Tylko mam jedno pytanie do tego zadania ...
W sumie rozwiązań może być wiele, na przykład dla 8 4 rozwiązań jest tyle na ile sposobów można dostać liczbę:
14 jako sumę elementów 1,2,3,4,5,6,7,8, np 8+6 lub 6+4+3+1 lub 5+4+3+2
Więc w sumie zadanie niewystarczająco sprecyzowane.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 7x, ostatnio: _13th_Dragon, 2019-12-02 12:05

Pozostało 580 znaków

2019-12-02 19:57
0

@hauleth: Dzięki za rady.
@_13th_Dragon: W zadaniach OI zawsze jest tak, że jeśli istnieje wiele odpowiedzi do zadania to można wypisać dowolną (przynajmniej nigdy się nie spotkałem z odmiennym przypadkiem). Mógłbym Cię prosić o opisanie pokrótce tego algorytmu? Nie rozumiem jak on działa.

Pozostało 580 znaków

2019-12-03 15:06
1

Maksymalna liczba kiedy cały czas idziemy w górę i jest to suma ciągu arytmetycznego: (n*n-n)/2 -> minmax
Zauważ że:

  • jak zmienimy ostatnią liczbę na idącą w dół zamiast w górę to suma nam spadnie o 2
  • jak zmienimy przedostatnią liczbę na idącą w dół zamiast w górę (oczywiście dalej też będzie wszystko pozmieniać) suma nam spadnie o 4
  • jak zmienimy k-tą od końca to suma nam spadnie o k*2
    Natomiast sumę musimy zmniejszyć o: (n*n-n)/2-s ja to dziele przez 2 -> delta aby zmniejszać o k a nie o 2*k
    To int dec=(delta>=n); decyduje czy idziemy w dół.

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Sumy ciągów arytmetycznego zaczynającego się od 0 o przyroście 1 (czyli inaczej mówiąc - sumy początkowych n wyrazów zbioru ℕ) nazywamy liczbami trójkątnymi. - hauleth 2019-12-03 18:23
Bardzo dziękuję. - licealista 2019-12-04 21:58

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0