Author |
Message |
31/01/2018 21:40:15
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
https://practice.geeksforgeeks.org/problems/challenge-by-nikitasha/0
Пробав да ја решам иако знаев дека однапред со мојата имплементација дека ќе го надминува времето на изврушување па затоа барам помош
|
|
|
01/02/2018 13:18:03
|
MOI
Joined: 07/07/2010 16:31:48
Messages: 447
Offline
|
Јас би ја решавал од десно налево. Нешто вака.
|
|
|
01/02/2018 14:11:46
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
аааа одлична идеја , јас пак цело време кога ги помрднувам се отпочеток ги пресметувам а ова навистина прекрасна идеја со едно множење пута 10 бришење со бришење на крајниот елемент со додавање однапред мхмх вкусно Фала многу
|
|
|
12/02/2018 20:39:07
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
Да не правам нов пост , па тука ќе постирам бидејќи имам задача исто од GeeksForGeeks
https://practice.geeksforgeeks.org/problems/path-in-matrix/0
Еве ја задачата, сакам идеја (не код) , јас мислам да почнам од нулти ред сите елементи да ги поминам така што ќе проверувам надоле
max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+blabla[i][j] , но се си мислам дека вака нема да даде точен резултат до крај. Па затоа треба да се почне можеби од прв ред па да проверуваме max(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) ??? ваша идеја
|
|
|
13/02/2018 12:59:07
|
MOI
Joined: 07/07/2010 16:31:48
Messages: 447
Offline
|
Perezmax(dp[i+1 wrote:[j-1],dp[i+1][j],dp[i+1][j+1])+blabla[i][j] , но се си мислам дека вака нема да даде точен резултат до крај. Па затоа треба да се почне можеби од прв ред па да проверуваме max(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) ??? ваша идеја
Второто. Со тоа што ќе имаш плус вредноста на полето каде што си - значи најдобриот пат до некое од претходните 3 полиња (од каде што можеш да дојдеш до тековното) плус вредноста на тековното поле.
Еве и код (кога веќе го искуцав) ако треба помош. Ја намалив големината за да не го читаш ако несакаш Ако сакаш, само ископирај го во некој друг документ.
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
int M[N][N];
for (int r=0; r<N; r++)
for (int c=0; c<N; c++)
cin >> M[r][c];
int best = 0;
for (int r=1; r<N; r++)
for (int c=0; c<N; c++)
{
int value = M[r-1][c];
if (c > 0) value = max(value, M[r-1][c-1]);
if (c+1 < N) value = max(value, M[r-1][c+1]);
M[r][c] = value + M[r][c];
if (r == N-1)
{
best = max(best, M[r][c]);
}
}
cout << best << endl;
}
return 0;
}
|
|
|
13/02/2018 17:48:59
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
Одлично, одлично (благодарам многу за помошта)
https://practice.geeksforgeeks.org/problems/subset-sum-problem/0
Сега за оваа задача треба да се направи матрица сумата на сите елементи и колку елементи
значи sum +=arr[0]+arr[1]+..+arr[n];
и dp[n][sum] ? но дали кодот ќе биде брз ако sum = 100 000 и n=100 ?
|
|
|
13/02/2018 17:50:11
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
Perez wrote:Одлично, одлично (благодарам многу за помошта)
https://practice.geeksforgeeks.org/problems/subset-sum-problem/0
Сега за оваа задача треба да се направи матрица сумата на сите елементи и колку елементи
значи sum +=arr[0]+arr[1]+..+arr[n];
и dp[n][sum] ? но дали кодот ќе биде брз ако sum = 100 000 и n=100 ?
Настрана од ова ме интересира дали MOI учествува на натпреварот или е организатор / професор ?
|
|
|
13/02/2018 18:23:45
|
MOI
Joined: 07/07/2010 16:31:48
Messages: 447
Offline
|
Perez wrote: дали кодот ќе биде брз ако sum = 100 000 и n=100 ?
Не е многу за компјутер
Како помош, прочитај нешто за knapsack (оваа задача е варијација), и еве мое решение ако заглавиш. Генерално, knapsack (проблем на ранец во литература на македонски) е многу познат проблем, и се среќава во разни задачи (и на натпревари!).
(Инаку, ќе почнам да ти ги бришам прашањава да не ти помагаат и други, оти мислам дека треба прво да ги помислиш задачите сам - така најдобро се учи и најдобро се сфаќа зошто некој алгоритам е корисен или не - ако прашуваш за неколку задачи во ист ден, значи не си потрошил доволно време самиот и ние само ти правиме контра услуга)
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int N;
cin >> N;
int dp[100001];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
int sum = 0;
for (int i=0; i<N; i++)
{
int value;
cin >> value;
for (int j=sum; j>=0; j--)
{
if(dp[j])
{
dp[j + value] = 1;
}
}
sum += value;
}
if (sum%2 == 0 && dp[sum/2] == 1)
{
cout << "YES" << endl;
} else
{
cout << "NO" << endl;
}
}
return 0;
}
Perez wrote:Настрана од ова ме интересира дали MOI учествува на натпреварот или е организатор / професор ?
Нема да учествувам , освен (делумно) како организатор. Тука сум само како поранешен натпреварувач и автор на доста материјали за учење и задачи од системов.
This message was edited 1 time. Last update was at 13/02/2018 18:26:48
|
|
|
13/02/2018 18:55:21
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
Фала многу , вака значи, значи DP ми е тешко може да сфатам дел, мм да ,може да не прашам и да не ја решам задачата по 2-3 дена или цела недела да изгубам на една задача
затоа не само hardwork , туку треба нели и smartwork . За да не губам цела недела на една задача одлучив да прашам за неколку задачи како се решаваат, па јас ги разгледувам повеќе време зошто така се решава конкретно DP , а сега вака MOI бидејќи ми помогна многу јас контам веќе малку повеќе DP . Сега решавам истите задачи со мали модификации многу побрзо време бидејќи веќе имам сретнато таква задача. Иначе не ми е целта само copy paste
|
|
|
24/02/2018 13:03:36
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
https://practice.geeksforgeeks.org/problems/equilibrium-point/0
Кодот мој
https://pastebin.com/wPtsEkPz
Input:
42
4 42 27 16 28 3 4 5 9 3 31 5 5 29 10 18 35 35 33 19 41 23 8 32 9 5 8 18 35 13 6 7 6 10 11 13 37 2 25 7 28 43
Its Correct output is:
-1
And Your Code's Output is:
9
Едноставен и глуп алгоритам е што го напишав за секој број зима сума1 од лево и од сума2 од десно и ако бидат еднакви тогаш ...break и да се испечати ...
|
|
|
24/02/2018 13:16:30
|
ThePopivanov
Joined: 24/09/2015 23:17:41
Messages: 16
Offline
|
И јас иам таков код пишано ама не дозволува врменскиот лимит. Мојот код би требало да работи незнам оти прави проблем.
|
|
|
24/02/2018 13:30:02
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
Де прати .. може во условите е ... while(k>=0 ...
|
|
|
24/02/2018 13:31:10
|
ThePopivanov
Joined: 24/09/2015 23:17:41
Messages: 16
Offline
|
И твојата надминува временски лимит, ја средив со овој код работи без проблем имав проблем со иницијализацијата
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
main()
{
int N;
cin >> N;
int A[N], zbir = 0;
for(int i = 0; i < N; i++)
{
cin >> A[i];
zbir += A[i];
}
int lz = 0, dz = 0, tr = 0;
for(int i = 0; i < N; i++)
{
if(i-1 >= 0) lz += A[i-1];
dz = zbir - A[i] - lz;
if(dz == lz)
{
tr = i+1;
break;
}
}
if(tr == 0) tr = -1;
cout << tr;
return 0;
}
|
|
|
24/02/2018 13:52:38
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
А да не ми текна вака може да да супер фала
|
|
|
|