Apr 2024
1 / 8
Apr 2024
Jun 2024
tradiatore
Apr '24
1

Cześć,

Czy byłby ktoś w stanie pomóc mi znaleźć “błąd” w moim programie? Słowo “błąd” ująłem w cudzysłów, ponieważ nie jest to ani błąd kompilacji, ani niepoprawna odpowiedź, a przekroczenie limitu czasowego. Skróciłem złożoność czasową algorytmu na tyle na ile pozwalała mi moja wiedza, ale niestety dalej nie mieszczę się w wymaganych ramach czasowych. Przetestowałem program zarówno na milionie mniejszych łazanek, jak i na dwóch tysiącach tych dużych (bok <= 1e9) i wydaje się być wszystko okay.

[Edit]:
Zadanie rozwiązane

Z góry dzięki i pozdrawiam.

  • created

    Apr '24

  • last reply

    Jun '24
  • 7

    replies

  • 287

    views

  • 4

    users

  • 6

    likes

yula
Apr '24

A ty wiesz co twój program robi i po co? Jesteś pewny że potrzeba aż tylu wywołań funkcji porównującej ? Sprawdź ile razy i do czego porównuje. Raczej algorytm do przemyślenia jeszcze. Jak będziesz takie zadanie robić na żywo to będziesz je robić tak samo jak twój kod?

narbej
Apr '24

Tym razem nie wielkość, ale ilość jest ważniejsza… Przecież i małe i duże to są te same inty i jeden zajmuje tyle samo miejsca i czasu czy jest duży czy mały. Zawsze jeden czy kilka rejestrów procka.

Ale @yula ma rację. Coś tam mocno przekombinowałeś.
Np wydaje mi się, że
Wczytujesz w pętli (…, … , ++i)
I zapisujesz i, i+1, i+2, więc w taki sposób nadpisujesz wczytane wartości. Efektywnie masz co trzecią daną.
Możliwe, że twój program “czeka”, na następne dane a ich brak?

Ps
Czy robiłeś zadanie sort1?

tradiatore
Apr '24

@yula
Tak, wiem co robi mój kod. Czy potrzeba aż tylu wywołań funkcji porównującej - skoro zadajesz to pytanie to pewnie nie, aczkolwiek nie wpadłem jeszcze na pomysł jak to uprościć :slight_smile:. Szczerze zagięłaś mnie z pytaniem jakbym to robił w rzeczywistości - wydaje mi się, że wizualnie “łapałbym” cały zbiór i wtedy jakoś dobierał potencjalnych kandydatów, ale nie wydaje mi się, żeby to było do zrobienia w C w prosty sposób (bez implementacji a’la pythonowskich setów)

@narbej
Tak jak napisałeś, tablica jest rozmiaru 3*n, jako reprezentacja tablicy arr[n][3] a odwołanie do niej następuje poprzez uwzględnienie tego offestu ARRAY_SIZE = 3. Co do pytania - tak wykonałem zadanie “sort1” - było jakoś prostsze :sweat_smile:.

narbej
Apr '24

Dokładnie tak. Ale gdyby potencjalni kandydaci “leżeli” sobie grzecznie obok siebie, nie łatwiej by było ich zauważyć/wyłapać “wizualnie”?

tradiatore
Apr '24

Udało się! Rozwiązaniem okazało się zastosowanie struktur oraz wstępne pogrupowanie łazanek. Dzięki @yula i @narbej :wink:

1 month later