11024 - Circular Lock

All about problems in Volume 110. 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
ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan

11024 - Circular Lock

Post by ferng1021 »

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

Post by andresw1 »

You are wrong. Think again:)

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel »

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

Post by ferng1021 »

AC!! :D

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

Post by cypressx »

rushel , you are underestimating the problem , it's not that easy.

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel »

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:

Post by mf »

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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. :wink:

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by trulo17 »

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:

Post by mf »

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:

Post by Krzysztof Duleba »

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:

Post by mf »

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

Post by rushel »

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

Post by rajkon »

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
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

I don't know how to derive the system of linear equation everyone is talking about, I have solved it using GCD and subtraction only. After subtracting couple of numers, i chek if the lock is opened, i.e. 0,0,0,0 configuration or not. Can anyone explain the relation between these two methods ?

Post Reply

Return to “Volume 110 (11000-11099)”