10707  2DNim
Moderator: Board moderators

 Learning poster
 Posts: 53
 Joined: Sat Jan 24, 2004 9:22 pm
 Location: Tomsk, Siberia, RUSSIA
 Contact:
10707  2DNim
Well I solved it. But I didn't enjoy it at all. My pascal solution is 200+ lines and over 5KB in size. I wan't smaller programs, preferably in Pascal. If your program is AC and under 2KB or so, please leave it here as a private message or send it to caa<commercial_at>academ.tsc.ru
Thanks to everyone who is ready to help a dumb russian programmer!
Thanks to everyone who is ready to help a dumb russian programmer!
The more contests are held, the happier I am.
I can tell you the basic idea of my solution, which is slightly longer than 100 lines (though it could be shorter), and around 2.5 kb, though it's in C++:
For each component (find with dfs or whatever you like), transform it to some canonical form (see below), then sort the components of both boards, then go through them one by one and check that the i:th component of board 1 is the same as the i:th component of board 2. So the time complexity is O(n + c log c), where c <= n is the number of components.
My particular choice of canonical form was the following: try all eight transformations of the component, translate the component so that both min x and min y are zero, and then sort the points of the component (ordering doesn't matter as long as it's a total ordering). Then choose the one which yields the lexicographically smallest representation of the component as the canonical form.
It should also work (and be a lot faster) to just take a hashvalue of the component, if one can find a good hashfunction.
For each component (find with dfs or whatever you like), transform it to some canonical form (see below), then sort the components of both boards, then go through them one by one and check that the i:th component of board 1 is the same as the i:th component of board 2. So the time complexity is O(n + c log c), where c <= n is the number of components.
My particular choice of canonical form was the following: try all eight transformations of the component, translate the component so that both min x and min y are zero, and then sort the points of the component (ordering doesn't matter as long as it's a total ordering). Then choose the one which yields the lexicographically smallest representation of the component as the canonical form.
It should also work (and be a lot faster) to just take a hashvalue of the component, if one can find a good hashfunction.

 Learning poster
 Posts: 53
 Joined: Sat Jan 24, 2004 9:22 pm
 Location: Tomsk, Siberia, RUSSIA
 Contact:
YES! Absolutely the same here. My trouble is mostly about sorting components and the points in them. For this purpose I wrote 2 different sorting function, and I never use nothing but mergesort. I dont know of any good pascal builtin sorting procedures.
Other than that, I also decreased all the coordinates by MinX and MinY. I also used lexicografic sorting. It's just ... my solution is ugly... I ll be glad to have your solution, so I could see how it's done in C++
Other than that, I also decreased all the coordinates by MinX and MinY. I also used lexicografic sorting. It's just ... my solution is ugly... I ll be glad to have your solution, so I could see how it's done in C++
The more contests are held, the happier I am.
One can get a fast solution by hashing the groups (selecting the hash code among the 8 transformations of a group that has the smallest value) and comparing those hashed values.
How to detect collisions? You don't You can always generate several different hash values using different constants; if it always says the boards are same, the likelyhood that they are really different is negligible.
How to detect collisions? You don't You can always generate several different hash values using different constants; if it always says the boards are same, the likelyhood that they are really different is negligible.
I have a short solution in C++ in which i heavily use the STL. I use the following 'tricks':
 I store a group in a vector<pair<int,int> >. This makes normalizing a group very easy. All you have to do is sorting the vector (using a stl function) and then subtract the first element from every point. It also makes comparing which rotated/flipped version is 'better' easy.
 I rotate and flip the groups in a loop. It's something like for(int i=0;i<2;++i) { for(j=0;j<4;++j) { rotate(cur); normalize(cur); if(cur<best) best=cur; } flip(cur); }
 I store the collection of groups in a vector<vector<pair<int,int > > >. All i have to do after making these vectors is sorting both (using stl) and then if(g1==g2) printf("YES\n"); else printf("NO\n");
Hello, I tried to solve the problem.alex[LSD] wrote:Yep, I already have a variant like that. And it looks pretty good!
I found the problem is from ACM Tehran Site .
And I found some input/output on the site.
I have passed all the input/output.
But still get WA.
Could someone give me some critical input/output?
I don't know what's wrong with my code.
Thx

 New poster
 Posts: 9
 Joined: Fri Feb 20, 2004 6:48 am
 Location: India
 Contact:
