10593 - Kites

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

Moderator: Board moderators

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

10593 - Kites

Post by 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?? 8)

SimonGog
New poster
Posts: 1
Joined: Sun Dec 28, 2003 2:50 am
Location: Ulm Bockighofen, Germany

Post by 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
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen »

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

My program is waiting for other lines. 8)

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen »

Finally, I got accepted.

Thank you.

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:

10593

Post by 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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

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.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:

Post by 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]

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

.............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.....
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k »

.. wrote: 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 :D

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

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 :wink:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:

Post by 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 :cry: ...

please HELP!

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k »

Ghost77 dimen wrote: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
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by 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
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

10593

Post by 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
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Re: What's the algorithm to solved 10593(kites)

Post by rotoZOOM »

L I M O N wrote: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.

Post Reply

Return to “Volume 105 (10500-10599)”