Zadania z Olimpiady

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

2

Rozumiesz że pytasz o rozwiazania do konkursu który AKTUALNIE TRWA?! A jak już się skończy to pojawią się oficjalne (i nieoficjalne) rozwiązania.

0

Co z tego że trwa? Te zadania są taką formą wyzwania dla mnie i dodatkową pracą którą muszę ukończyć do końca tego tygodnia(dodatkowa praca dla ambitnych). Jako iż nie potrafię sobie z tym poradzić, więc pytam tutaj. W sumie nie wiem jak się za to zabrać bez drzewa przedziałowego.
Pozdrawiam gorąco :)

0

Pytanie o pomoc w zadaniach do konkursów które aktualnie trwają jest nietyczne w stosunku do innych uczestników konkursu, bez względu czy się bierze udział w konkursie czy nie.
Co do zadania, to jest to typowe zadanie na przetwarzanie odcinków przedziałów i nawet jeśli nigdy się nie robiło podobnego i nie zna się schematu, to dojście do rozwiązania samemu nie powinno sprawić większego problemu.

0

@neves:
Mógłbyś szerzej opisać pomysł wiadomości prywatnej?

0

@kr091 o_O

  1. Jaką mamy pewność że nie bierzesz udziału i nie próbujesz oszukiwać? Szczególnie że "przypadkiem" akurat do końca tygodnia musisz mieć, tak samo jak ta runda OI.
  2. Są inni którzy biorą udział i mogą na forum wejść i przeczytać.

Te zadania są taką formą wyzwania dla mnie i dodatkową pracą którą muszę ukończyć do końca tego tygodnia(dodatkowa praca dla ambitnych).

No to chyba poległeś na tym wyzwaniu skoro nie potrafisz tego sam rozwiązać. Na tym chyba polega wyzwanie że próbujesz coś samodzielnie zrobić?

0

Korci mnie żeby napisać odpowiedź, bo zadanie jest banalne i nie wymaga skomplikowanego algorytmu, ale koledzy mają rację. Poczekaj do 13.

0

@Shalom:
Po co miałbym kłamać? Po to są konkursy by rozwiązywać je samodzielnie. Ja jednak dostałem takie zadania jako zadania dla ambitnych i nie biorę w tym konkursie udziału ... Naprawdę taki problem tylko o to, że trwa ten konkurs? To że akurat mam czas do końca tygodnia to kwestia tego, żebym nie znał odpowiedzi przypadkiem na zajęcia(ale chcę coś zrobić). Zwracam się tutaj, bo próbowałem to zadanie zrobić, ale nic szczególnego nie przychodzi mi do głowy. Pozdrawiam.
PS. Jak wszyscy robią problem, że jest to publicznie i każdy może zobaczyć(to racja), to bardzo proszę o przesłanie na priv wiadomości :)

0

Ja jednak bardzo bym prosił aby nikomu, nieważne za kogo się podaje w internecie, wiadomości na priv nie przesyłać. Olimpiada to jednak dość poważny konkurs i nie rozwalajmy go.

0

Niby dlaczego masz taką prośbę? Przecież pisałem już kilka razy, że nie biorę udziału w tym konkursie ... Ile razy można to powtarzać.

0

Niektórzy mają pomysły na dobre bait'y ale to to nawet nie wiem co napisać ...

0

Najbardziej smutne jest to, że jest to chyba najłatwiejsze z zadań (zadanie "Pion" jest dużo bardziej skomplikowane).
IMO student informatyki nie powinien mieć najmniejszego kłopotu by to rozwiązać.

0

Już , po olimpiadzie ! , podzieliłby się ktoś rozwiązaniem ?

1

To jest typowe zadanie na "zamiatanie" odcinków :).
Każdy wierzchołek to trójka: współrzędna, numer odcinka, i informacja czy to poczatek czy koniec.
Sortujesz wierzchołki po współrzędnej.
A później przetwarzasz je po jednym od lewej do prawej za pomocą miotły.
Jeśli wierzchołek jest początkowy to dodajesz go do miotły, jeśli jest to końcowy to zdejmujesz mu odpowiadajacy wierzchołek poczatkowy z miotły.
Miotła to posortowana tablica wierzchołków poczatkowych po współrzędnej, odcinków które w danym momencie przecinają miotłę.
Po każdym kroku sprawdzasz czy masz na miotle k lub więcej wierzchołków.
Jeśli tak, bierzesz k-ty element z miotły, on jest początkiem spotkania i odejmujesz go od obecnej pozycji miotły, co nam daje długość najdłuższego możliwego spotkania k osób które się kończy w obecnej pozycji miotły.
No i pozostało nam sprawdzić czy wyznaczone spotkanie przez miotłe jest dłuzsze od wcześniej znalezionego rozwiązania, jeśli tak mamy nowe dłuższe rozwiązanie, i zapamietujemy te k odcinków z miotły.
Dalej kończym przetwarzanie tego wierzchołka i przechodzimy do następnego, aż nam się skończą wierzchołki.

0

witam skąd nabyć wiedze potrzebna do rozwiazywania tego typu zadan ? ( tylko nie pisac ze studia )

1

