## 11297 - Census

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

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
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

### Re: 11297 - Census

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
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] , mi[SZ] , 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
Contact:
I don't see why your algorithm should work.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
>> 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:
"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
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
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
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
Contact:
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
>>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
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:
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
Contact:
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:
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:
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.