Zadania z Olimpiady

Odpowiedz Nowy wątek
2017-11-05 22:27
0

Witam. Jestem studentem informatyki. Nigdy wcześniej nie przeglądałem żadnych zadań z olimpiad itd. i teraz próbuję zrobić zadania z olimpiady z tego roku. Oczywiście nie mogę wziąć już udziału w tym konkursie, ale chcę zrobić to tak dla siebie.
Właściwie problem mam z każdym zadaniem, ale na początek:

#1 Prawnicy:
Tutaj możnaby zastosować drzewo przedziałowe, tyle że ograniczenie na pamięć eleminuje to rozwiązanie. Jak można to inaczej zrobić? Pomysłów miałem sporo, ale wszystkie są o wiele za wolne.

Ma ktoś jakiś pomysł? Z góry dzięki za odpowiedź.

Link do screenów:

https://imgur.com/a/FNOm7

edytowany 1x, ostatnio: Shalom, 2017-11-06 00:21

Pozostało 580 znaków

2017-12-02 09:11
2

Ja opisałem wcześniej wersję która spogląda w lewą strone miotły (czyli przeszłość) i tak jak @nalik słusznie zauważył, trzeba sortować po dwóch rzeczach.
Ale wersja @krystian99 ze spoglądaniem w prawą stronę miotły (przyszłość) wydaje mi się prostsza w implementacji i bardziej elegancka i taką popełniłem:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
struct Prawnik
{
    int a;
    int b;
    int n;
};
 
bool sortujePoPocztku(const Prawnik& i, const Prawnik& j) { return i.a < j.a; }
bool sortujePoNumerrze(const Prawnik& i, const Prawnik& j) { return i.n < j.n; }
 
struct PorownajPrawnikowNaKolejce
{
    bool operator ()(const Prawnik& p1, const Prawnik& p2)
    {
        return p1.b > p2.b;     
    }
};
 
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    vector<Prawnik> p(n);
    for (int i = 0; i < n; ++i)
    {       
        scanf("%d%d", &p[i].a, &p[i].b);
        p[i].n = i + 1;
    }
 
    // sortujemy po poczatku spotkania
    sort(p.begin(), p.end(), sortujePoPocztku);
 
    // znajdujemy maksymalna dlugosc spotkania i moment t w ktorym się ono zaczęło
    priority_queue <Prawnik, vector<Prawnik>, PorownajPrawnikowNaKolejce> pq;
 
    int max_spotkanie = 0;
    int start_spotkania = -1;
 
    for (int i = 0; i < n; ++i)
    {
        // zdejmujemy tych ktorych czas juz przeminal (czyli prawnikow ktorzy sobie poszli przed przyjsciem obecnego prawnika)
        while ((!pq.empty()) && (pq.top().b <= p[i].a))
        {
            pq.pop();
        }
 
        // dodajemy obecnego prawnika do kolejki
        pq.push(p[i]);
 
        // zdejmujemy jak mamy ich juz za duzo (zdejmujemy tych ktorzy najwczesniej sobie pojda)
        while (pq.size() > k)
        {
            pq.pop();
        }       
 
        // sprawdzamy czy mamy k prawnikow jednoczesnie
        if (pq.size() == k)
        {
            int obecne_spotkania = pq.top().b - p[i].a;
            // sprawdzamy czy mamy lepsze rozwiazanie od poprzedniego
            if (obecne_spotkania > max_spotkanie)
            {
                max_spotkanie = obecne_spotkania;
                start_spotkania = p[i].a;
            }
        }
    }
 
    printf("%d\n", max_spotkanie);
 
    // wypisujemy prawnikow bioracych udzial w spotkaniu
    int koniec_spotkania = start_spotkania + max_spotkanie;
    vector<Prawnik> rozwiazanie;
    for (int i = 0; i < n; ++i)
    {
        if ((p[i].a <= start_spotkania) && (p[i].b >= koniec_spotkania))
        {
            rozwiazanie.push_back(p[i]);
            if (rozwiazanie.size() == k)
            {
                break;
            }
        }
    }
 
    // sortujemy rowiazanie co by sie nam latwiej testy sprawdzalo 
    sort(rozwiazanie.begin(), rozwiazanie.end(), sortujePoNumerrze);
 
    for (int i = 0; i < k; ++i)
    {
        printf("%d ", rozwiazanie[i].n);
    }
 
    return 0;
}

tutaj są dostępne oficjalne testy:
https://sio2.mimuw.edu.pl/c/oi25-1/tests/119/
mój kod działa dobrze dla wszystkich od pra1a do pra4g, dalej mi się sprawdzać nie chciało.

No to teraz czekamy na liniową wersję (pomijając sortowanie) od @MarekR22 :)

edytowany 1x, ostatnio: neves, 2017-12-02 11:04
Fajne, rzeczywiście krótka i elegancka. - nalik 2017-12-02 09:26
Mam bardzo podobną wersję. Ja zastosowałem jeszcze niepotrzebnie wyszukiwanie binarne i złożoność jest minimalnie większa ;) - krystian99 2017-12-02 12:38

Pozostało 580 znaków

2017-12-05 22:36
0

@neves
Za bardzo nie miałem czasu, ale dałem się sprowokować :)
Złożoność po sortowaniu wychodzi mi o(n*k) więc liniowa ze względu na każdy parametr, ale w sumie nie liniowa (jeśli n=k to wychodzi kwadratowa) - skupiłem się jedynie na liczbie prawników i zapomniałem wymagana liczba uczestników spotkania ma wpływ na złożoność.
Można jeszcze to poprawić, ale mi się nie chce.

Biorąc pod uwagę detale zestawów danych testowych opisane pod zadaniem, to można robić bez problemów optymalizacje dla k=1 oraz k=n i mieć w tych wypadkach całkowitą złożoność liniową.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2017-12-05 22:39

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