pranjal.ssh's blog

BlackRock Codesprint

By pranjal.ssh, history, 8 years ago, In English

BlackRock is conducting an online coding competition on Hackerrank. You will have 48 hours to solve 8 challenges. This is an individual contest; top 54 participants get a BlackRock T-shirt and top three participants get Amazon gift cards worth $2000, $1000, $500.

The contest starts at 3PM, June 10, Eastern time

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

Comments Comments (47)
| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Does "financial problem" mean "standard algorithmic problem but with story/background related to finances"? And btw. why 54 t-shirts (not 50)?

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

    The problems are algorithmic problems with some financial terms(which will be well explained) and a bit of maths. Don't know about the t-shirts.

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

    This reminds me a story about Feynman (the physicist), he was taking a psychological examination. This is an excerpt from it:

    Then at some point near the end he says, “How much do you value life?”

    “Sixty‑four.”

    “Why did you say ‘sixty‑four’?”

    “How are you supposed to measure the value of life?”

    “No! I mean, why did you say ‘sixty‑four,’ and not ‘seventy‑three,’ for instance?”

    “If I had said ‘seventy‑three,’ you would have asked me the same question!”

    → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it -7 Vote: I do not like it

I posted something really stupid. Sincerely sorry about that. Hope everyone enjoys the round!

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

8 financial challenges = optimization problems as well?

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

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

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

I think for some problems most of contestants will spend more time trying to understand all these financial terms in statements than actually writing solutions to them.

That's one third of the second problem statement (Chromium refused to set zoom less than 0.25).

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

    Yeah, I decided to not solve that problem and try to learn with the other problems.

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

    That's the evilest thing I've ever seen in my life T.T

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

    I actually think it was a good exercise in problem statement decryption. You don't always get a perfectly explained problem or a simple statement — it was good practice in my opinion :)

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

      Nah, this was by far the worst problem — a simple linear-time algorithm to implement all the "if"s that are in the (unclear) statement. All other problems were far better than this, though maybe not terribly interesting.

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

