Competitive Programming Editorials

Problem Link   In this problem, we must divide a set of numbers into two sets such that if number x goes into set A, then the number A – x must also be put into set a and similarly, if number x is put into set b, then the number b – x must also be put into set b. If we had to actually go about assigning numbers to either set A or set b and then checking if the conditions above have been met, it would take way too long. This is because for each number we have two choices: put it in set a or put it in set b. This yields a time complexity of O(2n) which easily TLEs with n <= 1e5. There are some numbers that can go in either set if both the numbers A – x and B – x exist. There are also some numbers that can only be placed in set A since the number A – x exists in the array but not B – x and the same goes for numbers that can only be placed in only set B. there are also number that can’t be put in set A or B since neither of the numbers A – x and B – x exist. In this case, the numb...

  Problem Link Problem Summary A tree with N nodes is provided, where all the nodes are initially healthy. In the end, all nodes must be infected. There are 2 ways to infect a node: inject it with the infection, or let the infection spread. The infection can only spread from one node to another if they have the same parent node. In one second, the infection spreads to all possible nodes, and then one node is injected. Find the minimum number of seconds required for all nodes to be infected. Algorithm Used Graph Theory, Greedy, Simulation Editorial If  node is injected, then the infection can only spread to nodes within it's group. If only one node in a group is injected, then the number of seconds the infection takes to spread is the number of nodes in that group. So, to reduce the number of seconds in total, we inject the nodes that are part of the biggest groups first and try to get at least one node from every group injected as quickly as possible, so that the infection spr...