Prosta heura przechodzi oficjalne testy ;)

Ja niestety nie zdążyłem się zorientować, że naklepałem heurę, ale po odwróceniu przedziałów na wejściu akurat by przeszła. Pewnie sporo osób będzie mieć maksy za coś takiego:

http://pastebin.com/crqNjGhu

To jest przeglądanie przedziałów od lewej do prawej i wykonywanie zachłannie tych zadań, które najwcześniej trzeba zacząć robić, żeby mieć szansę zdążyć je zrobić (priorytet po k_i-c_i).
(ale trzeba odwrotnie: przeglądać od końca i wtedy nieszczęśliwie jest accept)

Ja mam maksa za to http://pastebin.com/7WbpL5r1 (n^3) co wydaje się śmieszne w porównaniu z wzorcówką. Nie wiem, czy to działa, czy słabe testy, może komuś się nudzi bez nowych zadań i spróbuje udowodnić poprawność?

Ja wysłałem (oprócz dobrego rozwiązania) także heurę opisaną przez Adama (ale idącą od początku) i ona dostaje 0 punktów (w każdej grupie uwala ją test e). Byłem dość zadowolony, że rozwiązanie, które przechodzi wszystkie testy z forum oprócz mojego dostaje 0 ;)

Zadaje rzeczywiście wydaje się heurogenne...

To jest dlatego, że mi się udało rozwiązać to zadanie. Zawsze jest na PA tak, że jak piszę heurę, to testy są bardzo mocne i dużo punktów mi ubija. Mimo, że heura myli się 2-5 razy na 1k losowych testów, to w każdej grupie jest coś, żeby ją załatwić.

Jeśli natomiast uda mi się rozwiązać zadanie, to oczywiście testy będą na tyle słabe, żeby heurystyki innych zawodników miały szansę wyrównać mój wynik :P

@Michał Włodarczyk

7 2
1 5 4
7 12 2
13 14 1
10 14 3
10 11 1
10 11 1
13 14 1

out:
NIE

Twój kod wypisuje TAK

@Maciek: Czyli jednak słabe testy. Dzięki

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.

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

Ale Ci powiedział.