I_love_Tanya_Romanova's blog

Invitation to HackerEarth MayEasy Contest
By I_love_Tanya_Romanova, 9 years ago, In English

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.

  • Vote: I like it
  • +45
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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! :)

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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:

    long long mult(long long a, long long b, long long mod)
{
	__int128 res = a;
	res *= b;
	res %= mod;
	a = res;
	return a;
}
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

          → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why greedy works?!

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        Because when you sort the amulus bottles, you get 2 * a[i] <= a[i + 1] (Given). That makes greedy work!

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Let gcd(i, n) = d. Then . Sum up them, we obtain that formula!

          → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply