[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: longhi
Forum Index » Profile for longhi » Messages posted by longhi
Author Message
Scratcher wrote:Немам никаква друга идеја за решавање на оваа задача освен со рекурзија(backtracking)


Втората акција што може да ја направи роботот (две вреќи да се спојат во една) е многу поедноставна од првата (бидејќи таму треба да одлучуваме колку подароци да префрлиме).
Ова може да го средиме така што првата операција воопшто нема да ја правиме, туку ќе ја правиме само втората - но во две насоки, т.е. почнувајќи и од почетната состојба (како што се ќесите спакувани на почеток) и од крајната состојба (како што треба да бидат спакувани). Ова има логика бидејќи едната акција на роботот е слична на втората - само обратно - наместо да спојуваме две вреќи во една, делиме една вреќа на две.

Значи, можеме да напишеме програма која што ќе користи неколку идеи
1) Да пресметаме со колку акции може да се стигне од една состојба до сите други со спојување на вреќи (за тоа може да се искористи queue - слична идеја како кај алгоритамот BFS)
2) Ако од почетната состојба можеме да дојдеме до некоја состојба X, и од крајната состојба може да дојдеме до истата таа состојба X - тогаш може да се стигне од почетната состојба до крајната состојба. Притоа, ако требаат A чекори за да се стигне од почетната состојба до X, и B чекори за да се стигне од крајната состојба до X, тогаш за доаѓање од почетната до крајната состојба преку X требаат вкупно (A+B) чекори.

Ако е уште нејасно, еве решение
BATIR wrote:Dali pod bitmaski, mislis za site kombinacii da gledame kolku sme potrosile, pri toa da e validno? I da go barame maksimumot?

Максимум градови во кои може да се направат митинзи - тоа што се бара во задачата.
Инаку, ако не ме разбра, тоа зборував дека "Постојат и други решенија за добивање на делумни поени" - едно е решението што беше напишано горе (greedy), може со bfs и битмаски (бидејќи има и помали тест случаи на кои се оценуваат решенијата), итн.
ThePopivanov wrote:Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.


Ова е greedy решение и е доста логично, па ќе добие дел од поените (инаку, како што излезе, сите ќе имаа 0 на таа задача).
Но, оваа задача е најдобро да се решава со помош на динамичко програмирање.

Идејата е доста едноставна, ќе користиме матрица dp[c][n] која ќе ни памети во колку најмногу градови може да се направи митинг ако веќе сме разгледале [c] градови и имаме уште [n] средства на располагање.
Сега, ќе ги поминуваме градовите еден по еден и ќе ја пополнуваме матрицава (како и други слични задачи кои се решаваат на ваков начин) и истата ќе содржи некаков резултат.
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x]. За се друго ќе се погрижи динамичкото програмирање. И тоа е решението.

(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)
forelax wrote:Фала, разбрав А и ги погледнав тестовите, random ми изгледаат. Инаку твоето решение има многу повеќе смисла

Мора да се прават од некој граф (добро, со некоја random должина на ребра - ама тоа и не е толку важно), и потоа да се направи матрицата, инаку голем број од резултатите ќе биде "GRESHKA".
Можеби да се додадат некои примери со слични должини, ама тоа е тешко да се погоди оти различни решенија ќе се искуцаат од натпреварувачите. Според резултатите на натпреварот, мислам дека се океј.
forelax wrote:Не очекував решението да работи. Како ефективната временска комплексност не стига до n^4 (бидејќи не добивам надминат временски лимит)? Дали е тоа до лоши тестови?
Еден пример би било кога матрицата на влез ќе е целосно исполнета со единици (освен на дијагоналата). Тогаш што би било поефикасно решение?


Немам време да го разгледам подетално твоето решение, но колку што дискутиравме денес дел од оценувањето е намерно (greedy на четвртата носи дел од поените, тука, итн), за да нема огромен скок во тежината и дека е регионален натпревар (и секако голем број ќе продолжат на државен натпревар).

Инаку, постои доста едноставно решение на задачава, кое отприлика оди вака:
floreloriz123 wrote:https://mendo.club/Task.do?id=704

Знае ли некој зошто не ми поминува на 1/10 тест случаи (на 4тиот мојот код дава резултат 1 23, а треба 1 21)?



