UVA – 983 – Localized Summing for Blurring

  • Problem Statement : http://uva.onlinejudge.org/external/9/983.html
  • Type : Dynamic, Maximum Sum
  • Level : 6  – Hard 
  • Description : you can solve it in N^3 using prefix sum array but it will get time limit even with efficient optimizations. to get it in N^2. use another prefix sum array each cell contains the sum of the upper corner  large square. and then use some calculations to generate back the sum of the selected square. you have to calculate the beginning and the end of each square, check out the code below.
  • Gochas
    • The answer will fit only in a 64 bit integer so that’s why you are getting Wrong Answer.
    • The input is reversed from bottom left to upper right corner and the output is like that as well
    • iostream , cin and cout will pass but at 2.9 seconds on the limit so use cstdio’s printf and scanf.
#include <cstdio>
using namespace std;
#define FOR(ii, i0, in) for((ii)=(i0); (ii)<(in); (ii)++)
#define FOR2d(ii, jj, i0, j0, in, jn) FOR(ii, i0, in) FOR(jj, j0, jn)
long int a[1000][1000], r[1000][1000];
int main() {
	register int N, M, i, j, t = 0;
	while (scanf("%d %d", &N, &M) == 2) {
		if (t++) printf("\n");
		long int K = N - M + 1, r[K][K], sum = 0;
		FOR2d(i, j, 0, 0, N, N) scanf("%ld", &a[N - i - 1][j]);
		FOR2d(i, j, 0, 0, N, N){
			if (i) a[i][j] += a[i - 1][j];
			if (j) a[i][j] += a[i][j - 1];
			if (i && j) a[i][j] -= a[i - 1][j - 1];
		}
		FOR2d(i, j, 0, 0, K, K){
			r[i][j] = a[i + M - 1][j + M - 1];
			if (i)	r[i][j] -= a[i - 1][j + M - 1];
			if (j)	r[i][j] -= a[i + M - 1][j - 1];
			if (i && j)	r[i][j] += a[i - 1][j - 1];
		}
		FOR2d(i, j, 0, 0, K, K){
			printf("%ld\n", r[K - i - 1][j]);
			sum += r[i][j];
		}
		printf("%ld\n", sum);
	}
	return 0;
}

This was my first Level 6 Problem 🙂 and my first time to be mentioned in the top 20 Submissions XD

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: