Hello everyone!

I would like to invite you to participate in HackerEarth May Easy Round that will be held on Sunday, 01 of May. The duration of the contest is 3 hours.

The problems were set by pkacprzak and tested by me. The difficulty of this round will be not harder than CodeForces Div. 2 Round (maybe even easier). You'll be provided with 5 classic problems having partial scoring — you get points for every test that your solution passed, and also one approximate problem — your score for this task depends on how good your solution is comparing to current best solution *(and don't be afraid of facing an approximate problem in a contest which lasts for 3 hours only ;) )*. This contest will be a rated HE Round.

You'll be provided with statements in English, and there will also be a Russian version as well — thanks to shef_2318 for working on a problemset as a translator.

Also I want to thank to belowthebelt for helping with technical aspects of contest preparation.

In any case, Good Luck && Have Fun all of you! I hope to see you in standings :)

*UPD. Please notice that problem statement of Bridges in Karak has been changed (there is an announcement about it in a contest as well — output format has been changed). We are sorry for it; in case you already attempted that problem — we strongly recommend you to check updated statement and try to fix your old solution. We'll do our best to minimize effect of this mistake in contest standings (exact decisions about rejudging old submissions and stuff like that will be made later), also contest has been extended by 15 minutes.*

I think it's time for me to get back to HackerEarth. And maybe for you to get back to Twitch, I really miss your streams :D

I dont know how the evaluation order is decided, but waiting for 5-10 mins for verdict sucks!

You should resubmit!

I don't know why I get TLE on the third task, I tried Fermat's test, then Miller-Rabin and still TLE. Anyone else who did the same and got TLE?

BTW, let's share our solutions to the sixth task! :) Mine was a few (5-8) phases of simulated annealing. To get a neighbor solution, I randomly choose one of the 4 colors, then randomly choose one of its parameters (L, a or b) and then I randomly choose whether to increase or decrease the parameter. Then for each simulated annealing I increase/decrease the parameter with different number which I called step, like STEP1=5 for the first simulated annealing, STEP2=1 for the second, STEP3=0.1 and so on :)

Miller Rabin worked for me, in 0.3 seconds. Checked against 2,3,5,7,11. (should be enough).

EDIT: Sorry, I forgot to mention that I used __int128

Apf, I also checked for them and got TLE, I will look at your code and compare it to mine after I have dinner. Thanks! :)

Hint: slow part of your solution is doing (A*B)%C with binary multiplication. If you are going to use it — it will be not so easy to make it work within TL :)

There are several ways to make it work faster; for me following fix sounds simplest:

Thank you, I remember on some judge I tried to use __int128 and it gave me CE and that's why don't even think about it but maybe I should start using it! Nice trick! :)

PS: Looking forward to your next streams :D

Miller Rabin was the intended solution. In my solution, which you can find under setter's solution, I used the deterministic version, but random one will work also.

I used Miller-Rabin but got Wrong Answer. Is it beacuse I didn't use __int128?

It depends on your implementation. Check it for possible overflows. I wrote my solution in Python in order to avoid overflows at all

And who are the top 5 beginners in the contest that win a T Shirt?

Is the editorial coming out? This is my first hackerearth round ever, so I've no idea.

UPD: How to solve approximate problem? Thanks in advance

Outlines of solutions and my codes to all problems are already in system, so they should be posted soon (it seems like some of them are available already). Feel free to ask questions if something isn't clear or if you need more detailed explanation of some parts.

There was a small hint about approximate problem — in announcement I told you to not be afraid of it :) It's not actually a standard approximate problem — obviously you can try some optimizations and stuff like that, but for this task exact solution

(giving zero penalty)exists and it is not hard to find — you have to pick vertices of some regular tetrahedron, defined by center and edge length :) You can either derive required formulas by yourself or find them in Wikipedia :) I believe there would be much more AC's on this one in case it wasn't an approximate problem and it was put somewhere in the middle of the problemset. And it was another try to make people not afraid of approximate problems and/or scary/complicated problem statements.Thank you! I actually figured out the solution some minutes ago. Feels bad to be slow.

The editorials are written nicely and are easy to understand, wish there were more like this.

What's solution of 2nd task, meet-in-the-middle with some optimizations ?

O(2^n2 * n1) for every case! Greedy + Bitmask

Why greedy works?!

Because when you sort the amulus bottles, you get

`2 * a[i] <= a[i + 1]`

(Given). That makes greedy work!Capacities of bottles of Amulus form a sequence called superincreasing sequence (you can google for it), for which a problem of deciding if any subset of them sum up to a certain value can be solved greedily in linear time. Check the editorial by Bohdan for more details and his or mine solution in setter/tester solution section.

Superfunctions is very nice! At first I thought it's super hard, but managed to submit it 30 seconds before the end. And I don't understand completely how it works, just managed to fit the formula for samples.

I used mobius inversion to solve the first one, second and third were simple modifications of the first one!

In superfunctions I used a very nice, but not well know result (the paper with it is given in the editorial). However, if you examine the nature of these functions and group the terms in a different order of summation, you should get the result also. Editorial explains this also.

In problem "Super functions", use the fact that . Example, the first formula is equal to: .

How the second formula follows from the first fact, please?

, and the third formula is similar to the first formula!

No, I meant formulas from your comment. How the sum of phi(d) is related to gcd?

Let

gcd(i,n) =d. Then . Sum up them, we obtain that formula!Asking it one more time after I didn't get a reply. Who are the top 5 beginners(First yeat/Second year), has it been announced?