Ај види го следниот код (таму каде што е поправено) и размисли зошто овој работи на сите примери.
Хинт: И зошто тоа има врска со ова "Цревата на системот не може да поминат преку полињата со бетонски плочи, но слободно може да поминуваат преку сите други полиња.", и фактот што долу за секое 'C' викаш graph[i][j] = 0; visited[i][j] = true;

P.S. Пробав да променам најмалку работи во кодот, па затоа само сменив во функцијата bfs(), инаку ова може да се поедностави.


MODDI wrote:Ја решавав задачава, кодов ми работи на 6 тест примери, на останатите ми враќа прогрешен резултат, хелп


Има повеќе работи за поправање. Види кодот подолу:
David_Gorgiev wrote:Овој код е за задачата „Точка“ од Научи С++
Може ли некој да ми каже што имам грешка во кодот?


Прво, не мора да проверуваш (како со првиот if) дали податоците се соодветни (ако пишува во текстот дека ќе бидат помеѓу 0 и 1000, на пример, тогаш ќе бидат).
Второ, можеш да симнеш тест случај од МЕНДО и да го извршиш на компјутер за да видиш што е проблемот.

Еве што забележав јас:
1) каде што имаш (by=dx+b) треба наместо dx да е dy.
2) каде што имаш (ax=px+a) треба да имаш само (ax=px), инаку A и B ти се истата точка (види кај B дека користиш dx,dy).

Со тие промени работи на сите тест случаи.
>
MODDI wrote:Ја решавав задачата Зајак од МОИ 2015, ми работи на 3/25 , помош околу кодов.


Не е баш така, кодов како да е за некоја друга задача.
Јас вака би поправил, имаш коментари во програмата ако нешто не е јасно.

MODDI wrote:Ја решавав задачава и ми вади 8/40, може малку помош околу кодов.

Имаш точно решение погоре ако бараш нова идеја.

Инаку, околу кодов, би ти препорачал да почнеш од почеток оти мислам дека малку се имаш измешано со even, noneven и како се тоа го користиш.
На пример, додади го делот што го имам ставено под коментар во твојата програма, и на пример изврши ја кај тебе на компјутер (за пример од текстот на задачата), ќе видиш печати "error", а во тој дел pom треба да е помало од even.size(), бидејќи низата е дефинирана вака: visited_even[even.size()]

MODDI wrote:Овој код ми дава 8/20 точни тест примери останатите 12 ми паѓаат на време, може помош!!

Пред да почнеш со решавање, треба да си направиш анализа на временската сложеност на решението, за да знаеш дали ќе помине на време уште пред да почнеш со куцање на кодот (освен ако не можеш да дојдеш до соодветно решение - тогаш може и вакво, бидејќи ќе освои и ова неколку поени на натпревар или испит или на што и да е).

За задачава, 1) пробај годините да ги гледаш во обратен редослед, 2) види го ова предавање http://mendo.mk/Lecture.do?id=44 и размисли како може да примениме union-find во задачата.
FloreTheFlaus wrote:11/20 тест случаи ми се точни, 9/20 имам надминат временски лимит. Како можам да го оптимизирам кодот?

Не можеш вака да ја решиш, имаш многу операции.

Има повеќе (барем две) идеи за задачава, јас би ти сугерирал тоа што ми е мене најлесно:

1. Сортирај ги двете низи (и girls и guys)
2. Имај еден for за женските (како што имаш сега), и внатре користи бинарно пребарување за машките.
KRISS wrote:Ја решавав оваа задача со ДФС. но ми работи само на 32/50 малку помош!!!

Ти работи на многу примери оти се одговорите со ДА или НЕ. На натпревар ако се дадени во групи ќе имаш малку бодови.
Решението не ти е со рекурзија ниту некој вид DFS, туку само на алгоритамот BFS имаш заменето queue со stack.

Целта на решението објаснето во коментарот над твојот е ако почнуваш од 1 (со бројки означуваме поле), да ги посетиш (ова е само пример) и [1, 2, 3] и [1, 3, 2], бидејќи тие се различни (од 3 и 2 може да има различни следни чекори).
Кај тебе кога ќе се стави нешто дека е посетено, нема да ги разгледаш другите можности. Види на мендо има предавање за рекузија, па таму примерот со пермутациите.
Ако заглавиш, прашај си пак.
 
Forum Index » Profile for longhi » Messages posted by longhi
Go to:   
Powered by JForum 2.1.8 © JForum Team