shahianshu's blog

Paradox spoj — WA
By shahianshu, history, 6 years ago, In English

i am trying to solve paradox using graph coloring but i am getting wrong anwser , i have tried all the test case which are there on spojtoolkit and my code is giving correct answer for everyone of them ( it gave wrong answer for only those testcases in which x > n , which is not possible due to given constraints in the question although i have tried doing that also but still it is giving wrong answer)

MY APPROACH :- the statement which says y : x true , we can group x and y into one group as we know that both of them can either be true or be false , similarly statement wich says y : x false , x and y belong to different group because if x is true , y is false and vice-versa . We have a paradox if two elements of the same group are said to be of the different groups i,e if one statement says y : x true and other says x ; y false , otherwise we don't have a paradox

problem : — PARADOX

My Solution : solution

I will be very thankful for the help and thanks in advance.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This case is "NOT PARADOX"

4
3 false
4 false
4 false
3 false
0

but your programs says that it is "PARADOX". One possibility is that (1+4) are true and (2+3) are false.

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

    thanks buddy , i understood my mistake but could you suggest me a way on how to solve this problem by coloring i tried on my own for solving the problem using coloring , keeping your test case in mind but couldn't come up with an answer and also could you please tell me the thought process by which you came up with that test case , so that i also do the same next time and thanks again.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      you need to do dfs not only for same color but also for different color in parallel. So if there is a "false" connection then change color and if there is a "true" connection take same color.

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

        correct me if i am wrong , but you are telling me to do the dfs once for true and then if i encounter color[a] == color[b] then i should again do dfs by taking false and then also if i encounter color[a] == color[b] , then i should print paradox otherwise not.

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

          No. For each statement generate an edge and store it in an adjacency list (as you did for true statements — but now also for false statements). if statement is true then add in both adjacency lists an edge to the other statement with an additional attribute same_color=true. if statement is false then add in both adjacency lists an edge to the other statement with same_color = false.

          Then do a dfs for each unvisited node. For each edge of this node do a recursive call. if same_color of the edge is true then do a recursive call with the same color of the current dfs and if same_color is wrong then do a recursive call with 1-"current color".

          → Reply