ayush29azad's blog

1097B — Petr and a Combination Lock
By ayush29azad, history, 3 years ago, In English

How to solve this problem using bitmask or bit manuplation ??

Problem Link :https://codeforces.me/problemset/problem/1097/B Editorial Link :https://codeforces.me/blog/entry/64310

I am not able to understand the editorial which says that clockwise rotation will be done if ith bit is set to 0 and vive versa ?? Can someone explain in detail ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Every rotation can be represented as 0 — clockwise or 1 — counterclockwise. It means that if you have to do N rotations, than you can represent all possible ways of rotations by 2 ^ N bit strings. For example for N = 2 you have 4 states — 00, 01, 10, 11. Than just check each state (iterate throw bit string, if bit is 1 — add angle, else — substract) if angle is divisible by 360, you found solution.

→ Reply