akulsareen's blog

Invitation to April Easy '16 on HackerEarth
By akulsareen, history, 9 years ago, In English

Hello Codeforces,

I invite you all to participate in HackerEarth's April Easy on the 2nd of April at 9:30 PM IST.

You will be given 6 problems to solve in 3 hours. The problem difficulty will be similar to that of a Div. 2 round on Codeforces. Each problem will be worth 100 points, but partial scoring is allowed so you can try to pass as many tests as you can.

The contest will be rated and will have prizes for the top 5 beginners.

The problems have been set by Pranet Verma (pranet) and tested by me (akulsareen). I would also like to thank HackerEarth admin, Arjit Srivastava (belowthebelt) for all his help.

Good Luck and Have Fun.

EDIT: Contest has been postponed by 1 day to avoid clashing with the Codeforces round.

UPD: Contest has ended. Congratulations to the top 5:

  1. azukun

  2. ceilks

  3. Kmcode

  4. hellman_

  5. rantd

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

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

EDIT: Contest has been postponed by 1 day to avoid clashing with the Codeforces round.

Now it overlaps with COCI.

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

I read the tags! :P

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

Reminder: Contest starts in a couple of minutes. Do take part.

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

Great Problems,thanks for your effort, problems could had been less ambiguous

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

How to solve linear recurrences?Mine was O(6^3*logn) which obviously din't pass.

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

    I had 5x5 matrix M which mapped (F[n - 2], F[n - 1], G[n - 2], G[n - 1], T[n - 1]) to (F[n - 1], F[n], G[n - 1], G[n], T[n]) where T[n] = H[0] + H[1] + .... Also precomputed all powers of the matrix Me for e = 0, ..., 215 - 1 and for e = 215, 2 * 215, 3 * 215, ...215 * 215. Then each query can be done with multiplication of two matrices (one from the first set and one from the second). But still I had to optimize to fit in 2 seconds TL.

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

      If you pre-compute M1, M2, M4, ... , M230, then you can compute the answer to each query in approximately 5^2*log(n) operations. To achieve this reduction perform the multiplication from right to left. Refer to the editorial for more details.

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

        speaking about editorials, where are they actually?

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

          If you are looking at the problem page then there are 3 options, "Problem", "editorial", and "my submissions".

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

            I have there only Problem and My submissions, but no Editorial :(

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

              Editorial.

              Also, if you are getting the option to go to practice area, do that and then see if you get any editorial option. If even that does not work then contact HackerEarth admins for help.

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

        I precomputed M1, M2, M3, ..., M215 and M215, M2·215, M3·215, ..., M215·215. So that I can compute Me = Ma + 215·b = Ma·Mb·215 in only one matrix multiplication.

        So I wonder what was so unoptimal in my solution, such that even log(n) multiplications from your solution may pass.

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

          You seem to be answering each query in O(m^3) (Please correct me if I'm wrong). Intended is O(m^2*log(m)) per query.

          My bad. Yours is indeed faster in theory( 5 vs log2(1000000000) ). However, your solution does seem to be suffering from cache misses(just changing the order of the loops in matrix mul achieves a small speedup).

          Dude! Use scanf and printf!. Your solution gets AC well within time limit(0.9s)

          http://ideone.com/anJgcj

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

            Ahh right, thank you very much for the investigation! My PR() macro confused me.

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

      Is it too much to ask you what was your matrix M? I tried the same thing but I couldn't even pass the sample tests.

      PS: Just found editorial is available, sorry for comment

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

        Sure, here it is:

            int step[5][5] = {
    //  F-2 F-1 G-2 G-1 T-1
       {0,  1,  0,  0,  0}, // F-1
       {0,  A,  B,  0,  0}, // F-0
       {0,  0,  0,  1,  0}, // G-1
       {D,  0,  0,  C,  0}, // G-0
      {FD, EA, EB, FC,  1}, // T-0
    };
        → Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve A?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  SORT(a);
  ll ans = 0;
  for (int i = 0, v = 1; i < n; ++v) {
    ll c = v * 1ll * v;
    if (c >= a[i]) {
      ans += c - a[i];
      ++i;
    } else {
      ans += c;
    }
  }

  cout << ans << endl;
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

      It doesnt work, actually.. Test:

      2
4 10

      UPD: But is gets 100 on Oj...

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

        You did not read statement carefully:

        "You quickly gather the balls and try to reconstruct a square pyramid(maybe of a different height) by using ALL the recovered balls"

        You have to use all found balls. E.g. in your example the optimal solution is to buy 1, for first colour, then 0 for second (you have 4 already), 9 for third (you have 10 balls, but according to statement we have to use ALL balls, so we can't throw one extra ball away), and we heed to buy 6 balls for the last color (16 — 10 that we have = 6). so, all together we need to buy 1 + 9 + 6 = 16 balls.

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

          Im using all the recovered balls, man:

          Lets split 10 into 1 + 9 and now we can build a square pyramid with height = 3.

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

            You cannot split them as each layer has to be coloured differently. The 10 balls are of the same color

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

            you can't split balls into two or more groups, because then you will have at least two layers of same colour which is prohibited.

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

              You are right, thanks for explanations.

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

Did you like any problem a lot? Did you dislike any problem a lot? Did you enjoy the problem non-linear recurrence? Do you have any other issue/praise for the contest? All feedback is welcome.

Also, editorials for all problems should be available.

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

Easy Non Linear Recurrences — I'm fooled :(

→ Reply