Author |
Message |
|
Оваа задача, и вакви слични задачи каде што треба да изброиме колку броеви постојат што задоволуваат некое својство кое не е тривијално обично се решаваат со техниката Digit DP.
Бидејќи постојат броеви со различен број на цифри кои би можеле да го задоволат бараното својство, ќе ја повториме техниката на броење за секоја должина на бројот посебно. Да речеме дека имаме дадна разлика S, |S| = k, и цифрите на S се s_k, s_(k-1), ..., s_1. Нека бројот кој тековно го разгледуваме е N, |N| = q, цифрите на N се n_q, n_(q-1), ..., n_1. Значајно е да спомнеме дека N > S и |N| >= |S|, инаку својството не би можело да биде исполнето. За поедноставување на проблемот, сметаме дека |S| = |N|, со тоа што S го пополнуваме со водечки нули.
За да развиеме техника за броење, треба да увидиме како можеме да ги пресметаме сите различни начини за да се добие цифрата на некоја произволна позиција (k) во бројот S. Првото нешто што би ни текнало на памет е да ги најдеме сите можни вредности на n_k и n_(q-k) за кои важи својството: s_k = n_k - n_(q+1-k). Но, тоа не е сосема точно, бидејќи кога одземаме броеви може да дојде до пренесување на десетки ако n_k < n_(q+1-k). Според тоа, нека carry е бит стринг, кај кој k-тиот бит има вредност 1 ако се пренесува десетка од k-тата во (k-1)-та позиција при одземањето. Нека valid(s, n, k, carry) е функција која враќа дали можеме да ја добиеме k-тата цифра во s од бројот n и пренесувањата carry. Тогаш, valid(s, n, k, carry) = true ако и само ако s_k = 10 * getBit(carry, k+1) + n_k - getBit(carry, k) - n_(q+1-k). Конечно, доаѓаме до следната рекурентна равенка за пресметување на сите можни броеви:
ways(k, carry, q) = cnt_k * ways(k+1, carry, q); k <= q / 2; каде што cnt_k се сите подредени парови (a, b), за кои важи valid(s, n, k, carry) и valid(s, n, q+1-k, carry).
ways(k, carry, q) = 1; k > q / 2;
Бидејќи не можеме однапред да знаеме на кои места ќе имаме пренесување на вредноста, ќе ги испробаме сите вредности на carry, кои се 2^(digitLen-1) на број, каде digitLen е бројот на цифри за кој пресметуваме. Псевдо-кодот на решението е следниот:
Да напоменам дека решението работи за MAX_LEN >= 19. Исто така, carry има вкупно 2^(digitLen-1) вредности, а не 2^(digitLen), поради тоа што не можеме да пренесуваме десетки од првата цифра на десно.
|
|
|
Simon74 wrote:
despotovski01 wrote:Не би можел никој да ти помогне ако не го ставиш остатокот од кодот.
Еве го ставив кодот. Наместо со вектори, решавав со стрингови, но пак истиот проблем.
Надминуваш мемориски лимит кога ги иницијализираш овие вектори:
И да не би паднало на меморија, верувам дека ова решение би паднало на време. Би те поттикнал да размислиш во насока, како да ги претставиш новите сладоледи врз основа на претходно направените и ефикасно да ги чуваш.
|
|
|
Не би можел никој да ти помогне ако не го ставиш остатокот од кодот.
|
|
|
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:
|
|
|
Идеја: размисли како би можел да се реши проблемот да се најде минималниот број на знаци за да се компресираат последните N знаци од текстот, ако последната буква M сме ја поставиле на j-тата позиција.
|
|
|
Решението е добро објаснето на овој сајт.
|
|
|
Тоа е така бидејќи во validMove координатите очекуваш да имаат 0-базиран индекс, но претходно тоа не беше така. За да работи како што било пред промената, validMove треба да изгледа вака:
|
|
|
Хинт: замисли дека втората прашанка, наместо избриши ребро кое излегува од X, беше додади ребро помеѓу X и Y. Како би изгледало решението во тој случај?
Хинт 2: пробај да ја сведеш втората прашанка на додавање на ребра наместо бришење. Која податочна структура би била погодна за брза пресметка на резултатот за првата прашанка?
|
|
|
Решението не ти работи бидејќи не ги земаш во предвид сите можни заеднички делители кои може да ги имаат тие 2 броја. Ти ги броиш оние кои одат до sqrt(min(a, b)), но дали може да имаат и други поголеми делители (хинт: да)?
Хинт 2: ако два броја имаат некој заеднички делител, тој мора да е помал или еднаков на нивниот најголем заеднички делител.
|
|
|
Еве една можна имплементација:
|
|
|
Грешката е тука:
Во вториот случај, не земаш во предвид дека некогаш е подобро Весна да стигне до Крсте без да земе автобус.
Исто така, имаш направено пропуст и во првиот случај, кога N == M или кога B == 0. Не мора да значи дека M > N.
Вака би било добро:
|
|
|
Perez wrote:Дали е ова BackTracking ?
Да. Започнуваш да ги генерираш подмножествата, и го земаш секој елемент во предвид, или го додаваш кон тековото подмножество, или не го додаваш. Евентуално веќе ќе немаш нови елементи за процесирање, па се враќаш наназад да донесеш друга одлука за претходните елементи. Со тоа ги испробуваш сите можности, и ги генерираш сите можни подмножества.
|
|
|
VlatkoSh wrote: if (o.size() == 0) o.push_back(0);
else if (e.size() == 0) e.push_back(0);
Go dadav na kraj, otkoga poveke pati dobiv Runtime Error, mislejki deka vsusnost programata dobivala Segmentation Fault (indeksiranje na prazen Vector, na primer). Ne mislev deka bi dalo gresen odgovor. Smetajte go kako da ne e tamu, pak dobiva Runtime Error. Isto taka, gi iskomentiruvam vtorata i tretata linija od main().
Go popraviv kodot za kako treba da e namenet.
Сега добива runtime error бидејќи не проверуваш дали векторите имаат должина поголема од 0 пред индексирање кај овој дел од кодот:
Справи се со ова и не би требало веќе да добиваш runtime грешки. Имаш уште еден пропуст во решението, но тоа ќе го оставам на тебе да го увидиш.
|
|
|
Кога го пробав твојот код не добивам runtime error, туку погрешен резултат. Проблемот е во тоа што кога немаш парни или немаш непарни цифри во влезот, ти додаваш нулти елемент, што не е валидно. Земи го за пример овој тест случај:
1
2 6 8
Твоето решение враќа резултат 806, што не е точно, прво, бидејќи 0 е парна цифра, а второ, дека ја немаше во влезот. Точното решение во овој случај е 8 (имаме 2 парни цифри, 0 непарни, па само ја земаме најголемата парна цифра што ја имаме).
EDIT: Во одговорот подоле ти е објаснето зошто добиваш runtime error. Јас претпоставував дека кога си го пратил решението си го избришал делот од кодот за пренасочување на stdin и stdout.
|
|
|
Perez wrote:Moze li nekoj da mi objasni koja e razlikava megju DP i brute force ? oti kolku shto gledam i DP gi pominuva site mozni resenija no i Brute Force toa go pravi
Динамичкото програмирање го пресметува решението на даден проблем врз основа на решенијата на помалите подпроблеми на кои може да се разложи тој проблем. Притоа, решенијата на подпроблемите ги чуваме (ова се нарекува мемоизација) така што не мораме да ги пресметуваме повторно. Ова е најголемата добивка која ни ја дава динамичкото програмирање. Но не може секој проблем да се сведе на динамичко програмирање, има проблеми кои не може толку лесно да се разложат на поедноставни подпроблеми така што би се исплатело да одиме со динамичко програмирање. Исто така, не е точно дека со динамичко програмирање ги поминуваме сите можни решенија. Типичен пример: трговски патник (travelling salesman problem). Брут-форс решение би било да се испробаат сите можни патеки и да се одбере најдобрата, во време O(n!) пропорционално со бројот на градови. Од друга страна, решението со динамичко програмирање (O(n^2 * 2^n)), за секое множество поминати градови, за кои не не интересира по кој редослед биле поминати, и даден тековен град во кој се наоѓаме, го пресметува оптималното решение со кое ќе ги поминеме останатите градови. Со тоа драстично се намалува бројот на потребни решенија кои треба да се проверат.
|
|
|
|
|