Moje rozwiązanie dostało 9, mogę w skrócie napisać czym się różniło.

Załóżmy najpierw n = 2^m. Tak jak we wzorcówce wybieramy dwa wierzchołki, i możemy ograniczyć się do grafów w których te wierzchołki są "takie same". Łączymy je w grupę rozmiaru 2, i zapamiętujemy czy zdecydowaliśmy się dać między nimi krawędź czy nie. Wybieramy kolejne dwa, robimy to samo, i tak dalej. Potem wybieramy dwie grupki dwuwierzchołkowe, i podobnie stwierdzamy że muszą one wyglądać tak samo, w szczególności w obu musieliśmy podjąć tą samą decyzję o dodaniu krawędzi bądź nie. Postępując tak dalej ograniczymy się do grafów o bardzo prostej strukturze - nasz graf rozmiaru 2^m będzie składał się z dwóch identycznych grafów rozmiaru 2^(m-1), a pomiędzy tymi grafami albo wszędzie są krawędzie, albo nie ma żadnych. Łatwo zauważyć że takie grafy będą mieć minimalne pokrycie rozmiaru 2^m - 2^l dla pewnego l, przy czym parzystość liczby grafów o takim pokryciu będzie taka jak parzystość (m po l). Dla n = 2^m mamy więc trywialne rozwiązanie.

W ogólnym przypadku rozkładamy n na sumę potęg dwójki (niech będzie ich t) i ograniczamy się do grafów w których wierzchołḱi są w t grupkach takich jak opisałem wyżej. Wiemy że każda grupa ma kilka możliwych typów, generujemy wszystkie kombinacje, bierzemy te które wystąpiły nieparzystą liczbę razy, i dalej rozumujemy tak jak we wzorcówce - mamy pewne multizbiory, jeśli któryś tworzy zbiór to znamy rozwiązanie, a w przeciwnym przypadku rozgałęziamy się na dwa sposoby. Ja nie robię tego w formie dynamika, tylko równoważnie zamiatając "w przód" - wyciągam multizbiór który jeszcze nie jest zbiorem, wrzucam obie powstałe z niego możliwości do zbioru do rozpatrzenia, przy czym jeśli wrzucam coś drugi raz, to usuwam. Tak do momentu, gdy zostaną nam same zbiory.

To rozwiązanie działa przy ustalonym n, i "spycha" te multizbiory, aż zostaną same zbiory. Gdy przetwarzam większe n, to sprawdzam czy rozwiązałem już problem dla innego n będącego jego podzbiorem (w sensie potęg dwójki w rozkładzie) - jeśli tak, to używam tamtego rozwiązania jako punktu startowego, "doklejając" do każdego zbioru to czego brakuje (patrząc na bity w n które dokładam), i spycham znowu, od tego miejsca.

Ale Ci powiedział.

Autora drugiego kodu dostającego dyszkę za Pokrycia proszę o opisanie optymalizacji użytej w rozwiązaniu. Wydaje się być warta przedstawienia szerszemu gronu.

Pomysł z zadaniem bardzo fajny, ale była jedna kwestia która zdecydowanie zepsuła jakakolwiek przyjemnosc z zadania. Chodzi o biblioteczkę do oceniania. Okazuje się, że ta używana na pretestach działała ponad 20 razy szybciej niż faktyczna. I w ten sposób łatwo było stracić mnóstwo punktów przez nieoptymalne wczytywanie wejscia inspirując się dobrym działaniem programu na maksymalnym teście przykładowym...

+1

@Paweł Ważną zasadą zadań algorytmicznych jest to, że niepoprawne zadania powinny dostawać (w miarę możliwości) 0 pkt, a poprawne, ale nieefektywne coś (np. 1pkt za Pokrycia dla n<=8 :P). To "niekompletne" rozwiązanie było po prostu rozwiązaniem błędnym i bardzo dalekim od wzorcowego, dlatego nie należały się mu żadne punkty (tak samo z rozwiązaniami od tyłu...). Nagradzanie osób walczących do końca jest stosowane i polega na dawaniu punktów rozwiązaniom poprawnym, ale za wolnym, nawet dużo za wolnym. W SZE był to pewnie jakiś backtrack.

