Page 1 of 2
10707 - 2D-Nim
Posted: Fri Sep 03, 2004 3:07 pm
by alex[LSD]
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!
Posted: Sat Sep 04, 2004 1:48 pm
by Per
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 hash-value of the component, if one can find a good hash-function.
Posted: Sat Sep 04, 2004 6:19 pm
by alex[LSD]
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 built-in 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++
Posted: Sat Sep 11, 2004 2:55 am
by Yarin
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.
Posted: Sun Sep 19, 2004 6:29 pm
by krijger
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");
Posted: Mon Sep 20, 2004 4:03 pm
by alex[LSD]
Yep, I already have a variant like that. And it looks pretty good!
Posted: Thu Sep 30, 2004 6:22 am
by windows2k
alex[LSD] wrote:Yep, I already have a variant like that. And it looks pretty good!
Hello, I tried to solve the problem.
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
Posted: Mon Dec 27, 2004 8:20 pm
by Dreamer#1
My solution gets AC in another site (can't remember exactly which one, most probably at timus or zju) but here I get WA!!!
Can someone give me some test cases? I feel confused.
Thanks in advance.
Wrong Answer with storing as vector<pair< int, int>
Posted: Thu Jun 02, 2005 8:11 am
by rajsekar_manokaran
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.
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(i-minx, j-miny));
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(i-minx, maxy-j));
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(maxx-i, j-miny));
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(maxx-i, maxy-j));
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(j-miny, i-minx));
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(maxy-j, i-minx));
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(j-miny, maxx-i));
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(maxy-j, maxx-i));
sort (ttmp.begin(), ttmp.end());
result = min(result, ttmp);
collection.insert(result);
Thanks in advance.
10707
Posted: Tue Aug 08, 2006 5:49 am
by shanto86
Can any one please post some I/O?
Posted: Tue Aug 08, 2006 6:22 am
by shanto86
sorry for wrong place of posting.
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
Posted: Thu Sep 28, 2006 2:27 am
by sclo
It is just easier to write a rotate function and to write a flip function, instead of worrying about 8 cases, let a loop handle that.
Posted: Wed Oct 10, 2007 11:03 am
by Darko
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:
Code: Select all
***@ ***@
***@**.@ ***@**.@
*@ *@
*@ *@
*@ *@
***@**.@ ***@
**@*.@ ***@**.@
*@ *@
*@ *@
*@ *@
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?
Re:
Posted: Mon May 26, 2008 6:56 pm
by greve
Darko wrote:Can someone check if their AC is still AC on the new server?
I just coded it and got AC.
10707 - 2D-Nim
Posted: Wed Apr 13, 2016 10:19 pm
by beginer
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