10593 - Kites

[Ghost77 dimen]

5
..x..
.xxx.
xxxxx
.xxx.
..x..

11

4
xxxx
xxxx
xxxx
xxxx

18

5
xxxxx
xxx..
.xxx.
..xxx
xxxxx

9

6
xxxxxx
.xxxxx
xxxxx.
.xxxxx
xxxxx.
.xxxxx

41

Above is my answer.

Anything wrong??

[SimonGog]

Your output is correct.
Another input and output:

30
.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x
xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.
.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x
.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x
xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.
.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x
.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x
xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.
.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x
.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x
xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.xxx.
.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x.x

312

[Ghost77 dimen]

The input should be a square, doesn't it??

My program is waiting for other lines.

[Ghost77 dimen]

Finally, I got accepted.

Thank you.

[tep]

Any idea how to overcome this probs? I use naive brute force O(n^3) for checking the square and O(n^4) for checking the kite and got TLE.

[..]

If you know that the maximum square with top left corner (i, j) has width w,
then the maximum square with top left corner (i, j+1) has width least w-1.
This can help you to decrease the runtime. Similar idea (but need some modification) can be used on kite.

[tep]

I think I have done it by using this loop. I count the square with the area. For the kite, first I check the area, if match then do the grid by grid check.
But I still got TLE.

Any other idea ?

[cpp]for (size=2; size<=nsize; size++)
for (j=1; j<=nsize - size + 1; j++)
for (i=1; i<=nsize - size + 1; i++)[/cpp]

My full code :

[cpp]// Problem : Kites
// UVA id : E
// Lang. : C++
// Author : Stephanus Indra
// Date : 20 December 2003

#include <iostream>

#define MAX_SIZE 501

using namespace std;

