## 11024 - Circular Lock

Moderator: Board moderators

ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan

### 11024 - Circular Lock

I got WA during the contest...

I think that a lock can be deactivated if and only if
(p11-s11)%p11 + (p22-s22)%p22 = (p12-s12)%p12 + (p21-s21)%p21

am I right?

If not, what's the correct way to solve this problem?

Thank you very much!!
andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm
You are wrong. Think again:)
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
I am also having a WA

my logic:

if s11%p==s12%p==s21%p==s22%p then "Yes"
else "No"

Is my approach al right.
ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan
AC!!

Thank you andresw1 and rushel!!

Your
%p
is a big hint for me!!

Thank you!!
cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm
rushel , you are underestimating the problem , it's not that easy.
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
First I misunderstood the problem and now I tried a lot but i couldnt figure out any solution. Pls someone will be kind enough to give me a hint:
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Make a system of linear equations modulo p, and solve it by hand.
Then you'll find a criterion, when a solution exists.
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
In the contest I did a silly mistake and got WA. But now I fixed my code and get it Accepted.

Suppose S11 is unchanged, and x press(es) to S12, S22 and y press(es) to S21,S22.

Then there would be a solution if

S11 % P = (S12 + x) % P = (S21 + y) % P = (S22 + x + y) % P

Now the rest is yours.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
it can be solved in O(p) . Change everthing to %p as suggested in description.Just try to figure out how many times you should press every one of the four buttons. During contest i got ac an O(p^2) solution.
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
It can be solved in O(1)
A solution to the puzzle exists iff s12-s11 = s22-s21 (mod gcd(p11,p12,p21,p22))
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
How do you do gcd(p11,p12,p21,p22) in O(1)?
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Ah, I was assuming an O(1) gcd operation.
Bit complexity would be of course higher.
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
Thank u guys. I found the System of linear equation modulo p after lot of hard work. i dont know why it takes too much time to analyze. Any way
Thanks Again.

Really It was a good problem for a programmer like me.
rajkon
New poster
Posts: 5
Joined: Sun Apr 02, 2006 11:59 am
Can somebody post a list of other math problems from uva.es? Thanx
Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm