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

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

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
  • Проголосовать: не нравится

»
6 недель назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

very very hard

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

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

→ Ответить
»
6 недель назад, # |
← 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

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

    Oh Ok. I'll check your solution

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

    Thanks! I got the mistake now.

    → Ответить
  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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?

    → Ответить
    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 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)
      → Ответить
    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

→ Ответить