char map[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
int nsize;

int check(int size,int y,int x)
{
int half = (size >> 1) + 1;
int i,j,start,end;
int maxx = x + size - 1;

start = end = y + half - 1;
for (i=0; i<half; i++)
{
for (j=start; j<=end; j++)
if (map[j][x+i] != 'x' || map[j][maxx-i] != 'x')
return 0;
start--;
end++;
}
return 1;
}

int main()
{
int i,j,k;
int size,area;
int nkites,square;

while (cin >> nsize)
{
// input
for (j=1; j<=nsize; j++)
for (i=1; i<=nsize; i++)
{
cin >> map[j];
if (map[j] == 'x')
dp[j] = 1 + dp[j-1] + dp[j][i-1] - dp[j-1][i-1];
else
dp[j] = 0 + dp[j-1] + dp[j][i-1] - dp[j-1][i-1];
}

nkites = 0;
for (size=2; size<=nsize; size++)
for (j=1; j<=nsize - size + 1; j++)
for (i=1; i<=nsize - size + 1; i++)
{
area = dp[j+size-1][i+size-1] - dp[j+size-1][i-1] - dp[j-1][i+size-1] + dp[j-1][i-1];
square = size * size;
if (area == square)
nkites++;
if (size & 1) // odd
{
k = (size + 1) >> 1;
if (area >= (square - (k*k - k) * 2))
nkites += check(size,j,i);
}
}
cout << nkites << endl;
}

return 0;
}[/cpp]

[..]

.............Your code need many many optimization to pass the time limit.

For example,
If you know that there is no sqaure of size n with matrix[j] as top left corner, of course there won't be sqaure of size(n+1) with matrix[j] as top left corner. But your code still check for that.

Also, you should optimize the checking on diamond bu using some dynamic programming technique. Your check() function is doing some same jobs for many many times. For example: check(size,j,i) and check(size+1, j,i). You should cache the result.....

[windows2k]

Also, you should optimize the checking on diamond bu using some dynamic programming technique.

Hello, Mr. ..
I don't know how to calc the diamond precisely, could you give me some hints , thx

[..]

I define downward[j] like this:

Code: Select all

....x....     <---the x is at matrix[i][j]
...xxx...
..xxxxx..
.xxx.xxx.
xxxxxxxxx

I will store downward[j] as 3 to represent that the maximum height of triangle with matrix[j] as the top corner is 3.

Similarly, define upward[j]:

Code: Select all

.x.xxx.
..xxx..
...x...     <---the x is at matrix[i][j]

upward[j] is 2.

Once you know the upward and downward for all i, j.
You can determine if there is a diamond with matrix[j] as top corner and height 2k+1 in O(1), just check if downward[j] >= k & upward[i+2*k][j] >= k.

Of course it still needs some small trick to compute upward and downward quickly

[tep]

before preceeding to counting the diamond shape..
I rewrite my code and write only the code for checking the square shape only.

I have used the area and matrix[j] (described above to prevent double checking) to compute the square shape only! But I still got TLE..
confused ...

please HELP!

[windows2k]

Finally, I got accepted.

Thank you.

Hello, Ghost 77 dimen, I tried to solve the problem , but get WA all the time, Would you give me some tricky input/output?
Here is my input

Code: Select all

5
..xx.
xx.xx
.xxx.
xx...
.x.xx
7
.x.x.xx
xx...xx
xx...x.
x.x..xx
.xx.x.x
.x.xx..
x.x.xx.
3
.x.
.x.
xxx
1
.
8
.x..xx..
xxx.xx.x
x...xxx.
...xxx..
x..x....
x..xx..x
.xxxxxx.
...xx..x
9
.....x..x
.xxx.x...
xxxxxx...
xx.xxx..x
x.xxx..xx
x.xx.x..x
.x...xxx.
.xxx.x..x
xxxx..xx.
9
..x.x.xxx
x...x...x
xxxx..xx.
...xx....
..xx.x...
xx..xx.xx
x.xx..xx.
.x.x....x
.x.xxxx.x
5
.xx.x
.xx.x
x.xx.
.xx..
.x.x.
3
.x.
xxx
.xx
3
.xx
...
x.x

My output:

Code: Select all

0
2
0
0
8
13
0
1
2
0

Are they all right?

[Ghost77 dimen]

To windows 2k :

Your output is right.

Try more samples.

5
x..xx
xxxxx
xxx..
xx.xx
xx.xx
10
x..xxxxxxx
.x.x.xxx.x
xxxxx..x.x
xxx.x.xx..
xxx.x.x.xx
xxxx..xx.x
x.xxxxxxxx
xxx..xxxxx
xxx.x..xx.
.xx.xxxxx.
15
xxxx..x.xxx.x.x
xx.xx..x..xxx.x
x..x.x.x.xx.xxx
.x.xxxxxx.xx..x
xxxxxx.xx.xxx.x
.x.x.....xxx...
x.xxxx.x..x.xxx
.xxxxxx.x...xxx
xxx.xx.x..xxxxx
xxxxxxxx.x...xx
xx..xxx.xx.xxx.
.xx.x.xx..x.x..
xxx.xxxxxx.xxxx
x.xxxxxxxx..xxx
..xxxx..xxx..xx
20
..xxxxxxx.xx....xx.x
xx.xx.x.xx.xxx..xxxx
xxx..xx.x.xxxxxxx.xx
.xx...xxx.xx.xxxxx.x
xxxx.xx.xx..xxx.xxxx
.xx.x.xxxx...x.x.xxx
xx..xxxxxxxxx...xxxx
x.x.xxxxx.xx.x.xxx.x
.xx..x.xxxxxxxxxxxx.
xxx..x.x.x.x.x.xx.xx
..xxxx.xxxxx..xxxxxx
xx.xxxxx.x.x.xx.xx..
xxxxxxxx.xxxxxx..xxx
x.xx..xx.xx.xxxxxxxx
xxx.xx.x.xxxxxxxx.x.
xxxxxx.xx.x.xx...xxx
xxx.xx.xxxxxxx.xxxxx
.x.x.x.xxx....xxxxxx
xxx..xxx.xxxxx.xxx.x
x.xxxxx.xxxxxxxx.xxx
25
.xx..xx......x...xx.x.xx.
....xxxxxxx.x.x.x.xxxxxx.
..xxx.x....xxx..xxxx..xx.
xxx..x..xxxxxx..xxxx.xxx.
.xx.xxxx..xxxxx.xx.xxxxx.
..xxx.xxx.x..xx.x.x.xx.xx
.xxxxxx.xxxxxx..xx.x.x.x.
xxx.xx.x....x..xxxxxxxx.x
.......xxx...xxx.xxx.x.xx
...xx.xx.xxx.xx..x.xxxxx.
.x.xx.x.xxxx.xx.x.xxxxxxx
.x.xx.xxxx.xxxxxxxx.xxx.x
xxx...xx.xxxxxx.x.x.xx.x.
...xxxx.xx....x.xx..xxxxx
x.......x..xxxxxx.xxxx.xx
xxxxxxx..xxxx..xxxxxx.x.x
xxxx...x.x..x.xxx.x.xxx.x
xx.xx...xxx.xx....xxx.xx.
xx.xx.xxxx.xx.x.x..x.xxxx
x.x.......xxxx.xxx.x.x.xx
.xxxx.xx.xxxxxx.xx.x..x.x
x.xxxxxxxx.x.x.xxxxxx.x.x
.x.x.xxxxxx.x....x...xx.x
xxxx.xxx.x.xxx.x..x..xx.x
xxxxxx.....x..xxxxx..x.xx
30
.x...xxxx.xx.xxx.x....x.xx.xxx
.x..xxx...xxxxx.xxxxxxx.xxxxxx
xx.xxxxxxxxxxx.xx..xxxx.x..xx.
..xxxxxxxxxxx.x.x.x.x..xxxxx.x
..xxxx.x...x.xxxxxxx.....x.xxx
x.....x..xxx...x..xxx...x.xx..
xx.xx.xx.x..x..x.xx..x.x.x.xx.
xx.x.xx.x...x.xxx...xxxx.xxxxx
x.xxxxx.x.xx.xxx.xxxxxxxxxxx..
xxxxxxxx..x...x...xxxxxxxxxx..
x...x..x.x.xx.xxxx....xxxxxx.x
....x.x..xxx..xxx..x.x.x..x.xx
xxxxx.xxxx...xx.x..x..x.x.xx..
xxx.xxxxxx.xx.x.xxx.xxxxxxx..x
.xxx.xx.xxx.xx..x.xxxx.xxx...x
.x.xxxxxx.x..xx.xx..xx.xxxxxxx
x.xxxx.xxxx.x.xx.xxxx.xx.xx.xx
xx.x.x..x.x..xx.xxxxxx.xxxxx.x
.xx.xx.x.xxx......x..xx.x.x.x.
..x.xx.xx..xxxx.xxx..xxxx.xx.x
..x.xx.xx.xx.x.xx.xx.x.xxxx.xx
x.xx.xxxxxxxxxx.x.xxx.x.xxxxxx
..xxxxx.x.xxxx..xxxxxxx.xx.xxx
.x.xxxx.x.xxx.....xxxx.xxx.x..
.x.x.xxxx.x..xxx..xxxxx.xxxxxx
...xxxxxx...x..x..xx.xxxx..xxx
xxx..xxxxx.xx...xxxx..xx.x..xx
x.xx.x.xx..xxxx.xx.xxxxxxxx.x.
.xx.xx...x.x...x.xxxx.xx.xxxxx
xx...x.xxxx..x..xxx...x.xx.xxx

Output:

7
30
60
135
132
244

[L I M O N]

hi everybody,
pls help me to solve problem 10593(kites). I cann't find any algorithm.
pls help me who got accepted.

Thanks..
Limon

[rotoZOOM]

hi everybody,
pls help me to solve problem 10593(kites). I cann't find any algorithm.
pls help me who got accepted.

Thanks..
Limon

I solved it by DP.
Firstly, find number of square kites.
Secondly, find number of rhombus kites.