11297 - Census

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

11297 - Census

Post by Robert Gerbicz » Mon Oct 01, 2007 2:09 am

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?!

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Re: 11297 - Census

Post by lord_burgos » Mon Oct 01, 2007 2:23 am

Robert Gerbicz wrote: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
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Mon Oct 01, 2007 7:40 am

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;
}
Last edited by mmonish on Mon Oct 01, 2007 9:11 pm, edited 1 time in total.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 01, 2007 8:05 am

I don't see why your algorithm should work.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Mon Oct 01, 2007 12:44 pm

>> 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
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Mon Oct 01, 2007 1:47 pm

"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?

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Mon Oct 01, 2007 6:42 pm

mmonish wrote: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
New poster
Posts: 1
Joined: Fri Apr 22, 2005 2:54 pm

Post by anikov » Mon Oct 01, 2007 7:07 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 01, 2007 7:27 pm

anikov wrote: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
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Mon Oct 01, 2007 9:15 pm

>>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
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Mon Oct 01, 2007 10:02 pm

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
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Mon Oct 01, 2007 10:10 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 01, 2007 10:28 pm

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

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Tue Oct 02, 2007 12:01 am

sclo wrote: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
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Post by Lomir » Tue Oct 02, 2007 6:12 am

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.

Post Reply

Return to “Volume 112 (11200-11299)”