rivudas's blog

Invitation to October Easy 2016 on Hackerearth
By rivudas, history, 8 years ago, In English

Hello Codeforces,

I invite you all to participate in HackerEarth's October Easy on the 1st of October at 10:00 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 Himanshu Jaju(himanshujaju) and me(rivudas) and tested by Yury Bandarchuk(Yury_Bandarchuk). I would also like to thank all the Hackerearth admins for their help.

Good luck and have fun.

Edit 1 — The contest has started. Good luck to all.

Edit 2 — The contest is over now.

The top five winners are -
1. Trumen
2. -Morass-
3. 1100011101
4. felix
5. hellman_

Thanks to everyone for participating. Hope you liked the problems. The editorials will be out soon.

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

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

Auto comment: topic has been updated by rivudas (previous revision, new revision, compare).

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

Oh, a time clash again! I hope it gets resolved before the Codeforces Round starts, I wanted to do both :) Since the intersection this time is minor (5 or 15 minutes, depends on Codeforces), I wonder if the October Easy can be moved forwards with like 20-30 minutes, it would be quite unfair to move the Codeforces round backwards.

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

    The contest has been postponed by half an hour. Good luck. :)

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

      What's the new time now?

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

        10:00 PM IST. The timing has been updated in the blog.

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

Auto comment: topic has been updated by rivudas (previous revision, new revision, compare).

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

Thanks a lot to everyone who took part in the contest. I was the setter of the first three questions "The Best Player", "Gold at lolympics" and "Closing ceremony". Any feedbacks on these questions is welcome :)

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

    People openly discuss solution in comments and no one takes any action. Also the problem statement of "Boring Marathon " was not clear earlier and a change was made between the contest without any notification.

    Wasted my 3 hrs. Last contest on hackerearth

    Here is one such comment.

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

      Well I was in charge of my questions, and kept deleting unnecessary comments as and when I saw them. Regret any inconvenience caused. We will definitely try to improve on the statements and overall quality. Thanks!

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

    I liked Gold at lolympics. Though it was more or less straightforward.

    Also I suspect the test cases were very weak. I was getting 1 test WA (and others AC), and I fixed 4 different bugs until I got it. Probably all that bugs were not covered..

    I suspect the same about other challenges. Byteland Trip — a graph problem with 5 tests? Seriously?

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

      Thanks for the feedback. Yes, after seeing some solutions pass I figured out that the tests were weak. I will try to improve my test generation skills. :)

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

    Could you explain author's solution for the problem "Gold at lolympics"? My solution got 100, but I suppose that it's not completely right.

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

      The author solution involves finding prime factorisation in O(N^{1/3}). Once that's done, its a simple dp to find the answer.

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

      Your solution is almost fine.

      If N has smallest prime factor p > cuberoot(N), then either N = p2 or N = pq in which cases the Sprague-Grundy function f(N) is equal to 2. Thus if you can't find a prime factor less than 105, you have to check if N is prime (f(N) = 1) or not (f(N) = 2), with a primality test.

      A tricky point is that even if you have found a small factor (e.g. N=2*d), you still have to check that d = N / 2 is prime or not.

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

        I didn't notice the fact "If N has smallest prime factor p > cuberoot(N), then the Sprague-Grundy function f(N) is equal to 2.".

        Thank you for the explanation!

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

Can you please :

Make the solution public

provide short editorial

Make the problem available for practise

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

Can anyone tell the correct approach of Closing Ceremony at Lolympics because the editorials are not available and the solutions of other programmers are also not visible.

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

    Good day to you.

    It can be solved with "Nimbers" {some dynamic programming [Number X maxXor] }.

    The nimbers are +/- prime_factors_counts (since this allows you to move on "some lesser divisors")

    You also have to use some faster factorization (such as Pollard Rho) :)

    Good Luck!

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

      I think you are telling about the Gold at lolympics question but I'm asking about the 3rd question which is Closing Ceremony at the lolympics.

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

        Count the number of bad answers and subtract it from 2^n.

        For the number of bad answers, count the number of subsets with sum < K and multiply by 2 (because it can belong to either bag A or bag B).

        Counting the number subsets with sum < k can be done in O(n*k) time using knapsack dp.

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

          Thank You :) Didn't thought the main trick of taking the problem in the opposite manner. Nice One !!!

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

        Oh ye,

        I'm so sorry for the inconvenience! :P

        So as abisheka said, Knapsbag ^_^

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

How to solve "Boring Marathon" ?

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

    What i felt this problem had a quite confusing and unclear problem statement, from what i had inferred and solved using the same logic. The problem basically gives you a string and this same string is given to both the players. Now we have to find the expected number of times both pick the same character, as there can be atmost 26 distinct characters this is what i did..

    1.Traversed the string and stored the count of each character in an array. 2.Iterate over all the characters and now we basically have to calculate the number of ways this character would be picked up simultaneously by both players ie (number of ways player1 picks up this character)*(number of ways player2 picks up this character). As the string is same this is equal to count(character)^2. 3. Add all these squares and finally divide them by the length of the string.

    This gave me AC. I hope this helps :)

    → Reply