Argh, seems like I am too slow for this sprints :( Although I started 40 minutes late because Y.A round

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

Even among the Codesprint series, there is the difference in their scoring systems. One scoring system uses "last time" as the tie-breaker and another one uses "sum of each time". Why does HackerRank use a different scoring system each time?

I think the difference of scoring system is very important for the strategy of solving order. Is there any way to know the scoring system before the someone's second submission? If none, I think HackerRank should announce the scoring system before the contest.

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

    It seems it can change even during contest

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

What is happening to the leaderboard? It seems like the scoring system is changed from "sum of time" to "last time" now.

Even if there are no way to know the scoring system before the contest, everyone can know the scoring system during the contest and build their strategy with the scoring system.

Changing rule during the contest is not fair at all.

In general, everyone assumes the result is final (unless unavoidable re-judgements occur). Why did they the change? Has my comment affected to it? Wasn't it unnecessary at all?

HackeRank should revert the change.

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

    Yes, I agree and it is not fair at all. They didn't even announce anywhere that they changed the scoring system. It seriously hampered the rank list, mostly the top 10. HackerRank should revert the change and explain what is going on.

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

    I totally agree. Doing such things moves an online judge/community from the "serious" category to "not serious", I think.

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

About time strategy.

All Hackerrank Long contest have last submit time as tie breaker, due to a bug the time strategy got messed up in this contest. It's evident although we didn't announced it in advance but it's expected to be last submit time.

It's a bug, and we had no intention on being unfair to any participant. In case your ranking fell we're extremely sorry.

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

    What are you even talking about?

    Regardless of the scoring strategy that you had in mind before the contest (and I think it's far from clear that all the long contests use the last submit time), the rule that was in place at the time the would-be winners were determining their strategy was sum-of-times. This is a sponsored contest with large monetary prizes and it was over in 3-4 hours (as to who wins these prizes). Then, after the contest (effectively), you went and changed the rules to what they had been supposed to be in your heads? Nobody cares about what that may have been!

    Now the only thing you can do to partially salvage your reputation is to change it back and issue an apologetic clarification, IMHO.

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

Time strategy update 2

Since at the beginning of contest strategy was sum, we'll stick with the sum strategy for this contest.

Any inconvenience caused is deeply regretted. Sorry for any confusion caused.

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

    And now other 3 people are affected by bug in scoring system. I think the most fair decision will be to split prizes between 6 people, or ignore time at all and split it between everyone who solved all problems, or even don't give any prizes in this contest.

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

      "split it between everyone who solved all problems"

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

When you realized you can't win t-shirt without 2nd problem

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

Seeing Belarus in the win-not-eligible list is indignant.

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

I don't get what's the point of these 24/48 hrs codesprint with when everyone knows it's about speed and top 10 are going to finish the contest in 2/3 hours :/

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

    If you enjoy solving problems and can't solve all of them within 2/3 hours... I think it is better than solving problems of contests which already ended?

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

Do people get job interviews as result of contests like these?

I am particularly interested as I have my term limit expiring soon (this is Cayman Islands thing), so I will have to change the job (and location) soon. Blackrock is the obvious choice for Finance professional who wants to get into IT.

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

Ended. Someone wants to share his interesting solutions? Especially the last problem

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

    How did you solve Trade analysis?

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

    Generate all possible valid subsets consisting of a's and b's of length n/2. There can be at most n/2 choose n/4 distinct valid subsets. Now for each subset count how many ways they occur as two distinct subsequence in the string with DP.

    Don't know if this is the intended solution or not but that's the way I solved it.

    source code

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

As editorials aren't revealed as of yet, Could anyone explain the solution to Trade Analysis. I was thinking in terms of finding coefficients of various powers of x in the polynomial (x+a1)(x+a2)...(x+an) using FFT turns out I can't implement it properly.Please share your solutions for this problem.

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

    code

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

    I solved it with FFT too. http://pastebin.com/Spk2vZRb

    But It's definitely an overkill.

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

    Another solution using a polynomial:

    Let f(x) = (1+x*a1)...(1+x*an). It's well known that the sum of a polynomial's coefficients is f(1). However, we have this weighted by |T| thing. So, let's consider f'(x) instead. Notice that the coefficient of x^(t-1) is equal to t*(sum of products of t things from a). So, f'(1) is our answer. Also, note that f'(x) can be written as sum of a_i * f(x) / (1+x*a_i). So, f'(1) can be found pretty easily from this sum. For example, see this code here: http://pastebin.com/JnN4yWCf

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

How to solve audit sale problem?

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

    Sort the elements by P*(100-C). Now if we pick M elements, then it's optimal to make sure that the first K elements can be sold. Use heap to build two arrays prefix[] and suffix[], where prefix[i] = sum of K largest Price*100 in the first i elements, and suffix[i] = sum of (M-K) largest Price*Prob in the last (N-i+1) elements. Finally answer = max(prefix[i] + suffix[i+1]).

    Code: http://pastebin.com/uFwdA9Q3

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

      Why do you sort by p*(100-c) ? Why partitioning this order of sorting gives all possible solutions?

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

        Let A and B be two selected elements, in which we can make exactly one element to be "special" (i.e it's probability become 100%).

        If we make A become special, the income is: F(A) = A.price*100 + B.price*B.prob;

        If we make B become special, the income is: F(B) = B.price*100 + A.price*A.prob;

        When it's better to make A become special ? The condition is exactly F(A) > F(B). This is what the compare operator do in my code.

        Now if you look closer to the expression F(A) > F(B), it's actually: A.price*(100-A.prob) > B.price*(100-B.prob).

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

Is there any other way beside backtracking + DP to solve problem 8 ?

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

    I only use backtracking with meet in the middle principle. Backtrack for the first 2^(N/2) possible configurations, save the difference of them in an array count[]. By difference I mean the remaining characters if we trim the similar prefix. Each configuration can be represented by a binary mask smaller than 2^(N/2), which is small. Do the same brute force backward, now use count[] to re-calculate the answer.

    Code: http://pastebin.com/akXMX9Dc

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

Leaderboard announcement.

There was a bug in Portfolio manager as pointed by AlexDmitriev here

This is fixed and leaderboard is now final to the best of my knowledge.

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

Somehow the contest disappeared from the archived contest list and my contest history. It's been a month and I haven't got any email from BlackRock.

→ Reply