Code Invicta Discussion

[eunoia_1729]

The editorials have been posted for all the problems. Do give them a read and feel free to discuss below them your approaches and ask queries.

BCK2 - Editorial

PROBLEM LINKS: Practice Contest Author and Editorialist: Aakash Mehta DIFFICULTY: EASY-MEDIUM PREREQUISITES: Trees, LCA, Centroid. PROBLEM: On a weighted tree, for all the nodes of the tree, we need to calculate total maximum distance possible that can be covered such that every node goes to some other node. EXPLANATION: Consider the distance between two nodes as: dis(u,v) = droot(u) + droot(v) - 2*droot(lca of u,v); Here dis(u,v) denotes the distance between two nodes u,v. droot(u) deno…

CHRIST02 - Editorial

PROBLEM LINKS: Practice Contest Link Author and Editorialist: Abhishek Garg DIFFICULTY: Medium-Hard PREREQUISITES: Lowest Common ancestor, Heavy-Light decomposition, Megre-sort tree PROBLEM: You are given a tree with distinct values attached to every node of that tree. You need to answer queries of the type U V L R i.e. for the given 2 nodes U and V, you need to tell the number of nodes on the simple path between U and V such that the value attached to those nodes lie between L to R inclusi…

XORSEQ - Editorial

PROBLEM LINKS: Practice Contest Link Author and Editorialist: Bhavya Girotra DIFFICULTY: Easy-Medium PREREQUISITES: std::set and std::pair PROBLEM: Given n cities with initially 0 gifts, you can either drop a gift in a house or have to find the magic number for a house. The magic number for the ith house is the xor of the house numbers of first continuous sequence of houses with house number \geq i and having 0 presents. QUICK EXPLANATION: We will be using a set of pairs, where each pair d…

MOON - Editorial

PROBLEM LINK: Practice Contest Author: Kumar Raju Editorialist: Kumar Raju DIFFICULTY: CAKEWALK PREREQUISITES: Implementation, Math PROBLEM: Given N items of value X and M items of value Y, divide the items into two sets S_1 and S_2 such that \sum s_1 = \sum s_2 . QUICK EXPLANATION: You can find the answer by running two nested loops. EXPLANATION: Let the two sets be denoted by S_1 and S_2. Let (i,j) be the tuple denoting the number of elements valued X and Y respectively is S_1. There…

FTALES01 - Editorial

PROBLEM LINK: Practice Contest Link Author- Samarth Mittal Editorialist- Samarth Mittal DIFFICULTY: EASY-MEDIUM. PREREQUISITES: Depth First Search, Bridges PROBLEM: Given a graph with N trees, M pavements and X animals. Find the number of harmful animals. Animals are harmful if they stand on a path which is the only path connecting its end-points. (i.e. is an edge of a graph whose deletion increases its number of connected components.) QUICK EXPLANATION: One needs to find all the special …

CHRIST01 - Editorial

PROBLEM LINKS: Practice Contest Link Author and Editorialist: Parmjeet singh DIFFICULTY: Easy PREREQUISITES: Combinatorics QUICK EXPLANATION: We can solve this problem simply by using inclusion exclusion principle. let A_{i} be the event denoting that character from i_{th} bag should remain together. So clearly S_{n} =| A_{1} \bigcup A_{2} \bigcup A_{3} ... \bigcup A_{n} | will be the required answer. EXPLANATION: using inclusion exclusion principle S_{n} can be written as: S_{n} = \displ…

Keep coding and stay safe !