Please read the new rule regarding the restriction on the use of AI tools. ×

olivergrant's blog

Partition based on conditions
By olivergrant, history, 8 months ago, In English

I have the following question:

Split a set of n elements into 2 sets based on k conditions.

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't your problem just this?

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    It is, but its a simpler and much more common variant., which reduces to bipartite coloring.

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

      Of course, you are right
      It's not the first time when I think about 2-SAT instead of bipartite coloring :)

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

      Thank you, this makes sense after reading about bipartite colouring. However, my question is how do I form the graph? Of course I form an edge between X and Y if they do not want to be with each other because then we can colour them differently. However, what about if we want X and Y to be together?

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

        it's like this

        dfs(v, c):
  if color of v is set:
    if color of v != c: impossible := true
    return
  color of v := c
  for to := each neighbor:
    if v and to should be in the same set:
      dfs(to, c)
    else:
      dfs(to, !c)

        Problem using this idea (and a bit more) (i hope i'm not spoiling a really good problem): 1291E

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

          How are the edges formed in this graph?

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

            edges contain both types of conditions. when traversing through conditions of type 2, you change color, but when traversing through type 1, you won't change color.

            → Reply