[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Задача Кампања регионален 2019  XML
Forum Index » Задачи од национални натпревари
Author Message
ThePopivanov



Joined: 24/09/2015 23:17:41
Messages: 16
Offline

Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто сега на 23 поминува а само на 7 паѓа.

This message was edited 1 time. Last update was at 11/03/2019 13:44:09

longhi



Joined: 16/01/2019 22:52:02
Messages: 18
Offline

ThePopivanov wrote:Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.


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

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

(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)
BATIR



Joined: 20/06/2015 16:36:50
Messages: 155
Offline

Dali pod bitmaski, mislis za site kombinacii da gledame kolku sme potrosile, pri toa da e validno? I da go barame maksimumot?
longhi



Joined: 16/01/2019 22:52:02
Messages: 18
Offline

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



Joined: 24/09/2015 23:17:41
Messages: 16
Offline

longhi wrote:
ThePopivanov wrote:Вчера на натпреварот кога ја решавав оваа падна на скоро сите тест примери освен на 3.
Денеска изменив нешто ситно сега на 23 поминува а само на 7 паѓа.


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

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

(Постојат и други решенија за добивање на делумни поени, dfs, битмаски, итн)

Ама не разбирам оти не работи моето решение
petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

ThePopivanov wrote:Ама не разбирам оти не работи моето решение


Бидејќи ваквите greedy алгоритми функционираат за некои задачи, а за некои не.
На пример, изврши ја твојата програма на овој пример:



Ќе добиеш одговор 2. Точниот одговор е 3.
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

longhi wrote:
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x].


Ne razbiram zosto gi sortiruvas po R[x] a ne po P[x]?
despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

VlatkoSh wrote:
longhi wrote:
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x].


Ne razbiram zosto gi sortiruvas po R[x] a ne po P[x]?


Нека N се парите што ги имаме, и нека имаме 2 градови опишани со вредностите P1 R1 и P2 R2 и нека важи дека R1 > R2. Да претпоставиме дека би било подобро прво да одиме во градот 2, па во градот 1. Тоа е подобро ако и само ако не можеме да одиме прво во 1, па потоа во 2. Според тоа, би важеле следниве неравенства:
P1 > R1, дадено во задачата
P2 > R2, дадено во задачата
R1 > R2, наша претпоставка
N >= P2, за да можеме да појдеме прво во градот 2
N - P1 + R1 < P2, претпоставуваме дека не можеме да појдеме прво во градот 1, па во градот 2. Го обележуваме ова неравенство со (1)
N - P2 + R2 >= P1, претпоставуваме дека можеме да појдеме прво во градот 2, па во градот 1. Го обележуваме ова неравенство со (2)
N < P2 + P1 - R1, добиено од неравенството (1)
N >= P1 + P2 - R2, добиено од неравенството (2)
Бидејќи R1 > R2, P1 + P2 - R1 < P1 + P2 - R2. Тоа ги прави неравенствата (1) и (2) контрадикторни и не може истовремено да важат. Според тоа, заклучуваме дека никогаш не е подобро да одиме прво во градот 2, па во градот 1, а со тоа, сортирањето по R го дава оптималното DP решение.

Дополнително: види го контра-примеров зошто не може да сортираме по P:

This message was edited 1 time. Last update was at 13/03/2019 13:20:20

VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

despotovski01 wrote:
Нека N се парите што ги имаме, и нека имаме 2 градови опишани со вредностите P1 R1 и P2 R2 и нека важи дека R1 > R2. Да претпоставиме дека ...


Fala za objasnuvanjeto, nema podobro od dokaz!
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team