sithope's blog

468B Two Sets My greedy solution~~
By sithope, 10 years ago, In English

This problem has many ways to solve it,here I want to write something about my greedy solution,thouth I haven't confirm it.

My solution is,firstly,sort the number sequence P，then start from the smallest one (suppose b>a)，if it can be divided into B set with a number which hasn't been used,just put it into B set,otherwise if it can be divided into A set with a number which hasn't been used,just put it into A set,or puts NO and ends the program.

I hope to know someone who has the same idea with me and confirm it and share my solution with you!!!

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

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My solution also used 2 sets:

http://codeforces.net/contest/468/submission/7875703

Firstly, put all elements into set A.

Secondly, put elements which are not suitable in set A into set B.

Finally, erase elements x and b-x in set B (or set A) and do some more simple work.

Hope that help you!

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Your greedy idea is correct and nice. But in CF's tutorial it is mentioned that this problem can be solved by using a 2SAT approach. Does anybody have idea exactly how? Where are the logical variables, where is CNF?

→ Reply