Hello everyone!
I would like to invite you to participate in HackerEarth's February Easy '19. The contest will be held on 1st February, 2019 at 21:00 IST
The problems have been prepared by me (Ashishgup) and Jeel_Vaishnav. We would like to thank TooDumbToWin for testing the round and trytolearn for giving us the opportunity to hold the contest.
You will be given 6 algorithmic questions to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope that everyone finds the tasks interesting. The contest is rated for all and prizes will be awarded to the top 3 beginners (i.e. programmers with a rating of 1600 or less before the challenge starts):
- First place: $75 Amazon gift card.
- Second place: $50 Amazon gift card.
- Third place: $25 Amazon gift card.
Good luck and have fun!
UPD: The contest begins in 15 minutes.
excited about all the Contests of Ashishgup.
Auto comment: topic has been updated by Ashishgup (previous revision, new revision, compare).
How to solve Colorful Tree?
We can prove that the farthest node of color c from a node k will be an endpoint of diameter of nodes with color c. We can obtain diameters of each color by running an algorithm similar to the one used for obtaining diameter of a tree online. In that algorithm, if we have endpoints e1 and e2 for a diameter of color c, and we add a new node x of color c, then if x increases the length of diameter (i.e. x becomes an endpoint of new diameter), the other endpoint should be e1 or e2. Hence, we can find the distance to both endpoints and if the maximum of both the distances is greater than the current diameter, this will be the new diameter. Once we have diameter endpoints for each color, we only need to find the maximum of distance to both endpoints of diameters to solve queries.
nice and challenging problems are there.
when will be editorial come?
Editorials are published.
How to solve Development cost ? I am thinking it to be brute but how to find the path cost for 2 given points ?
Binary search for the answer in range [1, 109] To check whether a particular mid value helps in getting the certificate, we can see that we cant move to cells having value > mid. We color the cells by considering nodes with value > mid as obstacles. The cells reachable from each other (i.e. in the same component) are colored with same color. This can be done using dfs. Once we color the cells we iterate over the queries. In order to check whether a particular query is satisfied, we check that the source and destination have same color. If the number of satisfied queries are > = k, mid value helps in getting the certificate.
problem B editorial
As Um_nik would say, this problem is faster to solve by yourself than find the solution on the internet.
Yes. I search this link after contest.
isn't development cost the same as this problem M here https://codeforces.me/gym/102021.
however instead of using parallel binary search to solve each one you solve binary search to solve all.
We didn't know that this version of problem existed when we created the problem. Sorry for any inconvenience.
Can you explain how to use parallel binary search for the problem exactly?
You can learn Parallel Binary Search from: https://codeforces.me/blog/entry/45578
Suppose you get two nodes connected by adding all edges with weight less than or equal to x then you know that smallest-cost path cost between them is less than or equal to x so you can basically binary search for finding this x. Parallelization comes from the fact each query is independent. Firstly you can sort all edges by weight and apply(i) here is analogous to adding edge(i) in the dsu then check(i) will check if query i nodes are connected or not. Using this you can find answer for each query then just report kth smallest value.
Code: https://www.hackerearth.com/submission/23494126/
This was a very instructive contest. Kudos to the problem setter.
Here are my solutions to this contest.
The Math questions — Pile of Stones and Array Game were nice.
But, I particularly enjoyed the data structure questions as it took me a day to solve each of them. It required nice implementation skills of structures like Disjoint Set Union, Segment Trees and LCA.
Ashishgup's code in the editorial was very readable !
I have a doubt in the problem Flipping Brackets.
When we are doing binary search in an array to find the last occurence of the element x and are guaranteed that no element smaller than x exists in the array, we are doing binary search on [i, N].
Initially, L = i, R = N
M = (L + R + 1)/2. We check the min{M, R}. If it is = x, we set L = M. Else, we set R = M — 1.
I got the binary search idea but my question is why do we set M to (L + R + 1)/2 and not (L + R)/2 ?
I also have a question about the problem Colourful Tree. I have made two submissions with the exact same code. One timed out and the other got AC. How did this happen ?
Regarding Binary Search conditions, I'll give a general approach that you can use to avoid such conundrums.There are other well tested conditionas that you can find elsewhere as well which would avoid infinite loops in BS.
In most BS problems we start with an answer(this can be either low or hi) and progressively try to optimize it (make it larger or smaller in each iteration as per the requirement) Ex : In a sorted array find first number greater than x -> you can plug 'infinity' at the end of your array and assign lo = 0, hi = n (size of array), In this case you have a possible answer (at hi) and in each iteration you try to push the hi to successive smaller values, during all times you maintain 'an answer' at hi.
In the current problem it seems that the author maintains the answer at L ( the assignment L = M), Suppose our Binary search domain has reduced to [5,6], Now since we are maintaining answer at Lo, we have already checked that 5 satisfies our requirement and we'd like to check if 6 does as well.
See what happens if you use M = (L + R)/2 ? , you end up checking '5' again and again, hence we use M = (L + R + 1) / 2. In a similar way in other questions your invariant might be to maintain answer at hi throughout, in that case use M = (L + R) / 2.
Oh I see, thanks. So we choose mid depending on which end of [L, R] maintains an invariant that satisfies our condition.
Yup.
Also see this comment by yeputons.