14 / 17
Jun 2022

Zadanie to (https://pl.spoj.com/problems/FR_10_16/17) akceptowano praktycznie tylko w C lub C++. W Python3 napisałem efektywny kod … no i timeout!
Moim zdaniem coś tu się nie zgadza, śmiem twierdzić.
Problem ze Spoj jest taki, żę nie podawane są dane wejściowe z ostatniego podtestu. Z tego powodu trudno znaleźć przyczynę, co znakomicie ogranicza możliwości edukacyjne, bo uczymy się na błędach.
W tym przypadku zostaję w sytuacji timeout tak bi tak.
Porównajcie sobie do LeetCode.
Przy okazji mój kod:
points=[]
n=int(input())
for i in range(n):
x,y=[int(s) for s in input().split()]
points.append((x,y))
pset=set(points)
count=0
while pset:
x1,y1= pset.pop()
for x2, y2 in pset:
if (x2-x1)==(y2-y1) or (x2-x1)==(y1-y2):
if (x1,y2) not in pset or (x2,y1) not in pset:
continue
else:
count+=1
print(count)

  • created

    May '22
  • last reply

    Jun '22
  • 16

    replies

  • 646

    views

  • 4

    users

  • 2

    likes

  • 3

    links

Podejrzewam, że jeśli przepiszesz ten kod na C++ to nadal dostaniesz TLE.
Jeśli dobrze rozumiem, wrzucasz wszystko do słownika i potem dla każdego elementu przechodzisz po wszystkich pozostałych punktach. Wychodzi O(N^2), co dla danych wejściowych rzędu ~1mln jest nie do przeskoczenia. Nawet w C++.

Co do danych z ostatniego testu, no cóż… SPOJ jest jaki jest i albo się na to zgadzasz i tu zostajesz, albo nie. Ja zawsze wychodzę z założenia, że jeśli dostaję WA, to znaczy, że mam zły lub błędny algorytm. Jeśli TLE - dobry, ale za wolny algorytm. Zazwyczaj to wystarczy

Co do kodu: wrzucam wszystko do zbioru set, który jest sukcesywnie zmniejszany (pop) po każdym punkcie, więc nie jest to rzędu On^2 . Poza tym set() ma bardzo szybkie wyszukiwanie (in set) ze względu na wbudowany hashing, stąd się dziwię Ale ok, pomyślę, albo niech ktoś zrobi to w Python to uwierzę.

W ten sposób zmniejszasz liczbę sprawdzeń o połowę, ale to ciągle jest złożoność kwadratowa.

Tak, ale wyszukiwanie robisz wewnątrz wewnętrznej pętli, więc masz O(N^2) + narzut związany z wyszukiwaniem (w teorii pomijalny, w praktyce da się go odczuć)

Poprawiłem kod. Dla 1812 punktów, gdzie jest 311 kwadratów, liczba iteracji była:
1 640 000 dla poprzedniej wersji, czyli O ( N^2 / 2 ), a teraz jest:
18 000, czyli o dwa rzędy wielkości szybciej!
I co…i nic - dalej jest TLE.

Jest postęp, ale cały czas problem jest z wczytaniem tak dużej liczby danych z konsoli (~1mln). Poszukaj informacji o fast I/O w Pythonie, może to coś pomoże.

Możesz też zrobić test na swoim komputerze. Wygeneruj milion losowych punktów i zapisz je do pliku. A potem zobacz. ile czasu będziesz je wczytywać. To da Ci pewien obraz, czy warto dalej walczyć, czy lepiej napisać to w C++

…i jeszcze dodam, że po zastąpieniu sprawdzania in set() i zastąpieniu tego tablicą logiczną 2001x2001, jak wspominano na forum w dyskusji tego zadania, czego wcześniej nie czytałem, nic to nie pomogło i w dalszym ciągu jest TLE.
Czyli wygląda na to, że faktycznie wąskim gardłem może być standardowe I/O pythona. Tak się zastanawiam, czy można by, w celu uniknięcia wpływu I/O na wynik, wczytywać w Spoj kod tak jak funkcje i pozbyć się wczytywania. Oczywiście zależnie od języka, np. dla Python:

class Rozwiazanie:
def kwadratowySwiat_II(self, points: [list[int]]) -> int:

Tak jest to zrobione np. na leetcode. Dla spoja to chyba by była za duża zmiana.

U mnie PyPy daje praktycznie taki sam czas. Czyli jednak problem z I/O.
( a przy okazji, Pypy w Spoj wywala bląd)

16 days later

Tak jak sugerowano zrobiłem w Python3 fast I/O input=(io.BytesIO(os.read(0, os.fstat(0).st_size)).readline) itd.
No i tym razem kończy się NZEC - ten sam kod oprócz czytania.
Teraz nie wiem, czy program nie ma juz TLE i poszedł dalej w testach i zaliczył wpadkę?
W Spoj brak jest informacji na jakim konkretnie przypadku danych testowych był błąd.
Nie wiem jaki to ma sens niepodawanie tego. Antyedukacyjne, zniechęcające.

Taki urok tego portalu. Mnie też to zawsze denerwowało, nie raz spędziłem długie godziny walcząc z dziwnymi błędami. Trzeba się do tego przyzwyczaić i tyle.

Swoją drogą jak testowałeś swój program? Odpaliłem Twój kod (tak, mam podgląd) na ideone i też dostaje błędy.

A teraz konkrety:

Linijka, którą podałeś działa, ale należy ją odpalić tylko raz, na początku programu (zobacz, że ona podmienia domyślny input, z którego potem pobierasz dane).

Więc odpalasz raz

input=(io.BytesIO(os.read(0, os.fstat(0).st_size)).readline)

A potem korzystasz tylko z input jakby nie było żadnego fast i/o:

n = int(input())
x,y=[int(s) for s in input().split()]

Nie sprawdzałem, czy Twój kod przechodzi w takiej formie, ale przynajmniej działa na ideone (dla testu przykładowego).

Dzięki za sugestię - faktycznie działa teraz fast i/o na ideone!
W Spoj test ma znowu TLE dla opcji Python 3 (3.7.3).
Dla PyPy 3.6.1, Python3 nbc, cpython 2.7.16 też.
Wygląda na to, że za wysoko poprzeczka dla Pythona.

Jakim cudem ten fast io Wam działa?
U mnie wywala się to…
n = int(input())
ValueError: invalid literal for int() with base 10: b’’

OK, już doszedłem, działa online.