10707 - 2-D Nim

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

Moderator: Board moderators

10707 - 2-D Nim

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!
The more contests are held, the happier I am.
alex[LSD]
Learning poster

Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA

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.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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++
The more contests are held, the happier I am.
alex[LSD]
Learning poster

Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA

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.
Yarin
Problemsetter

Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume

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");
krijger
New poster

Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Yep, I already have a variant like that. And it looks pretty good!
The more contests are held, the happier I am.
alex[LSD]
Learning poster

Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA

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
windows2k
Experienced poster

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

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.

Dreamer#1
Learning poster

Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

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.

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);`

rajsekar_manokaran
New poster

Posts: 9
Joined: Fri Feb 20, 2004 6:48 am
Location: India

10707

Can any one please post some I/O?
Self judging is the best judging!
shanto86
Experienced poster

Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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
`2100 100 40 0 1 1 1 2 2 10 0 0 1 1 0 3 37 4 20 0 1 00 2 0 3`
Self judging is the best judging!
shanto86
Experienced poster

Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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.
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada

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?
Darko
Guru

Posts: 572
Joined: Fri Nov 11, 2005 9:34 am

Re:

Darko wrote:Can someone check if their AC is still AC on the new server?

I just coded it and got AC.
For help with problems, visit http://www.uvatoolkit.com/
greve
New poster

Posts: 27
Joined: Tue May 29, 2007 8:52 pm