No dobra, macie rację. Ale trochę przeceniliście moją inteligencję, każąc mi się wszystkiego domyślać samemu. Począwszy od tego, że opisy rozwiązań nie były powątkowane po zadaniach i pochowane pod dziwnymi tytułami. Teraz już rozumiem, że walka z kubełkami była słuszna, a rozwiązanie w pewnym sensie lepsze od liniowego (ze współczynnikiem <1) nie jest znowu jakąś magią.

Do czego doszedłem (za późno)? Jeżeli mamy w planie policzyć inwersje pomiędzy przedziałami A i B, a martwimy się, że to potrwa za długo. To zróbmy tak: rozbijmy każdy z tych przedziałów na połówki i wykonajmy 4 podzadania: policzmy inwersje pomiędzy A1-B1, A1-B2, A2-B1 i A2-B2. To pozwoli skrócić czas o 50%, dzięki użyciu 4 równoległych maszyn. Jest to odpowiedź na pytanie, jak rozwiązać zadanie nie czytając wszystkiego w jednym nodzie.

> Kiedy w pośpiechu wysyłasz używanego przy testach bruta bez long longów na RYK

> nie wyślij nic w ostatniej rundzie
> dowiedz się że dostanie się na finał byłoby dla ciebie jeszcze prostsze niż myślałeś
> jeszcze bardziej nie żałuj
> profit

Ale nie wiem czego nie wiedziałeś, bo dla mnie wszystko co tu jest jest oczywiste od liceum, więc o to jest moje pytanie. Że jak się było >=2 razy to trzeba być w TOP10?

Zaskakujące jest to, dlatego, że nie doczytałem tego i nie wiedziałem, że tak jest. A teraz już wiem. I tyle

@Konrad, co jest dla Ciebie zaskakującego i nieoczywistego w tym regulaminie, bo nie mam pojęcia? Na pewno nie ma zasad kwalifikowania zawodników, którzy są zapraszani jak inni zrezygnują. Czy byłeś >=2 razy na finale?

@Przemysław
Kuuuuuuuuuurde, nie doczytałem, że w regulaminie jest "Po pięciu rundach zdalnych do finału zawodów zostaje zakwalifikowanych 20 uczestników. Dziesięciu spośród nich to zawodnicy sklasyfikowani na miejscach od 1 do 10 na liście rankingowej A+B. Następnych dziesięciu to najwyżej sklasyfikowani zawodnicy z kolejnych miejsc, z wyłączeniem osób, które przynajmniej dwukrotnie uczestniczyły w finale Potyczek Algorytmicznych.". To tym bardziej nie żałuję, że spędziłem weekend na ciekawszych rzeczach niż zadania z ostatniej rundy.

To jeszcze ja wtrącę swoje trzy grosze.

Zadanie samo w sobie niespecjalnie mi się podobało - na pierwszy rzut oka wyglądało trochę na "wymyślmy i dajmy zawodnikom jakieś zadanie na napisanie heury/losowej strategii" i moim zdaniem nie wyglądało zbyt atrakcyjnie. (Oczywiście, gdyby w jakiś magiczny sposób istniała dowodliwa strategia gwarantująca rozwiązanie zadania z dużym prawodpodobieństwem, to GRA od razu dostałaby u mnie +20 do fajności. Zwykle jednak nie oczekujemy takich rozwiązań po tego typu zadaniach.)

Z drugiej strony nie mam nic przeciwko jednym, może dwu, niestandardowych zadaniach w trakcie rund zdalnych - byleby wciąż miały dość mocny algorytmiczny posmak. Wg mnie GRA była tutaj trochę na granicy i nie dziwię się mieszanym uczuciom zawodników (jestem jednak zaskoczony skrajnym emocjom wokół niej). Ale tutaj powstaje pytanie: czy obecnie zadania rozproszone nie wykorzystują już co najmniej większości quoty na "niestandardowe zadanka"? Trochę nie wiem, co o tym myśleć.

