I have the following question:
Split a set of n elements into 2 sets based on k conditions.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | cry | 160 |
2 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | atcoder_official | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | maroonrk | 152 |
10 | Dominater069 | 149 |
I have the following question:
Split a set of n elements into 2 sets based on k conditions.
Name |
---|
Isn't your problem just this?
It is, but its a simpler and much more common variant., which reduces to bipartite coloring.
Of course, you are right
It's not the first time when I think about 2-SAT instead of bipartite coloring :)
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?
it's like this
Problem using this idea (and a bit more) (i hope i'm not spoiling a really good problem): 1291E
How are the edges formed in this graph?
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.