Niebieskie książeczki z omówieniem zadań są wydawane po każdej oi, jest jeszcze kilka ksiązek o tematyce programowania konkursowego:
Algorytmika praktyczna. Nie tylko dla mistrzów, Stańczyk Piotr
Competitive Programmer’s Handbook, Antti Laaksonen
Competitive Programming, Steven Halim
a także na stronach na których organizowane są takie konkursy, zwykle też są jakies materiały edukacyjne.

0
neves napisał(a):

To jest typowe zadanie na "zamiatanie" odcinków :).
Każdy wierzchołek to trójka: współrzędna, numer odcinka, i informacja czy to poczatek czy koniec.
Sortujesz wierzchołki po współrzędnej.
A później przetwarzasz je po jednym od lewej do prawej za pomocą miotły.
Jeśli wierzchołek jest początkowy to dodajesz go do miotły, jeśli jest to końcowy to zdejmujesz mu odpowiadajacy wierzchołek poczatkowy z miotły.
Miotła to posortowana tablica wierzchołków poczatkowych po współrzędnej, odcinków które w danym momencie przecinają miotłę.
Po każdym kroku sprawdzasz czy masz na miotle k lub więcej wierzchołków.
Jeśli tak, bierzesz k-ty element z miotły, on jest początkiem spotkania i odejmujesz go od obecnej pozycji miotły, co nam daje długość najdłuższego możliwego spotkania k osób które się kończy w obecnej pozycji miotły.
No i pozostało nam sprawdzić czy wyznaczone spotkanie przez miotłe jest dłuzsze od wcześniej znalezionego rozwiązania, jeśli tak mamy nowe dłuższe rozwiązanie, i zapamietujemy te k odcinków z miotły.
Dalej kończym przetwarzanie tego wierzchołka i przechodzimy do następnego, aż nam się skończą wierzchołki.

W zasadzie to trzeba by posortować nie tylko po współrzędnej, ale także po początek/koniec, aby przy takich samych współrzędnych początki zawsze były rozważane pierwsze.

1

@nalik:
Wystarczy sortowanie względem początku przedziałów.

Zadanie jest proste. Kluczem do rozwiązania tego zadania jest fakt, że początek danego przedziału może być początkiem 'k' maksymalnie pokrywających się przedziałów. Osobiście zrobiłem to zadanie z użyciem kolejki priorytetowej posiadającej maksymalnie 'k' elementów. Algorytm z kolejką był połączony z wyszukiwaniem binarnym. Każdy przedział posiadał swoją rangę. Ranga była zależna od końca danego przedziału. Jeśli koniec przedziału był większy od poprzedniego największego, to ranga następnego przedziału się zwiększała... Sporo tutaj opisywania, możliwe że jutro podam dalsze szczegóły ;)

0

nie no potrzebne są dwie tablice, jedna opisująca początki a druga opisująca końce obecności prawników.
Potem trzeba jedyni odpowiednio poprzesuwać iteratory na obu tablicach, tak by zawsze mieć wymaganą liczbę i zapamiętywać największy poprawny przedział.
Złożoność wyjdzie o(n log n) z sortowania, a reszta problemu jest liniowa.

0

Wg mnie to tak:

using range_t = pair<int, int>;

struct Point {
    int value;
    bool is_end;
};

void solve(const vector<range_t> &ranges, int k) {

    // Transform ranges to range points.
    auto points = vector<Point>();
    for (auto &r : ranges) {
        points.push_back({r.first, false});
        points.push_back({r.second, true});
    }

    // Sort ...
    sort(points.begin(), points.end(), [](const Point &a, const Point &b) {
        return tie(a.value, a.is_end) < tie(b.value, b.is_end);
    });

    auto open_starts = 0;
    auto longest_joint_range = range_t{-1, -1};
    auto longest_joint_range_size = 0;

    // Swipe from left to right, calculating the longest joint range.
    auto joint_range_start = 0;
    for (auto i = 0; i < points.size(); ++i) {
        if (!points[i].is_end) {
            ++open_starts;
            if (open_starts == k) {
                joint_range_start = i;
            }
        } else {
            // If have more than k opened ranges then try to update longest joint range.
            if (open_starts >= k and longest_joint_range_size < points[i].value - points[joint_range_start].value) {
                longest_joint_range_size = points[i].value - points[joint_range_start].value;
                longest_joint_range = range_t{points[joint_range_start].value, points[i].value};
            }

            // Close opened range. 
            // If had at least k opened ranges, start was pointing to first range in joint range that meet the condition
            // of having at least k opened ranges. Removing the range falsified the condition across the joint range.
            // Move to next start, so the condition might be true once again.
            do {
                joint_range_start++;
            } while (points[joint_range_start].is_end && joint_range_start < i);
            --open_starts;
        }
    }

    // Print the result.
    cout << longest_joint_range_size << endl;
    for (auto i = 0; i < ranges.size(); ++i) {
        if (ranges[i].first <= longest_joint_range.first and ranges[i].second >= longest_joint_range.second) {
            cout << i + 1 << " ";
        }
    }
    cout << endl;
}

Nie testowane na prawdziwych danych, więc może być babol :).

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 :)

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ą.

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