PS. Muszę docenić, że GRA była opracowana naprawdę porządnie. Nie kojarzę z nią żadnych istotnych problemów technicznych, które chyba notorycznie prześladują zadania tego pokroju.

Ja obstawiam, że 80 pts spokojnie wystarczy, bo jest cała masa weteranów, którzy byli już 2 razy na finale i dla nich jest tylko 7 miejsc (pierwsze 3 są zarezerwowane dla gości z Chin, którzy i tak nigdy nie przyjeżdżają na finał). Zatem zostanie 13 miejsc do rozdzielenia wśród tych, którzy nie byli 2 razy na finale.

Nawet, jeśli nie w pierwszym rzucie, to ostateczna lista finalistów będzie zawierała osoby z 80 pts.

:(

Ja bym nie był taki pewien czy 80 spokojnie wystarczy...

@Przemysław Podleśny
No nie do końca stos. Taki "pseudostos" z którego mogę wywalać rzeczy z początku i z końca, a dodawać na koniec. Ja to trzymałem jako: wektor i index na którym faktycznie zaczyna się fragment otoczki. Jak dorzucam nową półpłaszczyznę, to
1. sprawdzam, czy aktualna płaszczyzna jest podzbiorem/nadzbiorem ostatnio dodanej i w pierwszym przypadku wywalam ostatnią, w drugim wywalam aktualną
2. przeglądam od końca to, co już jest w otoczce, patrzę na dwie ostatnie i aktualną i a) jeśli te trzy płaszczyzny są rozłączne, to zwracam pustą otoczkę (czy w przypadku tego zadania wypisuję 0 i kończę program) b) jeśli środkowa jest nadzbiorem przecięcia pierwszej i trzeciej, to wywalam środkową i przeglądam dalej
3. analogicznie od początku
4. Sprawdzam, czy aktualna półpłaszczyzna jest nadzbiorem przecięcia pierwszej i ostatniej w aktualnej otoczce, jeśli nie to ją dorzucam

Tu jest kod. Do sprawdzania, czy przecięcie 3 półpłaszczyzn jest puste (no tak precyzyjnie, czy ma puste wnętrze) i czy jedna płaszczyzna jest nadzbiorem przecięcia dwóch innych liczę odpowiedni wyznacznik. Można do tego dojść tak: a) wyznaczam przecięcie dwóch z tych prostych i wstawiam do równania na trzecią, by zobaczyć, po której stronie proste jest b)założyć: no zawsze jak coś takiego się liczy, to sprawdza się znak wyznacznika, to tu pewnie też, teraz tylko doświadczalnie dobrać, czy ma być dodatni, czy ujemny.
https://pastebin.com/HS7qnNMs
Tymi vsv> nop(o, pair<c u d>, e, a.f o b, a.s o b), clp(+) clp(-) itd. to się nie przejmuj, to jest definicja wszystkich operatorów typu: para + para, para * liczba, -para itd.

g++ kon.cpp -o kon -g (i bez sanitize'ów)
gdb ./kon
r < maxin
Czekamy parę sekund i CTRL+C
Wyskoczy Program received signal SIGINT, Interrupt.
wpisujemy "bt" i mamy w którym miejscu był w momencie, kiedy przerwaliśmy
Z dużym prawdopodobieństwem akurat będzie w najcięższej części kodu, w tym przypadku w konstruktorze kopiującym stringa.

Jakby wprowadzić zmianę, że zamiast kodu wysyła się rozwiązanie (output) dla jakiegoś wejścia losowo generowanego dla każdego uczestnika to problem języka by zniknął. Nawet jeżeli nie dla wszystkich zadań to przynajmniej dla zadań z kat. B, która służyłaby "promowaniu" zawodów wśród szarych klepaczy kodu a starzy wyjadacze mieliby po staremu w kat. A.