OJ Board

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!!

You are wrong. Think again:)

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.

AC!!

Thank you andresw1 and rushel!!

Your

%p

is a big hint for me!!

Thank you!!

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

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:

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

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.

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.

It can be solved in O(1)
A solution to the puzzle exists iff s12-s11 = s22-s21 (mod gcd(p11,p12,p21,p22))

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

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

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.

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

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 ?