KIMJONGOOF's blog

Help with a 2-SAT problem please?(Resolved)
By KIMJONGOOF, history, 2 months ago, In English

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

My submission -> https://codeforces.net/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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -23 Vote: I do not like it

very very hard

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh Ok. I'll check your solution

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! I got the mistake now.

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 

      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)
      → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      https://cp-algorithms.com/graph/2SAT.html

      This is where I learned 2-SAT. Came across this concept while solving the CSES problem set.

      → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by KIMJONGOOF (previous revision, new revision, compare).

→ Reply