Блог пользователя AARYABHATTA_THE_GREAT

Help with a 2-SAT problem please?(Resolved)
Автор AARYABHATTA_THE_GREAT, история, 18 месяцев назад, По-английски

Problem Link -> https://mirror.codeforces.com/contest/776/problem/D

My submission -> https://mirror.codeforces.com/contest/776/submission/285238557

Its pretty obvious from my code what i am trying to do. My Question is that is the logic correct? Where am I going wrong?

I just take cases of whether the door is locked or not and accordingly I build the adj list for the corresponding switch combinations.

*Edit -> Resolved now.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
18 месяцев назад, скрыть # |
 
Проголосовать: нравится -23 Проголосовать: не нравится

very very hard

→ Ответить
»
18 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

First thing , dont ever put the soln idea or hint in the title As here "2-SAT" either put it in spoiler

→ Ответить
»
18 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I just submitted with 2-sat and it got accepted , probably you not making the graph correctly refer to my solution for checking the edges

→ Ответить
  • »
    »
    18 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    bro what is the full form of 2-sat, this seems like a completely new topic to me, is there any resource where I can learn it from?

    → Ответить
    • »
      »
      »
      18 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится 

      Ohk, i don't think you will able to understand it completely, possibly because you seem to not reached enough level to solve this.

Let me give you an idea what is 2 sat:

 assume some boolean variables  x1 x2 ... xk
    func :  (kx | ky) & (kx2 | ky2) & ...   
   
    ki : be any value of the variables

  We need to find if there is some assignment of these boolean variables such that the function evaluates to true

For more:  cses programmer handbook  (google it, you will find the book)
      → Ответить