Hello everyone!
I would like to invite you to participate in an upcoming HackerEarth contest — HackerEarth May Easy '17. The contest will start on May, 1 22:00 IST (check your timezone).
The problemset consists of 6 traditional algorithmic tasks. You will receive points for every test case your solution passes — so you can get some points with partial solutions as well. Please check contest page for more details about in-contest schedule and rules.
You'll have 3 hours to solve problems prepared by me (r3gz3n) and xennygrimmato. Thanks to usaxena95 for helping me with the preparation of the problems and testing them. Thanks to MikeMirzayanov for creating Polygon.
The contest is RATED.
Happy Coding!
UPD: The contest is ended. I hope you have enjoyed the problems. Editorials will be published soon.
Congratulations to winners:
What is the difficulty of problems comparing to codeforces Div2 rounds? Is it worth to participatinf for non beginners?
The difficulty of the problems is similar to codeforces Div2. Its worth giving a try. I hope you will enjoy the problems.
30 minutes to go. See you on the leaderboard. :)
Why editorial for Little Shino and Contests not provided? I am unable to understand through solution.
We will upload the editorials soon.
How to prove the greedy algorithm for Increasing alternative Sequence link
I was unable to come up with the greedy solution.But there is a solution using binary search.Binary search on the ratio and for checking a particular ratio use dp with 2 segment trees one each on array A and B.
Let's call the first array X, and the second array Y. Note that the problem requires that the sequence should start with an element of X.
The optimal solution will either have a length of 2 or 3, or greater than 3. Let's prove that the sequence will never have greater than 3 elements.
First let's prove that the sequence will end with an element of X.
Say that the optimal solution has a length greater than 3, and it ends with Y. i.e.
Hence p is even and greater than 3. We could get a better solution than this by just removing Yp. Hence the optimal solution will not end with Y, if it has a length greater than 3.
Now let's say the optimal solution has length greater than 3, and ends with an element of X. Assuming the sequence has p elements, the sequence can be represented as:
Now note that Xi < Yi + 1. Let's say that α is sum of all elements of X in the sequence, except Xi, and β is sum of all elements of Y in the sequence, except Yi + 1. Clearly, β < α
We can prove that removing Xi, Yi + 1 will lead to a better solution than the present sequence. Let's say Yi + 1 = y and Xi = x, then we have:
Now since x < y and β < α, we have β * x < α * y, and therefore:
Therefore, if we have a sequence of length > 3, and there exists an index i such that Xi < Yi + 1, removing Xi, Yi + 1 will lead to a better solution.
Hence the optimal solution will always have length <= 3
Can someone explain his solution for the last problem ?