AL_09_01 - Wielomian 1

[redysz]

Zadanie: link
Moje rozwiązanie: https://ideone.com/q5poyD

Rozwiązanie jest wolniejsze (zapewne) od wzorcowego niemniej otrzymuję błędną odpowiedź co mnie w tym wypadku dziwi. Sprawdzam tylko zakres od -100 do 100 bo tylko tam mogą być rozwiązania całkowite wielomianu o współczynnikach z zakresu [-100,100].

PS. Wynik jest różny od tego na stronie spoja gdyż nie musi być taki sam “Dla każdego zestawu testowego należy w osobnej linii wypisać dowolne rozwiązanie równania z przedziału [0,2^15)”.

Czy ktoś posiada test, którego nie przechodzę?

[tarpauwatratar]

x^2 - 17

[mariusz193]

to zły przykład - musi istnieć rozwiązanie będące liczbą całkowitą

[tarpauwatratar]

Musi, ale w pierścieniu. I istnieje, np. 6423

Dowód: 2^15 | 6423 * 6423 - 17.

A jak ktoś nie wierzy to https://www.wolframalpha.com/input/?i=(6423+*+6423+-+17)+mod+2^15

[redysz]

ja zapis “Należy znaleźć rozwiązanie równania p(x)=0 modulo 2^15.” rozumiałem, że mam najpierw znaleźć rozwiązanie wielomianu rzeczywistego o całkowitych współczynnikach, a dopiero to rozwiązanie mam podzielić modulo 2^15. Zresztą chyba tak jest właśnie napisane. Pierścień o którym mówisz zmienia postać rzeczy.

[mariusz193]

czyli rozwiązanie równania

p(x) % 2^15 = 0

[tarpauwatratar]

Zadanie to stare algoligii i faktycznie jest z deczka słabo opisane (nie ma nawet jakiegoś ładnego obrazka ). Ale od tego jest forum, by tego rodzaju wątpliwości wyjaśniać Oczywiście nie wińmy autora, który stworzył dwa (w trudnych też jest wielomian, ale mod 2^30) ciekawe zadania - autor zapewne nawet nie przypuszczał, że tyle osób po latach będzie mierzyło się z tym zadaniem, już dawno po algolidze.

p(x)=0 modulo 2^15 w treści zadania miało oznaczać p(x) <równa się z trzema kreskami> <2^15 w nawiasie>

Ale będę bardziej pomocny i podpowiem, bo też mnie to ciekawiło i przed chwilą sprawdziłem - przechodzi brute force. W cpp w czasie 0.06 sekund roztrzaskałem zadanie podstawiając kolejne wartości. W Pythonie czy innej żmii pewnie też nie będzie problemu

[redysz]

Nom, to dzięki bardzo za pomoc. Trochę spędziłem czasu nad myśleniem co tu nie gra.

Tak, a więc dla potomnych… poprawny zapis zadania to:
Należy znaleźć rozwiązanie równania p(x) ≡ (0 mod 2^15)
lub tak jak napisał @mariusz193

W Pythonie chyba nie przejdzie brute force

[tarpauwatratar]

W Pythonie chyba nie przejdzie brute force

Z początku myślałem, że w C++ nie przejdzie, ale okazuje się, że 2^15 to na prawdę mała liczba.

Właśnie spróbowałem w Pythonie i lipa… nie sądziłem, że jest aż tak wolny i ok 0.05s w C++ to TLE w Pythonie… Może jakieś buforowanie wyjścia albo wczytanie wejścia za jednym razem a potem sparsowanie coś pomogą? W sumie nie sprawdzałem, ale chyba faktycznie masz rację…

[redysz]

Nie ma problemu z przepisaniem na c++ algorytmu. Najpierw próbuję (zazwyczaj) zrobić w Pythonie jak myślę, że się zmieszczę, a nie lubię c++ za jego tajniki wczytywania wejścia. Na przykład teraz. Czemu mam tylko jedno wyjście?

A co do

nie sądziłem, że jest aż tak wolny i ok 0.05s w C++ to TLE w Pythonie

szkoda, że nie ma żadnego buforu dla wolniejszych języków programowania co by pozostawienie algorytmu, a sama zmiana języka nie wpływała na wynik TLE. Takie sprawdzenie czy np. rozwiązaliśmy zadanie algorytmem o złożoności O(n) po przez sprawdzanie coraz trudniejszych przykładów, ale to już takie marzenie

[tarpauwatratar]

Popełniasz błąd przenosząc jeden język na drugi aż tak dosłownie. W C++ nie musisz używać w tym zadaniu stringów.

 scanf("%d", &t);

  while(t--) {
    scanf("%d", &n);

    for(int i = n; i >= 0; --i) //wczytuje tak bo potem tak mi to latwiej analizowac ;)
      scanf("%d", &coef[i]); 
  }

Powyżej masz fragment mojego kodu, w którym wczytuję wszystko w stylu C. Możesz oczywiście zamiast scanfów robić ciny.

[redysz]

Rozumiem, że nie muszę, ale nie wyjaśnia to dlaczego tamten sposób wczytywania nie zadziałał.

Napisałem tak, nie w celu odwzorowania 1:1 kodu z Pythona, ale dlatego, że taki sposób mi nie zadziałał.

Potrafię rozwiązywać średnie (i czasem trudne) zadania na spoju, ale przydałby mi się podręcznik na temat wczytywania danych jak nic. Co zrobiłem źle w powyższym?

Edit. Jeszcze powinienem zwiększyć n. Tutaj poprawiona wersja, ale też niedziałająca.

[mariusz193]

Moje siłowe rozwiązanie © liczyło się w czasie 0,16
chwilę pomyślałem i zmieniłem operację modulo na inną - i w tym momencie stało się dla mnie jasne jak należy rozwiązać to zadanie poprawnie

[mariusz193]

Tutaj poprawiona wersja, ale też niedziałająca.

wygląda na to, że tylko 2 proste błędy w kodzie, poprawienie zajęło mi mniej niż minutę i poszło