11024 - Circular Lock

ferng1021 · Post by **ferng1021** » Sun Apr 02, 2006 5:23 am

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 · Post by **andresw1** » Sun Apr 02, 2006 10:19 am

You are wrong. Think again:)

rushel · Post by **rushel** » Sun Apr 02, 2006 11:16 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 · Post by **ferng1021** » Sun Apr 02, 2006 12:51 pm

AC!!

Thank you andresw1 and rushel!!

Your

%p

is a big hint for me!!

Thank you!!

cypressx · Post by **cypressx** » Sun Apr 02, 2006 2:19 pm

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

rushel · Post by **rushel** » Sun Apr 02, 2006 9:08 pm

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 · Post by mf » Sun Apr 02, 2006 9:20 pm

Make a system of linear equations modulo p, and solve it by hand.
Then you'll find a criterion, when a solution exists.

Jan · Post by **Jan** » Mon Apr 03, 2006 12:31 am

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.

trulo17 · Post by **trulo17** » Mon Apr 03, 2006 12:41 am

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 · Post by mf » Mon Apr 03, 2006 1:23 am

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 · Post by **Krzysztof Duleba** » Mon Apr 03, 2006 1:52 am

How do you do gcd(p11,p12,p21,p22) in O(1)?

mf · Post by mf » Mon Apr 03, 2006 2:24 am

Ah, I was assuming an O(1) gcd operation.
Bit complexity would be of course higher.

rushel · Post by **rushel** » Mon Apr 03, 2006 8:38 pm

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 · Post by **rajkon** » Thu Apr 06, 2006 8:08 pm

Can somebody post a list of other math problems from uva.es? Thanx

Raiyan Kamal · Post by **Raiyan Kamal** » Fri Apr 07, 2006 8:28 am

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 ?