Wrong Answer with storing as vector<pair< int, int>
To compare two components, I am using something very similar to what Per has done. I perform all the 8 transformations on the matrix and store the coordinates in an array and sort the array. Now, I take the lexicographically least one. I keep getting WA
Could someone see if I am overlooking something and point in out.
Thanks in advance.
Could someone see if I am overlooking something and point in out.
Code: Select all
Piece_Type result, ttmp;
result.clear();
for (int i=minx; i<=maxx; i++)
for (int j=miny; j<=maxy; j++)
if (tmp[i][j])
result.push_back(make_pair(iminx, jminy));
sort (result.begin(), result.end());
ttmp.clear();
for (int i=minx; i<=maxx; i++)
for (int j=maxy; j>=miny; j)
if (tmp[i][j])
ttmp.push_back(make_pair(iminx, maxyj));
sort (ttmp.begin(), ttmp.end());
result = min(result, ttmp);
ttmp.clear();
for (int i=maxx; i>=minx; i)
for (int j=miny; j<=maxy; j++)
if (tmp[i][j])
ttmp.push_back(make_pair(maxxi, jminy));
sort (ttmp.begin(), ttmp.end());
result = min(result, ttmp);
ttmp.clear();
for (int i=maxx; i>=minx; i)
for (int j=maxy; j>=miny; j)
if (tmp[i][j])
ttmp.push_back(make_pair(maxxi, maxyj));
sort (ttmp.begin(), ttmp.end());
result = min(result, ttmp);
ttmp.clear();
for (int i=minx; i<=maxx; i++)
for (int j=miny; j<=maxy; j++)
if (tmp[i][j])
ttmp.push_back(make_pair(jminy, iminx));
sort (ttmp.begin(), ttmp.end());
result = min(result, ttmp);
ttmp.clear();
for (int i=minx; i<=maxx; i++)
for (int j=maxy; j>=miny; j)
if (tmp[i][j])
ttmp.push_back(make_pair(maxyj, iminx));
sort (ttmp.begin(), ttmp.end());
result = min(result, ttmp);
ttmp.clear();
for (int i=maxx; i>=minx; i)
for (int j=miny; j<=maxy; j++)
if (tmp[i][j])
ttmp.push_back(make_pair(jminy, maxxi));
sort (ttmp.begin(), ttmp.end());
result = min(result, ttmp);
ttmp.clear();
for (int i=maxx; i>=minx; i)
for (int j=maxy; j>=miny; j)
if (tmp[i][j])
ttmp.push_back(make_pair(maxyj, maxxi));
sort (ttmp.begin(), ttmp.end());
result = min(result, ttmp);
collection.insert(result);
sorry for wrong place of posting.
BTW i got AC. for others who are getting (or will get) WA for them 2 simple cases:
BTW i got AC. for others who are getting (or will get) WA for them 2 simple cases:
Code: Select all
2
100 100 4
0 0 1 1 1 2 2 1
0 0 0 1 1 0 3 3
7 4 2
0 0 1 0
0 2 0 3
Self judging is the best judging!
Can someone check if their AC is still AC on the new server?
I tried hashing first and then tried building Strings, but I can't get it to pass. I tested it a bit, even assumed that there might be more than 3000 points, but nothing...
Here is how I encode the components in the example cases:
When I sort them, if they match, I print "YES", otherwise I print "NO".
I really don't know what else to do  anyone has a suggestion?
I tried hashing first and then tried building Strings, but I can't get it to pass. I tested it a bit, even assumed that there might be more than 3000 points, but nothing...
Here is how I encode the components in the example cases:
Code: Select all
***@ ***@
***@**.@ ***@**.@
*@ *@
*@ *@
*@ *@
***@**.@ ***@
**@*.@ ***@**.@
*@ *@
*@ *@
*@ *@
I really don't know what else to do  anyone has a suggestion?
Re:
I just coded it and got AC.Darko wrote:Can someone check if their AC is still AC on the new server?
For help with problems, visit http://www.uvatoolkit.com/
10707  2DNim
hi,i was solving this problem,
i used this algorithm ,
find size of all row connected component and column connceted component in both board;
sort them then compare;
please if any can tell me where the wrong since you can only remove connected component by row or column
i used this algorithm ,
find size of all row connected component and column connceted component in both board;
sort them then compare;
please if any can tell me where the wrong since you can only remove connected component by row or column