Isn’t it O(n \sqrt{n \log(n)}) with optimal C ?
Oh true, that does become slightly better.
Well, I think my solution is quite short and simple to understand. CodeChef: Practical coding for everyone I think it is O(nlog^3n) , but I use lower_bound which is quite fast. Also, you could make this solution faster by using Fenwick tree like so: CodeChef: Practical coding for everyone HLD is based on this: Easiest HLD with subtree queries - Codeforces and this can solve almost all tree query problems.
1 Like
You declared n as integer , it should be long long .
1 Like
@admin
Editorials will be posted soon. @ubc_123
1 Like
What will be the approach in order to minimise the answer ?
Check the 2nd section in in the solution sketch to of Jeremy and bearimy problem
My approach was similar to yours can you see why i am getting WA?https://www.codechef.com/viewsolution/30743684
Can you please explain how you solve the " Bring Positivity " Question !
Please share a tag for " Bring Positivity ". Thanks
You can check out the editorial : CHRIST01 - Editorial
1 Like
XORSEQhttps://www.codechef.com/viewsolution/30746067
you are getting TLE as your soln runs in O(NQ) but the intended soln is O(Q log(N))
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.
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…
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…
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…
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…
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 …
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 !
2 Likes
Help please, FTALES01CodeChef: Practical coding for everyone
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].2^n … so the worst case complexity will be n 2^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.
2 Likes
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 ?
NO!!!