zemen's blog

Week of Code 31 on HackerRank
By zemen, history, 7 years ago, In English

Week of code 31th edition is starting soon April 10th 7:00am UTC.

Monday to Sunday Every day 1 challenge will go live.(Easy to Hard)
Score decreases by 10% at the end of every 24 hours.
Your submissions will run on hidden test cases at the end of every 24 hours.
Time of each challenge will be counted as your most recent successful submission.

Contest is rated and top 10 get T shirts.

GL & HF

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

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

Could you provide the proof for applicability of binary search in "Spanning Tree Fraction"? At least that if sum(a_i)/sum(b_i)>=C then we should prefer edge weight function a_i+b_i*C with bigger C and if sum(a_i)/sum(b_i)<C then we should prefer edge weight function a_i+b_i*C with smaller C.

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

    A proof for similar problem (choose a subset of size k having maximum weighted average. In this case k = n - 1 with additional spanning tree constraints) is mentioned here.

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

      Thank you very much for your link!

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

The final tests could have been stronger. I got accepted with partially random solution in the last problem (in counting the number of connected components) and I'm pretty sure I know quite a wide class of situations where my solution should fail.

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

    Also, the problem Nominating Group Leaders has weak tests, I got accepted with solution, where C — the number of different numbers that occur at least 2 times in an array v.

    → Reply