Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

Partition based on conditions
Автор olivergrant, история, 8 месяцев назад, По-английски

I have the following question:

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

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

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

Isn't your problem just this?

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

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

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

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

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

      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?

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

        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

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

          How are the edges formed in this graph?

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

            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.

            → Ответить