Algorytmika C++

Question

Mam problem z algorytmem w zadaniu z 2 etapu OIG z przed około 10 lat. Link: https://szkopul.edu.pl/problemset/problem/isVbAEInYlrdxQNvE6mEnS9i/site/?key=statement

Zrobiłem już pierwszą część zadania. Pozostaje mi najtrudniejsze mam Vector liczb typu long long i muszę znaleźć ile jest kombinacji liczb które podzielone na 3 osobowe grupy ( każda dodana do siebie) dają większą wartość niż k czyli np. 15. Wiem, że mogę łatwo to zrobić 3 pętlami, jednak wtedy złożoność czasowa będzie zdecydowanie za duża (3000 * 3000 * 3000) A mam maksymalnie 2,5 sekund limitu czasu. Vector może mieć maks 3000 elementów.

Nie przychodzi mi nic do głowy.

Comments

Pamiętaj, że te 2.5 sekundy dotyczyło komputerów 10 lat temu

Answer 1

Spróbuj policzyć dystanse jakie mogą pokonać wszystkie rakiety złożone z pierwszego i drugiego modułu. Teraz zastanów się, czy dla dowolnego trzeciego modułu x, jesteś w stanie jakoś szybko policzyć ile jest rakiet złożonych z pierwszego i drugiego modułu i tego x, takich że łączna suma ich pokonanego dystansu jest większa od tego k. Postaraj się skorzystać z tego, że wcześniej policzyłeś wszsytkie rakiety 1+2 modułowe

Comments

Tak udało mi się zrobić to tym sposobem. Sortuję pierwsze 2 moduły i 3 wyszukuję wyszukiwaniem binarnym pierwszy, która spełnia założenie. Z O(n*n*n) wartego 80pkt Robi się O(n*n* log n) Warte 100 pkt z dużym zapasem.

Dziękuję za odpowiedź!