Never give up on ideas before trying
This is the problem from today's round. Problem basically need to remove two nodes from graph and divide it into highest possible number of parts. First idea hit was to virtually remove first node with highest number of connected nodes. Then find second best. Removing them is answer. This failed, because there could be cases where removing random with highest number might not be appropriate(Wrong answer test 2).
Second try: Then I tried checking with removing each node with highest number of connections as first (the best). (Time limit)
Finally, I almost gave up and tried thinking of greedy (if you don't know what it is, it is hard/impossible to prove ideas). Basically I tried to do 2nd try, but checking only 2 as the best(wrong answer test 4, I was a bit happy). Tried 5 and got accepted, I don't know 100% why. But there are some reasons which are intuitive.
Intuition rules😎
That wasn't expected solutions imo.
This is the problem from today's round. Problem basically need to remove two nodes from graph and divide it into highest possible number of parts. First idea hit was to virtually remove first node with highest number of connected nodes. Then find second best. Removing them is answer. This failed, because there could be cases where removing random with highest number might not be appropriate(Wrong answer test 2).
Second try: Then I tried checking with removing each node with highest number of connections as first (the best). (Time limit)
Finally, I almost gave up and tried thinking of greedy (if you don't know what it is, it is hard/impossible to prove ideas). Basically I tried to do 2nd try, but checking only 2 as the best(wrong answer test 4, I was a bit happy). Tried 5 and got accepted, I don't know 100% why. But there are some reasons which are intuitive.
Intuition rules😎
That wasn't expected solutions imo.