try this: sample input: 2 -1 -2 -3 -4 sample output: -1 oh i found my mistake Edited by author 03.11.2014 12:28 4 -1 -2 -3 -4 -5 0 -7 -8 -9 -1 -127 -100 -3 -4 -7 -1 I have WA on tc 4 too and am unable to figure it out. Some help? #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector <vector <int>> a(n, vector <int> (n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } int ans = a[0][0]; for (int leng = 1; leng <= n; leng++){ for (int up = 0; up <= n-leng; up++){ vector <long long> sumv(n); for (int j = 0; j < n; j++) { for (int i = up; i < up + leng; i++) { sumv[j] += a[i][j]; } } int sum = 0; for (int r = 0; r < n; ++r) { sum += sumv[r]; ans = max(ans, sum); sum = max(sum, 0); } } } cout << ans; } There a[i][j] in [-127..127] and n <= 100 -- May be there bitmask tricks, or other tricks???? There's one hard solution with quick matrix multiply My code is as following: #include<iostream> #include<vector> using namespace std; long getMaxSumRow(long rowArr[], int n) { long cs = 0; long ms = 0; bool positiveNumberPresent = false; for (int i = 0; i < n; i++) { if (!positiveNumberPresent && (rowArr[i] >= 0)) { positiveNumberPresent = true; } cs += rowArr[i]; if (cs < 0) { cs = 0; continue; } if (cs > ms) { ms = cs; } } if (positiveNumberPresent) { return ms; } ms = rowArr[0]; for (int i = 0; i < n; i++) { if (rowArr[i] > ms) { ms = rowArr[i]; } } return ms; } long maxSumRec(vector<vector<long> > &arr, int n) { if (n == 1) { return arr[0][0]; } /* Take an array for running rows sum */ long runningRowSum[n]; for (int r = 0; r < n; r++) { runningRowSum[r] = 0; } long maxSum = INT_MIN; /* Initialize variables for left-right and top-bottom bounds */ int left, right, top = 0, bottom = n-1; /* Iterate from all possible lefts to all possibe rights ahead of this left */ for (left = 0; left < n; left++) { for (right = 0; right < n; right++) { for (top = 0; top <= bottom; top++) { runningRowSum[top] += arr[top][right]; } /* For this left-right combination, calculate contigeous subarray with maximum sum in runningRowSum */ long currSum = getMaxSumRow(runningRowSum, n); if (currSum > maxSum) { maxSum = currSum; } } /* Reinitialize running row sum to 0 */ for (int r = 0; r < n; r++) { runningRowSum[r] = 0; } } return maxSum; } int main() { int n; cin >> n; vector<vector<long> > arr(n); for (int i = 0; i < n; i++) { arr[i] = vector<long>(n); for (int j = 0; j < n; j++) { cin >> arr[i][j]; } } cout << maxSumRec(arr, n); return 0; } But I am getting wrong answer for test case#3 . Any advice on what it might be failing at ? I can't understand how to solve the problem with Python and meet time limitations. I implemented solution with creating 3-D list of subsumes[column][row_start][row_offset] using accumulate from itertools and list comprehension. After that I used Kadane's algorithm. I expect that it works with O(N^3). But it isn't enough... Are there some tricks in the problem for Python? Except for stdin of course. 1-use dynamic 2-i got AC with 22lined program and 2array [1..100,1..100] (one integer and one longint)(pascal) 3-answer of this sample is -1 -1 -2 -3 -3 -2 -1 -1 -2 -3 4-its best order is O(n^3). For other elp mail me Sincerely Aidin_n7@hotmail.com Thank you for test!! I got AC! 1-use dynamic 2-i got AC with 22lined program and 2array [1..100,1..100] (one integer and one longint)(pascal) 3-answer of this sample is -1 -1 -2 -3 -3 -2 -1 -1 -2 -3 4-its best order is O(n^3). For other elp mail me Sincerely Aidin_n7@hotmail.com Thanks... :) I got AC too... i have O(n^3)solution. but wrong answer on test 7. Can you give me some test cases please? Please, give me some tests! Solution looks like bruteforce with a precalc, not a dynamic programming one. Or precalc counts as DP? Or DP is just a clever bruteforce? Edited by author 25.07.2017 20:10 Are you calculating something like "maximal sum subarray" ? That is where it is DP. If you are doing Kadane algorithm You are doing essentially that thing dp[i] = max(0, dp[i-1] + matrix [i]) answer = max(dp[i]) My solution passes first 4 test cases and shows memory limit exceeded error at 5th test case. I have made a global 4D array 100*100*100*100 which keeps the result of the sum of a rectangle whose top left corner is x1,y1 and bottom right corner is x2,y2, 4d array mat[x1][y1][x2][y2] stores the sum of the numbers corresponding to that rectangle. Now if this big array were a reason behind memory limit exceeded error than it shouldn't have passed even the first test cases because i made global 4d array of maximum size by default. So what can be the reason? #include <iostream> using namespace std; const int M = 107; int mat[M][M][M][M]; int main() { int n; cin >> n; int arr[n][n]; int ans = -1e9; for (int i=0; i<n; i++) for (int j=0; j<n; j++) { cin >> arr[i][j]; mat[i][j][i][j] = arr[i][j]; if (arr[i][j] > ans) ans = arr[i][j]; } for (int size = 2; size<=n*n; size++) { for (int p=1; p<=size and p<=n; p++) { int q = size/p; if (p*q != size) continue; for (int i=0; i<n-p+1; i++) { for (int j=0; j<n-q+1; j++) { int x1 = i, y1 = j; int x2 = i+p-1, y2 = j+q-1; if (x2-x1 > y2-y1) { mat[x1][y1][x2][y2] = mat[x1][y1][x2-1][y2] + mat[x2][y1][x2][y2]; if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2]; } else { mat[x1][y1][x2][y2] = mat[x1][y1][x2][y2-1] + mat[x1][y2][x2][y2]; if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2]; } } } } } cout << ans << endl; } Edited by author 26.06.2017 17:06 Edited by author 26.06.2017 17:06 Edited by author 26.06.2017 17:07 Actually, if you don't access your global allocated memory, that memory don't counts. I have noticed that when watching how my solutions are testing. When there is a global array of big size first few cases are low memory. And last test cases are high memory usage. You can find any simple task were you are to output some string. Allocate a HUGE buffer for that string. Then submit your solution. Then allocate a buffer just enough to hold your string and submit again. And you will see that memory usage is the SAME. I cann't believe it! Dynamika O(n^4). Can you give me some hints about algo O(n^3)? Is it Dynamika too? Thanks a lot! Edited by author 04.06.2006 14:57 So, your solution O(N^4) was accepted? I know O(N^4), and O(N^3) (but it requires O(N^3) memory). I can tell you the last. Sure, please. So, what's the O(n^3) solution ? Hint: Solve problem 1296 first. And use it's solution. Hint: Solve problem 1296 first. And use it's solution. Yeah... That's right. Thanks a lot for the hint.... It worked. My program gets WA #5. Did anybody have the same problem? Program works correctly with all inputs I have found. Edited by author 09.09.2012 13:01 Also accepted O(n^4) in Go 0.312 As task marked easy, it was lazy for me to implement O(n^3) Firstly my solution got TLE#4. Next, I make mew solution with new idea, and got WA#4. Also, my 2nd solution makes mistake in this test: 4 0 -2 -1 0 9 2 -9 -2 -4 1 -1 1 -1 8 10 -2 answer is 18. It can help someone. P.S. forry for bad English. I haven't idea how to approach this test? my code is simple O(n^4),but #9 test doesn' work: for (i=1;i<=n;i++) { for (j=1;j<=n;j++)
s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
} for (i=1;i<=n;i++) for (j=1;j<=n;j++) { for (k=i;k<=n;k++) { for (m=j;m<=n;m++) { sum=s[k][m]-s[i-1][m]-s[k][j-1]+s[i-1][j-1];
if (sum>max1) max1=sum;
} } } I had the same problem. Firstly I used array of short and there was overflow in sum (max possible sum is 127 * 100 * 100 = 1270000 > 32767). Then I changed type to int and got AC :) #include <iostream> using namespace std; int n,A[1002],i,maxi,S[1002],st,dr,rez; int main() { cin>>n; for(i=1;i<=n;i++) cin>>A[i]; S[1]=A[1]; for(i=1;i<=n;i++) if(S[i-1]<=0) S[i]=A[i]; else S[i]=A[i]+S[i-1]; rez=-1000000; for(i=1;i<=n;i++) if(S[i]>rez) rez=S[i]; cout<<rez; return 0; } it's just a joke, isn't it? please help me if you have O(n^2) algorithm for this problem . thanks From my knowledge i know there is possible only O(n^3) code deleted Edited by author 13.09.2007 17:11 Your Solution C++: time = 0.187 Solutin in Pascal (other algorithm): time = 0.031 Pleace, delete your solution code :) There is an O(n^3) way(my solution is that). First you must save the sum of the elements form the first to each of the others in every row. Then for each column I and each column J (J>=I) you sum all the rows (using the first step). On each step you check if the sum now is better than the max.If the sum gets below zero you make it zero and continue. Kiril Kafadarov 1146 C++ Accepted 0.015 197 KB Gimme some tests, please :) All tests that I found my program passed right, I can't understand my mistake. Now I have WA4 :) Edited by author 08.07.2012 10:07 can anybody explain me an idea of N^2? I think there is no O(N^2) solution, but who knows? Maybe, I'm not right. Now my AC solution is nearly O(N^3) (something like N^3-N^4 operation) - it's enough. |
|