Hello Everyone!
I would like to invite you to participate in HackerEarth's August Easy '18. It will begin at 13:30 UTC, August 4, 2018
The problems have been prepared by me (TooDumbToWin) and vntshh. The problems have been tested by Lewin. I hope you'll find the problemset to be interesting.
You will be given 6 algorithmic problems 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 even experienced problem-solvers find one or two problems to be interesting. The contest is rated.
As usual, the prizes will be awarded to the top 5 beginners (that is, programmers with a rating less than 1600 before the challenge starts):
- $100 Amazon gift card + HE t-shirt.
- $75 Amazon gift card + HE t-shirt.
- $50 Amazon gift card + HE t-shirt.
- HE t-shirt.
- HE t-shirt.
Good luck and have fun!
Edit: Contest begins in 15 minutes.
Edit2: The contest has ended. Congratulations to the winners. You can discuss the problems now.
The contest page says prizes for beginners(with rating of 1600 or less).This announcement says less than 1600.Can you clarify it?
It was incorrect on contest page. It's fixed now.
Need some explanation for the tougher problems :(
I won't tell anything bad about tasks, they were fine :)
But can you explain next few things :
How solution in complexity O(n2) passing second one ? You should take care of it.
What is happening about third task and are you sure your solution is correct?
Why in the D task you are allowing complexity O(n * MaxAreaOfCycle) ? You could make bigger constraints for precision at least for one decimal. I think lower precision than 0.01 for points still will pass all testcases.
And how to solve D faster?
First, I described following solution:
Change area 100 × 100 to something bigger, like 10000 × 10000 squares ( with this cases 2000 × 2000 was enoguh and that is bad from my view). After it iterate over all circles and mark all visited squares for that circle. In worst case it can be O(n × Area). With lower precision it was AC.
But you do not need to mark all points. You can mark only over different rows. Something like for each row you have n different intervals which contain at least one circle. Now question is how many points are inside that n intervals and it can be solved in O(nlogn). So final complexity would be something like O(numberOfRows × nlogn). So for current constraints, you don't need to separate area to 2000 × 2000, you can separate to 105 × 105 and still it will be AC, but with bigger precision.
Monte-Carlo algorithm was enough.
I didn't notice any O(n2). Can you point me to the solution? I did notice something like O(100n) (which should not have passed). I agree tests should have been stronger.
Yes, I'm sure tests are correct. I am not sure why solutions were failing so I'll assume it is precision issue. Your solution failed on N = 16, P = 997815202912861716 (9th test on 1st input file). It has no solution. Your output was 7336876492006336.
It was my first geometry problem, so the constraints were quite liberal. Since the targeted audience was beginners, I won't really mind O(n * MaxAreaOfCircle) passing, but sure I should have been careful.
No, I do not talk about O(100n) or something like it, I am talking about algorithm: number A_i is equal to Ai = AiorAi - 1or... orAmax(1, i - k). So you can simulate answer for Ai. Complexity is O(n × min(n, k)).
Ok, I won't say that my solution is enough precise, I do not know it. But when you give next custom input: T = 1, N = 100000, P = 1 — your expected output is - 1. I am talking about tool given by HackerEarth. So, something is not good there.
It is not problem, I have just mentioned what is my opinion for that task. I could try, I though it would not pass :)
Just an advice for future contest: try to reduce the impact precision makes, I have no idea what is the difference between mine and official solution, and it fails on couple large tests.. It must be due to precision
How to solve problem C?
you can easily get the probable answer, lets to say x, by dividing P with sum of n numbers from 1 to n and now the only thing that is to check is whether it is possible for any real value in the range [x,x+1) to make the sum equal to P and you can do this by implimenting binary search. Checking for numbers with the precision of 6 digits after decimal place would be sufficient (you can prove it very easily) and thus if you get any such number print x else -1.
How to solve problem E , how is lca between nodes helping here
There are a lot of possible solutions. The simplest one to implement and understand is:
Start with any random node among the selected nodes. Find the node in the given set farthest to the current node in O(k). Mark this node. Again find the node at the maximum distance to this marked node in O(k). This is basically simulating the approach of finding the diameter of a tree, except that here we don't have the complete tree.
LCA will be used to calculate the distance between two nodes. For finding the node at the maximum distance to a particular node, just iterate over all the remaining nodes and check their distances with the help of LCA.
Thanks for the reply. I get most part of code in editorial except that involves stack and dp. What does sorting vertices based on intime do
Here is my O(120N) solution that got AC.
The case of 10^5 elements with 1 followed by all 0s would not have passed.
Most doubtful statement — "the contest is targeted towards beginners".
What's the idea behind solution for problem F?
well, those two operations of type 2 are basically "delete element at position k and after that insert it at position N or 1 (depending on type of query)". This can be simulated with a treap with implicit keys.
The intended solution was to use segment tree. You can check the setter's code in editorial.
UPD: Editorials for all the problems are up.