[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Messages posted by: boolTrue
Forum Index » Profile for boolTrue » Messages posted by boolTrue
Author Message
petarsor wrote:
boolTrue wrote:Видов дека има тема за истата задача меѓутоа дали е можно да се реши вака, проблемот лесно се согледува за влез:
7 5
6 4
1 0
1 0
1 0
1 0
Односно, кога веќе имаме посетено град кој враќа вредност по негово посетување, т.е. не може да откриеме колку вредност ни останува за подоцна да ја имаме во предвид.


Не го разбрав баш твоето прашање. Ако прашуваш зошто не функционира твојот код, добро е да го видиш најпрвин решението во другата тема (што ја спомна), има таму добро решение. Пробај да го тргнеш сортирањето, и види дека не работи како што треба.
Едноставно, кај задачава имаме неколку работи кои што ја прават малку потешка за класично динамичко програмирање: фактот што е битен редоследот (во кој ги посетуваме градовите), и тоа што втората вредност се додава од кога веќе е направен митинг (не пред тоа). Инаку ќе функционираат и многу поедноставни решенија.

Да, без сорт повторно дава 1 град помалку/повеќе т.е. исто решение како со алчен алгоритам, а мислев бидејќи е ДП нема да има врска, благодарам

Видов дека има тема за истата задача меѓутоа дали е можно да се реши вака, проблемот лесно се согледува за влез:
7 5
6 4
1 0
1 0
1 0
1 0
Односно, кога веќе имаме посетено град кој враќа вредност по негово посетување, т.е. не може да откриеме колку вредност ни останува за подоцна да ја имаме во предвид.
petarsor wrote:
boolTrue wrote:Фала сега работи, меѓутоа нели го правам истото во горниот код? Сакав да скратам неколку редови код.

Не баш, разгледуваш една позиција (i, j) а печатиш одлуки за друга (m - j, n-i).

Да, ама ова се случува кога двата елементи имаат исти збир, зошто не и кај вториот алгоритам, бидејќи и таму постојат 2 патишта а во решението е можно да е одбран друг од 2та точни патишта, или постои само 1 точен?
petarsor wrote:
boolTrue wrote:Проблемот е што имам точен резултат но погрешен пат, бидејќи ги има повеќе патишта. Како да знам кој е оптималниот пат во задачата?


Тргни од крајот.

Фала сега работи, меѓутоа нели го правам истото во горниот код? Сакав да скратам неколку редови код.
http://mendo.mk/algoritmi/Task.do?competition=150&id=102

Проблемот е што имам точен резултат но погрешен пат, бидејќи ги има повеќе патишта. Како да знам кој е оптималниот пат во задачата? Тест пример:
Влез:
5 5
2 3 4 5 1
1 1 2 4 3
1 3 1 3 1
4 6 3 4 2
3 3 1 1 2
Точен излез:29
1 1
1 2
1 3
1 4
2 4
3 4
4 4
4 5
5 5
Кориснички излез:29
1 1
1 2
2 2
2 3
2 4
2 5
3 5
4 5
5 5
Благодарам, цело време барам ако е > < или =, а не ми текнува да проверам само за двете променливи колку најмалку кршења е потребно
Ако може хинт, не добивам никакви идеи, успевам само да го поправам за тој тест пример но потоа прави грешка на 5
Што треба да сменам во овој код, не минува на 9тиот тест:
MOI wrote:
boolTrue wrote:Ако може некој hint или предлог за точен алгоритам?


Јас вака нешто би пишувал.

Интересно решение но мислам дека е полесно со 2d низа, сепак благодарам

http://mendo.mk/Task.do?id=538
Ако може некој hint или предлог за точен алгоритам?
lekov wrote:Кодот што не ти е битен го ставив во коментари. Поминува за сите тест случаи.

Сум направил глупава грешка, кога го прочитав кодот без непотребниот дел сфатив дека самиот код нема проблем со случајот кој сум го имал на памет хаха, а во врска ако дојде до случај кога не се исполнува вгнездениот while услов и се инкрементира i, 7<7 нема да биде точно, дали е можен ваков случај?


Тест случај 1 вредности:
3 4
1 2 1

Со овој код програмата кај мендо заглавува, кај CodeBlocks дава одговор 1, кој е и точниот одговор, дали некој знае каде е проблемот?
Едит:
Execution time 0.3s, со статички вредности, значи проблемот е кај системот на мендо Не може за цела низа да ја прегледува да се надмине лимит од 1 секунда, а не па само дел од низата.
MOI wrote:Системот ги проверува решенијата на ограничен број тест случаи. Ако пратиш решение, ќе видиш дека задачата се тестира на 5, 10, 20 (или некој друг мал број) тест случаи (не на сите можни вредности). Ако решението поминува точно на одбраните тест случаи во тренинг делот, задачата се смета за решена.

Во повеќето задачи, тест примерите кои се во текстот на задачата се дел од тест случаите, но понекогаш не се (зборувам за тренинг делот).


Ако дојде до ваков ист случај на натпревар, дали ќе ми се важи задачата за решена ако се проверуват рачно?


Мендо вели дека задачата е решена, но за вредностите:
1 1 1
1 2 1
1 1 3
програмата ми дава одговор 2 3, што е грешка, а самиот случај со точниот одговор (3 3) го има на страницата на задачата.

Едно од точните решенија со кои се решава овој проблем е:


TLDR;
Има 1 посебен тест случај од кој може да се заклучи дали има грешка во кодот на програмата..
 
Forum Index » Profile for boolTrue » Messages posted by boolTrue
Go to:   
Powered by JForum 2.1.8 © JForum Team