ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1060. Flip Game

Come On!!!! 0.02sec 24KB !!!! Incredible (aidin_n7@hotmail.com)
Posted by Locomotive 18 Feb 2003 18:53
Again 0.02 but with O (32) !!! better than ever :P
Posted by Locomotive 18 Feb 2003 20:30
>
Re: Come On!!!! 0.02sec 24KB !!!! Incredible (aidin_n7@hotmail.com)
Posted by Marcin Mika 19 Feb 2003 02:02
I did it in 0.08sec
what other optimizations did you have that i dont have in my code?

[code deleted]

Edited by moderator 19.05.2020 22:17
My OPTIMIZTIONs
Posted by Locomotive 19 Feb 2003 12:38
if you notice that
4 blocks of first row and also first block of second row:
XXXX
X...
....
....

will force other blocks choosing...and these have 32ways only!
after selecting True or False for choose (and reverse) these blocks,
first block of first row will have just one side which never will
change by others:
X***
*OOO
OOOO
OOOO
{O never change side of X}
and all of '*'`s force the blocks under them
such as E forces D
XE**
*DOO
OOOO
OOOO
I mean that if E has same colour as X then D shouldn`t choose to
reverse (because after it side of E will change and it will be agains
the X and never change and....) and so on...
so should calculate just first 5 blocks and it is O(32)!!!

Sincerely
Aidin_n7@hotmail.com
I cannot understand what you have said
Posted by CO2 18 May 2004 18:51
I cannot understand what you have said.
Which 5 blocks do you choose?
Can you explain it to me?
Have you got AC?
Could you public your program?(If you don't want to talk much)(PASCAL will be better)
Thank you very much.
Re: I cannot understand what you have said
Posted by PTD_PDP 19 Sep 2004 16:03
I encode the table to LongInt var (You may use Word if you want)

And then I use BFS, here is my code:

And I got 0.031s

[code deleted]

Edited by moderator 19.05.2020 22:18
Re: Come On!!!! 0.02sec 24KB !!!! Incredible (aidin_n7@hotmail.com)
Posted by Samsonov Alex [SESC USU] 14 Jun 2005 16:15
862298 0.001 sec 34 KB