### Ashishgup's blog

By Ashishgup, history, 3 years ago,

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.

• +66

 » 3 years ago, # |   +29 excited about all the Contests of Ashishgup.
 » 3 years ago, # |   +3 Auto comment: topic has been updated by Ashishgup (previous revision, new revision, compare).
 » 3 years ago, # |   +17 How to solve Colorful Tree?
•  » » 3 years ago, # ^ | ← Rev. 6 →   +31 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.
 » 3 years ago, # |   +16 nice and challenging problems are there.
 » 3 years ago, # |   0 when will be editorial come?
•  » » 3 years ago, # ^ |   +17 Editorials are published.
 » 3 years ago, # |   +8 How to solve Development cost ? I am thinking it to be brute but how to find the path cost for 2 given points ?
•  » » 3 years ago, # ^ | ← Rev. 5 →   +17 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.
 » 3 years ago, # |   +5
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 As Um_nik would say, this problem is faster to solve by yourself than find the solution on the internet.
•  » » » 3 years ago, # ^ |   0 Yes. I search this link after contest.
 » 3 years ago, # | ← Rev. 2 →   +1 isn't development cost the same as this problem M here https://codeforces.com/gym/102021.however instead of using parallel binary search to solve each one you solve binary search to solve all.
•  » » 3 years ago, # ^ |   +15 We didn't know that this version of problem existed when we created the problem. Sorry for any inconvenience.
•  » » 3 years ago, # ^ |   0 Can you explain how to use parallel binary search for the problem exactly?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +11 You can learn Parallel Binary Search from: https://codeforces.com/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.
 » 3 years ago, # |   +11 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 ?