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
Post
by Ghost77 dimen » Sat Dec 27, 2003 7:32 pm
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
New poster
Posts: 1 Joined: Sun Dec 28, 2003 2:50 am
Location: Ulm Bockighofen, Germany
Post
by SimonGog » Sun Dec 28, 2003 3:00 am
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 » Sun Dec 28, 2003 5:13 am
The input should be a square, doesn't it??
My program is waiting for other lines.
Ghost77 dimen
Learning poster
Posts: 67 Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
Post
by Ghost77 dimen » Sun Dec 28, 2003 5:57 am
Finally, I got accepted.
Thank you.
tep
New poster
Posts: 23 Joined: Fri Jun 13, 2003 6:08 am
Contact:
Post
by tep » Tue Dec 30, 2003 6:35 am
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 .. » Tue Dec 30, 2003 8:02 am
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 » Tue Dec 30, 2003 12:57 pm
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 .. » Tue Dec 30, 2003 1:27 pm
.............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 » Wed Dec 31, 2003 3:51 am
.. 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
..
A great helper
Posts: 454 Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Post
by .. » Wed Dec 31, 2003 6:47 am
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
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 » Wed Dec 31, 2003 8:06 am
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
Experienced poster
Posts: 136 Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Post
by windows2k » Thu Jan 01, 2004 5:45 am
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:
Are they all right?
Ghost77 dimen
Learning poster
Posts: 67 Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
Post
by Ghost77 dimen » Thu Jan 01, 2004 8:02 am
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:
Post
by L I M O N » Sun Jan 04, 2004 9:19 am
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:
Post
by rotoZOOM » Sun Jan 04, 2004 6:32 pm
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.