10707 - 2D-Nim

[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!

[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.

[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++

[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.

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

[alex[LSD]]

Yep, I already have a variant like that. And it looks pretty good!

[windows2k]

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

[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.

[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.

[shanto86]

Can any one please post some I/O?

[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

[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.

[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?

[greve]

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

I just coded it and got AC.

[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