Code Invicta Discussion

[aalokagrawal]

XORSEQ
anyone plz help me why my solution getting runtime error for a subtask.I got 20 marks for the solution and it is absolutely fine with the sample case.please help me to remove it
https://www.codechef.com/viewsolution/30746067

[rohitpal210]

you are getting TLE as your soln runs in O(NQ) but the intended soln is O(Qlog(N))

[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 !

[piraterajay]

Help please, FTALES01
why i am getting TLE for last 2 cases CodeChef: Practical coding for everyone

[phantom654]

I think your logic is : If two nodes are part of a cycle then there will be a different part other than the edge path.

The DFS part is a slight modification of printing all the cycles in graph algorithm.

Consider a fully connected graph with N nodes. Then cycles will be formed if we pick any number of nodes between [3 - n].
So total number of nodes that will contibute in cycle will be : 3 * nC3 + 4 * nC4 …+ n* nCn ~= n2^n … so the worst case complexity will be n2^n.

I also used the same code from GFG article in contest seeing its complexity O(n+m) and got TLE. I think the complexity is mentioned wrong there.

Better use the Atriculation points and bridges technique to see if removing the edge makes the two nodes unreachable from each others and increment ans accordingly.

Please correct me If I’m wrong.

[piraterajay]

My logic is exactly what you said and i think you are right. Thanks for the help and this complexity is a big mistake at GFG have you confirmed this from somewhere else also ?

[phantom654]

NO!!!
But if you find any mistake in the wrost-case I gave please let me know.