Jakub, Ja właśnie tak rozwiązałem to zadanie i dostałem zero punktów (we wszystkich paczkach test E nie przechodzi) i przyznam że jestem rozczarowany. Wysyłając wiedziałem że nie jest to 100% poprawne bo Twój test wrzucony na forum był kontrprzykładem ale już nie byłem w stanie wymyślić nic lepszego. Liczyłem na 1-2 punkty. Uważam że paczki testowe powinny być tak zrobione że takie niekompletne rozwiązanie powinno dostać chociaż 1 punkt. W ten sposób osoby które walczyły do końca mają szansę być odrobinę wyżej w rankingu niż osoby które w ogóle się poddały i nic nie wysłały.

Po pierwsze, brakowało mi w filmowych omówieniach linków do poszczególnych części omówienia w opisie filmu. Przykładowo:

Treść zadania link?t=0s
Spostrzeżenie X link?t=30s
Rozwiązanie link?t=90s
Dowód link?t=150s
Opis struktury danych link?t=300s
itd

Wtedy jeśli mam jakiś swój szkic rozwiązania ale brakuje mi na przykład informacji jak zrobić strukturę danych to oglądam 2 minuty zamiast 15.

Druga rzecz jest taka, że omówienia filmowe bardziej pasują mi do zadań z grupy B a tekstowe do A. Zadania B są bardziej edukacyjne i chyba warto omówić je dokładniej. Z kolei zadania A mogą być dla niektórych za trudne nawet jeśli będą wytłumaczone ze szczegółami, a tym, którzy by zrozumieli wystarczy spokojnie pdf (a na przykład dla mnie nawet będzie wygodniejszy). Z kolei takie zadania jak jedynki czy ciepło-zimno (ale w wersji 2D) mogą być zrozumiałe nawet dla osób, które nie potrafią programować, więc takie omówienia w postaci filmów mogą też pełnić rolę popularyzatorską.

W SZE przekleiłem Dinica z zespołowej biblioteczki ACM-owej. Teoretycznie worst-case w tym zadaniu to O(n^4), ale na wszystkich testach mam 0.00s.

A w Pokryciach można było nie ogarnąć, jak przyspieszyć standardowy dynamik (sploty, FFT i takie tam) i optymalizować sześciana na wszystkie sposoby. Da się go wcisnąć pomimo odstraszających limitów. :)

Bardzo fajny konkurs, ciekawe zadania, organizacyjnie też super.

Moje ulubione zadania to 1A (gra w karty) i 3A (grzybobranie), natomiast jedyne dość smutne zadanie to był Hilbert z rundy weekendowej. Dywizja B ogólnie bardzo przyjemna.

Sporą atrakcją jest dla mnie runda rozproszona.

Również ode mnie wielki plus za bardzo trafny wybór zadania na rundę rozproszoną. Zadanie z rozwiązaniem zostało podane na tacy, a cały problem polegał na zrównolegleniu, co nie było łatwe. Brawo, brawo, brawo!!!

107

Tak ogólnie (patrząc tylko na [B]) zadania były ciekawe, a formuła niektórych (umożliwiająca sprawdzić wszystkie przypadki we własnym zakresie) odświeżająca.

Jaki rodzaj zadań jeszcze mógłby się pojawić? Zawsze lubiłem te, które dało się rozwiązać w domu, a należało przesłać tylko odpowiedź.
Pamiętam, że w przypadku zadań NP, gdzie punktowane były tylko najlepsze wyniki, organizowano zmowy, więc tego rodzaju zadania bym dał, ale właśnie w rozproszonych, bez wcześniejszej wiedzy o wyglądzie testów.
No i od 2010 roku, gdy ITPW miało swoją ostatnią odsłonę brakuje mi trochę gier, ale to już by chyba była przesada ;)

Technicznie i organizacyjnie - dla mnie jak zawsze bez zarzutu.

A ja tu podziękuję, bo bardzo mi się podobało, że zostało wzięte zupełnie stare zadanie i w rundzie rozproszonej zyskało drugą młodość.

Z technicznych kwestii w tym zadaniu, to fajnie że była już napisana cała biblioteka do łatwego testowania (co było już zaznaczone w jednym z poprzednich wątków) oraz format był identyczny jak na OI - pozwalało to uniknąć dodatkowego okołozadaniowego kodu.

87