11297 - Census

[Robert Gerbicz]

From the problem statement:

Code: Select all

In the first line you will find N (0 <= N <= 500)

But in the first line of sample input I see

Code: Select all

5 5

Assuming that the problem desription is good I've got RTE for my program. It indicates that the description is wrong. It's really confusing, what is the second number in the first line? Is it the duplication of the N value, or what?!

[lord_burgos]

From the problem statement:

Code: Select all

In the first line you will find N (0 <= N <= 500)

But in the first line of sample input I see

Code: Select all

5 5

Assuming that the problem desription is good I've got RTE for my program. It indicates that the description is wrong. It's really confusing, what is the second number in the first line? Is it the duplication of the N value, or what?!

yes this is a mistake, is n and m, but because is just a test case, n is equal to m, mmm, I need to change this part , thanks

[mmonish]

I got too many WA in this prob. here i post my code. Anyone please help me..

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>

#define SZ 505
#define INF (1 << 30)

int mat[SZ][SZ] , n , ma[SZ][30] , mi[SZ][30] , m;

int main()
{
	//freopen("c.in" , "rt" , stdin);
	int i , j , k , l , q , a , b , c ,d;
	char ch;
	scanf("%d%d" , &n , &m);
	for(i = 1;i<=n;i++)
		for(j = 1;j<=25;j++)
		{
			ma[i][j] = 0;
			mi[i][j] = INF;
		}
	k = (int) sqrt(m);
	for(i = 1;i<=n;i++)
	{
		for(j = 1;j<=m;j++)
		{
			scanf("%d" , &mat[i][j]);
			j % k == 0 ? l = j/k : l = (j/k)+1;
			if(mat[i][j] > ma[i][l]) ma[i][l] = mat[i][j];
			if(mat[i][j] < mi[i][l]) mi[i][l] = mat[i][j];
		}
	}
	scanf("%d" , &q);
	while(q--)
	{
		scanf(" %c" , &ch);
		if(ch == 'c')
		{
			scanf("%d%d%d" , &a , &b , &c);
			b % k == 0 ? l = b/k : l = (b/k)+1;
			mat[a][b] = c;
			if(ma[a][l] < c) ma[a][l] = c;
			if(mi[a][l] > c) mi[a][l] = c;
		}
		else
		{
			scanf("%d%d%d%d" , &a , &b , &c , &d);
			c > n ? c = n : c = c;
			d > m ? d = m : d = d;
			int mir , mar;
			mar = 0;mir = INF;
			for(i = a;i<=c;i++)
			{
				l = b;
				while(l <= d)
				{
					if((l-1) % k == 0) break;
					if(mar < mat[i][l])
						mar = mat[i][l];
					if(mir > mat[i][l])
						mir = mat[i][l];
					l++;
				}
				l = (l/k)+1;
				for( ;l<= d/k;l++)
				{
					if(mar < ma[i][l])
						mar = ma[i][l];
					if(mir > mi[i][l])
						mir = mi[i][l];
				}
				l = (d/k)*k+1;
				for(;l<=d;l++)
				{
					if(mar < mat[i][l])
						mar = mat[i][l];
					if(mir > mat[i][l])
						mir = mat[i][l];
				}
			}
			printf("%d %d\n" , mar , mir);
		}
	}
	return 0;
}

[sclo]

I don't see why your algorithm should work.

[mmonish]

>> sclo

Will u tell me why my algorithm shouldn't work. I think if i understand the problem then my algo gives correct ans.

[Lomir]

"x1 y1 x2 y2" which represent the coordinates of the upper left and lower right of where you must calculate the maximum and minimum change in population.
"x y v" indicating a change of the population of city C [x, y] by value v.

q 1 1 2 3
c 2 3 10
q 1 1 5 5
q 1 2 2 2

Which input format is right? There are or not characters 'c' and 'q'?

And why the answer to the second query in sample test is 10?
We increace value in row 2 column 3 by 10 and initial value was 2.
So the answer must be 12?

P.S. Could somebody correct all problem defenitions from yesterday contest?

[lord_burgos]

I got too many WA in this prob. here i post my code. Anyone please help me..

// CODE

Input:

Code: Select all

10 10
3 9 380 28471 29141 12245 0 5957 57 8535
5 9582 224 8649 2763 7 63 42 4462 0
11616 0 4647 4099 5 11 30991 0 32585 1
7 0 16 0 363 0 0 10947 1 31210
0 13 48 5997 8734 325 424 0 5949 18088
146 0 7 664 9175 22785 2055 4433 5783 586
214 31 363 8852 89 0 1748 9217 14348 21473
177 19922 0 2 973 73 27593 15329 71 7
0 2311 16 481 476 646 5081 80 66 36
234 22716 161 1 467 2594 8256 0 18567 0
10
c 7 4 2671
q 8 1 10 3
q 1 3 3 4
c 9 10 6454
c 10 6 1118
c 2 3 5946
c 8 9 3405
q 2 2 10 8
q 1 1 495 493
q 3 5 10 10

Correct Ouput:

Code: Select all

22716 0
28471 224
30991 0
32585 0
32585 0

[anikov]

This is a very nice problem, but the problem description is one of the worst I have seen.
And this example is VERY stupid, not showing anything useful.

[sclo]

This is a very nice problem, but the problem description is one of the worst I have seen.
And this example is VERY stupid, not showing anything useful.

I agree. Actually for many problems for this contest, the example is too trivial and it doesn't really help much. And I find some of the problem statement simply doesn't make sense.

[mmonish]

>>lord_burgos

Thanks. I do some simple mistake in my implementation.Now i post my modified code which gives the correct ans. But i am getting WA in 1.4 sec.

I tried to figure out my mistake but couldn't. help plz..

[rushel]

in tht above test case the dimension of square is 10 * 10
but in the following query x2 = 495 and y2=493
q 1 1 495 493

so there can be test casese like this?

[Lomir]

I used N Interval Trees (a tree for each row) to get rather slow AC.
This is really nice problem, expcept for its statement.

[sclo]

2d interval tree works here.
Each query and update is O((log n)^2)

[Robert Gerbicz]

2d interval tree works here.
Each query and update is O((log n)^2)

There is a method using:
O(log(n)) time for 'c' query
O(n*log(n)) time for 'q' query

This is better if there are much more 'c' queries than 'q' queries.

[Lomir]

O(log(n)) time for 'c' query
O(n*log(n)) time for 'q' query

My n intervals work like this.
I think c is less then q, cause got AC only in more then 6sec.

2d interval tree works here.
Each query and update is O((log n)^2)

I know, however i would code it whole night It's enoght for me to have n interval trees, if they pass TL.