10707 - 2D-Nim

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

Moderator: Board moderators

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

10707 - 2D-Nim

Post by alex[LSD] » Fri Sep 03, 2004 3:07 pm

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! 8-)
The more contests are held, the happier I am.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sat Sep 04, 2004 1:48 pm

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.

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Sat Sep 04, 2004 6:19 pm

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.

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

Post by Yarin » Sat Sep 11, 2004 2:55 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.

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

Post by krijger » Sun Sep 19, 2004 6:29 pm

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

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Mon Sep 20, 2004 4:03 pm

Yep, I already have a variant like that. And it looks pretty good! 8-)
The more contests are held, the happier I am.

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

Post by windows2k » Thu Sep 30, 2004 6:22 am

alex[LSD] wrote:Yep, I already have a variant like that. And it looks pretty good! 8-)
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 :)

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Mon Dec 27, 2004 8:20 pm

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. :roll:

Thanks in advance.

rajsekar_manokaran
New poster
Posts: 9
Joined: Fri Feb 20, 2004 6:48 am
Location: India
Contact:

Wrong Answer with storing as vector<pair< int, int>

Post by rajsekar_manokaran » Thu Jun 02, 2005 8:11 am

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.

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

10707

Post by shanto86 » Tue Aug 08, 2006 5:49 am

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

Post by shanto86 » Tue Aug 08, 2006 6:22 am

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
Self judging is the best judging!

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

Post by sclo » Thu Sep 28, 2006 2:27 am

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.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Oct 10, 2007 11:03 am

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?

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Re:

Post by greve » Mon May 26, 2008 6:56 pm

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/

beginer
New poster
Posts: 2
Joined: Sat Apr 09, 2016 12:34 pm

10707 - 2D-Nim

Post by beginer » Wed Apr 13, 2016 10:19 pm

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

Post Reply

Return to “Volume 107 (10700-10799)”