chemthan's blog

Invitation to HackerEarth February Circuits '19
By chemthan, history, 6 years ago, In English

Hello everyone!

I would like to invite you to participate in February Circuits '19. It's a long contest that will start on Feb 15, 9:00 PM IST (check you timezone). Contest will run for 9 days.

The problem set consists of 7 traditional algorithmic tasks of various difficulties and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.

I'm the tester and Alpha_Q, aminul, Apptica is the setters. I would like to thank HackerEarth admin panel, without them we do not have such contests. Below is the detail of problem set:

  • Day-0: Easy, Easy-medium, Approximate.
  • Day-2: Easy-Medium, Medium.
  • Day-4: Medium, Medium-hard.
  • Day-6: Hard.

As usual, there will be some nice prizes for the top five competitors:

  • First place: $100 Amazon gift card + HE t-shirt.
  • Second place: $75 Amazon gift card + HE t-shirt.
  • Third place: $50 Amazon gift card + HE t-shirt.
  • Fourth place: HE t-shirt.
  • Fifth place: HE t-shirt.

Hope to see you at the scoreboard! GL & HF.

UPD: Congratulations to the winners

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

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

The contest will start in 30 minutes!

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

How to solve cost recovery?

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

    Let pi be the prefix sum of b. Then

    Unable to parse markup [type=CF_TEX]

    , where

    Unable to parse markup [type=CF_TEX]

    is the Stirling number of second kind. You can arrange these in matrix form and to find p, you can multiply vector a with inverse of the matrix of Stirling numbers of second kind, which is surprisingly the matrix of signed Stirling numbers of first kind!
    Since you only need to find

    Unable to parse markup [type=CF_TEX]

    , you need to find

    Unable to parse markup [type=CF_TEX]

    . You can find the

    Unable to parse markup [type=CF_TEX]

    row of signed Stirling numbers of first kind with FFT and then transition to next rows in linear time. Since

    Unable to parse markup [type=CF_TEX]

    , you'll do this only r - l times. This solution works in

    Unable to parse markup [type=CF_TEX]

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

      Got it, thanks!

      No idea why you got so many downvotes :/

      → Reply