Page 1 of 1
687 - Lattice Practices
Posted: Sun Jan 30, 2005 7:49 pm
by ranjit
687 is a very interesting problem. Though i am not able to either reduce the search space
or even find out all the possible configurations for the sample input.
Can anyone who is interested in this problem help ?
Thanks.
Posted: Fri Mar 04, 2005 1:44 pm
by little joey
I'm getting pretty desparate on this one
Once I get AC, I'll try to give a hint or two, ranjit, but still struggling.
Can someone verify this I/O?
IN:
Code: Select all
00001 00100 00101 00110 01010 01011 01111 10001 10011 11111
00000 00010 00111 01001 01010 01101 01110 01111 10011 11011
00001 00010 00011 00110 00111 01001 01011 10101 10111 11011
00000 00010 00111 01010 01011 01101 01111 10001 10101 10111
00001 00101 00110 00111 01010 01011 01101 01110 01111 10001
00000 00010 00011 00101 00111 01011 01110 10101 10111 11011
00000 00001 00101 00110 01011 01101 01110 10001 11011 11111
00000 00001 00100 00101 01010 01011 01110 01111 10111 11111
00010 00100 00101 00111 01001 01010 01110 01111 10001 11111
00011 00100 00101 00110 00111 01010 01101 10011 10101 10111
00000 00001 00010 00101 01011 01110 01111 10001 11011 11111
00000 00010 00101 01010 01111 10001 10011 10101 10111 11011
00000 00010 00011 00101 00110 00111 01101 01111 10101 11111
00010 00100 00101 01001 01011 01101 01111 10001 10101 11011
00010 00110 00111 01001 01010 01011 01110 10001 10011 10111
00000 00101 00110 00111 01011 01101 01110 10001 10011 11011
00000 00100 00101 00110 01010 01011 01101 01111 10011 11111
00010 00011 00100 00101 01010 01110 10001 10101 11011 11111
00000 00001 00101 00110 01001 01101 01111 10001 10111 11111
00001 00011 00101 01001 01101 01110 01111 10001 10011 10101
END
OUT:
Code: Select all
0
10
28
0
16
3
2
0
3
14
0
4
24
13
22
6
6
0
17
8
I could produce a file with all 25722 possible inputs that contain exactly 25 set bits, but that would be a little too much for this board...
Posted: Fri Mar 04, 2005 2:02 pm
by ..
little joey wrote:
Can someone verify this I/O?
I get the same output. I remember that when I solve this problem, my code can get the sample output even the code misses a kind of reflection. I don't know if this helps.......
Posted: Fri Mar 04, 2005 2:33 pm
by little joey
Thanks for replying.
Maybe I'm trying to be too smart
I'll start all over again; doing it in the simpelest possible way. Hope I don't get TLE...
Posted: Fri Mar 04, 2005 2:39 pm
by ranjit
can you tell me the order of your algorithm?
Posted: Fri Mar 04, 2005 2:52 pm
by ..
Just exhaustive search with some optimization. In general, given any configuartion I will try to reflect/roatate to a specific form. And I will only search for these specific form.....
Posted: Mon Mar 07, 2005 11:40 am
by little joey
OK, I got it
As I promised ranjit a hint or two:
- The order in which we try to place the blocks has a great effect on the number of iterations we have to perform, so we look for an order that limits the number of possiblities as early as possible. I used the "weaving order": first row 1, than column 1, then row 2, then column 2, etc. Already in the second level of iteration (column 1) the number of possibilities is reduced, and only few iterations reach level 6 (column 3).
- The number of possible solutions that result from the iterational stage is surprizingly small (for me it was), so choose a representation that makes the iterations as fast as possible, even if it means that the symmetry checking will be more elaborate than necessary.
Hope it helps.
Posted: Sat Jul 14, 2007 2:17 pm
by rio
Getting many WA...
My approach is:
Count the number of possible configurations without considering the mirrors and rotates, and divide the number with 8.
My code outputs correct with little joey's test cases.
I can't find any counterexample.
Is this a problem with the code ? or am I missing something ?
Thanks in advance.
----
Rio
Re: 687 - Lattice Practices
Posted: Tue Jan 08, 2013 9:26 am
by brianfry713
I was getting WA with different versions of my code that used division by 4 or 8 or 16 or 64 after counting solutions (they matched the I/O given in this thread). My AC code only counts unique solutions and runs in 0.824 seconds. I keep a set of all solutions found so far and all combinations of the rotations (0, 90, 180, and 270 degrees), mirrors (horizontal, vertical, and both diagonals), and the inversion. I placed the blocks in the order little joey described.