DEVVOTE : Solving the problem without hard coding the answers.

general
1

Can anyone explain their approach to solve the problem DEVVOTE, in the given time limits.
In the first 2 pages, of submission, I only found one person who actually got the problem accepted without hard-coding the values.

5 Likes
2

@karanaggarwal: you can solve the question in entire poly(n) time :slight_smile: Author’s and tester’s solution are of online numberOfpartitions(n) * poly(n). I infact, did not increase constraints because I was expecting a lot of online solutions :frowning:

1 Like
3

@dpraveen , I just used the following assumptions without loss of generality ,

  1. occurence of New numbers in increasing order .
  2. occurence of previous numbers for same count in increasing order.
    Was there any other Asymptotical optimisation involved ?
    My worst case soln i.e. 36 cases for n = 36 each took around 12 seconds , with very - unoptimised implementation though .
4

What was the complexity of the solution you used to hardcode the answers ?

1 Like
5

My similar implementation took 2-3min for n=36 :stuck_out_tongue: