Hi everyone!

I'm happy to announce you about the new contest organised by HackerEarth — **India Hacks 2016!**

Just check out the prizes:

There will be **3 qualification rounds** with 3 hours duration each. From each qualifier **top 1000 participants** will advance to the main contest, so the final is going to be a decent battle of 3000 coders.

The first qualification round is taking place on Sunday, January 3, 18.30 Moscow time. View your time here

The problems of the first round were kindly prepared by RomaWhite. As you might already guessed I'm the tester and editorialist. In my opinion this problem set is very nice because it requires more thinking than implementation, but on the other hand most of the problems are not very hard, so it will be a good warm-up for your brain after New Year celebration :)

In order to participate register here.

**Important note**: this contest has a partial scoring system and all the problems have subtasks. It means that if you don't know how to solve some problem you should try your best to get some partial solution.

Bye-bye and I hope to see you all participating and having fun :)

The contest starts in less than 2.5 hours. Good luck everyone!

Will there be editorials ?

You are red with black letter, why do you need one? ;)

Editorials were added before the contest, but there are some issues with adding problems to practice again and editorials are unavailable :/ I hope admins will deal with it soon.

Anyway feel free to ask questions and discuss problems here.

First four problems:

1) String DivisionIf the length of the string is less than 10, bruteforce over all possible ways of splitting the string.

Otherwise the answer is "YES" (split the string into four parts of lengths 1, 2, 3,

length- 6)2) Hungry Lemurs:Try all possible final values of

k, for each oneifind it's closest multiple ton, call itvand the answer for this value would beabs(k-i) +abs(n-v).3) Strange Function:First sort the array in ascending order and subtract

cfrom all elements of the array. calculate the current answer for this array, call itcurNow, go through the numbers in descending order, Add 2 *

cto the current element, updatecur.The answer will be the maximum value of

curUpdating

cur:Adding 2 *

cto an element will decrease the difference between it and each element larger than it by 2 *c(thereforecurwill decrease by 2 *c* (n-i) ) and increase the difference between it and each element smaller than it by 2 *c(thereforecurwill increase by 2 *c* (i- 1) )So

cur=cur- 2 *c* (n-i) + 2 *c* (i- 1)4) Permutation Swaps:Consider pairs that can be swapped as edges, and positions as vertices. A number

ican move to it's position inQif there is a path between it's beginning position and it's final position.I used DSU to solve this problem , after adding all edges, if there is a number whose position in the first permutation is in a different component than it's position in the second one, then the answer is "NO", and "YES" otherwise.

I would appreciate if someone could explain his solution to the fifth problem

Any proof for the third problem ? How did you come up with that ?

First, subtracting

cfrom all elements then adding 2 *cto some of them is equivalent to subtractingcfrom some elements, and addingcto others.The only assumption in my solution is that after sorting the array and subtracting c from all elements, the elements to which we will add 2 *

cform a suffix.Proof:

If we add 2 *

cto thei^{th}element and not to thej^{th}elementi<jthis will affect the answer by:2 *

c* (i- 1) - 2 *c* (n-i)However, If we add to the

j^{th}element instead of thei^{th}, this will affect the answer by:2 *

c* (j- 1) - 2 *c* (n-j)and since

j>i, then 2 *c* (j- 1) - 2 *c* (n-j) > 2 *c* (i- 1) - 2 *c* (n-i) ,therefore it's better to add to thej^{th}element, so the elements will form a suffixAnother way of looking at it: we need pairwise absolute difference for all pairs.So even if we sort the numbers we don't cause any change(since still the absolute pairwise diff would be the same.) So after we have sorted the data we want (assume 1 based indexing)..(let's see for first element )|a1-a2|+|a1-a3|...|a1-an| as data is sorted this is equal to (a2-a1)+(a3-a1)+...(an-a1).So we notice a1 is subtracted n-1 times . following similar process for a2 we'll get that a2 gets subtracted (n-2)times and added once(1st term of a1 series). so eventually we get a[i] is added (2*i-n+1) times. Now we can accordingly increase or decrease a[i] by c to suit our purpose of maximizing individual positive contribution or minimizing individual negative contribution of a[i],based on signs of a[i] and (2*i-n+1).

Can someone tell me how my naive solution got 100 points for the first problem ?

https://ideone.com/6eDaoc

If n>=10 there is always a solution where

i= 1,j= 3,k= 6 , so your solution will find the answer quicklyOh right !

How did you come up with this ? I mean that we need to bruteforce when n<10 ?

because n<10 :D

I'm not getting where is that '10' coming from ?

you can guarantee that 4 strings are pairwise different if they have different lengths right? so you need at least 10 letters to have 4 distinct lengths (1+2+3+4)

I am so stupid!

You're and legendary grandmaster (nutella).

So you already know all these things. and you're just kidding. ;)

he is magically legendary grandmaster.

I know,

I'm also kidding.

By the way, the editorials are live now. And the problems are open for upsolving, too. Do not underestimate the power of upsolving a contest. (That is, if you failed to solve something!)

Are all the rounds online or is there any onsite round as well?

There is something called "PHASE II (OFFLINE)" in the contest website. Does this mean there will be an onsite for Algorithms track as well?

Yes. There will be one.

When can we expect prizes to be delivered to us? It has been more than 6 months but haven't received prizes yet.

They just keep on postponing the expected date. They always reply that it's in progress and will be delivered to you within next 3 days.

UPD: Today I got a confirmation mail from HackerEarth that my prize has been shipped.