11581 - Grid Successors

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

Moderator: Board moderators

Post Reply
f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

11581 - Grid Successors

Post by f74956227 » Fri Feb 27, 2009 12:00 pm

I think this problem can't be a cycle...but why??? Can someone give me a proof please :D
Last edited by f74956227 on Fri Feb 27, 2009 12:36 pm, edited 1 time in total.
electron

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11581 - Grid Successors

Post by Jan » Fri Feb 27, 2009 12:28 pm

Check the first sample..

Code: Select all

111
100
001
Its f0(g). We can find f1(g) easily.

f1(g) = f( f0(g) )

This way we can construct all.

So,

Code: Select all

f0(g) =
    111
    100
    001

f1(g) =
    001
    100
    110

f2(g) =
    110
    101
    011

f3(g) =
    010
    101
    010

f4(g) =
    000
    000
    000

f5(g) =
    000
    000
    000

...
fI(g) = f4(g). Here 'I' stands for infinity. So, 3 is the highest index for which the result is finite. So, the result is 3. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 11581 - Grid Successors

Post by f74956227 » Sat Feb 28, 2009 1:54 am

Thank you!! I think this problem will always convergence to the zero matrix (3x3) for every grid, but i can't prove this. Actually my AC program shows the
feature.
electron

priorm
New poster
Posts: 4
Joined: Tue Nov 05, 2013 11:28 am

Re: 11581 - Grid Successors

Post by priorm » Tue Nov 05, 2013 11:29 am

Hey all, having trouble getting WA and tried some rudimentary test cases. Formatting looks good. Any hints?

DELETED - missed the new line at the very end =/
Last edited by priorm on Sat Nov 30, 2013 6:55 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11581 - Grid Successors

Post by brianfry713 » Tue Nov 05, 2013 9:26 pm

Use class Main
Check input and AC output for thousands of problems on uDebug!

priorm
New poster
Posts: 4
Joined: Tue Nov 05, 2013 11:28 am

Re: 11581 - Grid Successors

Post by priorm » Sun Nov 24, 2013 6:57 pm

Sorry. Edited my response - (I modify my code to conform to the java submission instructions just prior to submitting)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11581 - Grid Successors

Post by brianfry713 » Tue Nov 26, 2013 11:23 pm

Print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

priorm
New poster
Posts: 4
Joined: Tue Nov 05, 2013 11:28 am

Re: 11581 - Grid Successors

Post by priorm » Sat Nov 30, 2013 6:54 am

ugh, thanks!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11581 - Grid Successors

Post by uDebug » Tue Sep 23, 2014 2:36 pm

Jan,
Thanks for the explanation. That really helped see things in perspective.

Also, I've uploaded input I found useful during testing / debugging on uDebug.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 115 (11500-11599)”