[Community Puzzle] Robbery optimisation

Puzzles
#21

But the solver count depends on the number of people who have seen it.
That is probably higher for easy problems.

#22

Now you’ve just unsolved everything! :anguished:

#23

Hello. I have a question about the negative houses.

How should they be considered ? Do we break into them and then their values are added to the sum or do we avoid them and then there is no impact on the sum (so we add zero) ?

#24

@TheYoungPyro Negative houses (btw this is something that was added after validation of the problem…) have to be considered exactly as any other house: If you break into them, you add their (negative) values to the sum, otherwise they do not contribute to the sum.

2 Likes
#25

Was about to exclaim the same.

@Potemkine never do that again! This changes the puzzle in a significantly non-trivial way, and there are now solutions that went through and don’t pass the current state of validators. Very bad form.

2 Likes
#26

My bad, I just discovered the input and output for the “full negative houses” test and the expected output is 0. Also, considering the “positive and negative” test, I conclude that a negative house has to be avoided. I never noticed the “show testcases” icon on the top right corner of the test cases box before I asked the question.

#27

To my knowledge, Elliptic Curve was set to medium by nicola, after he did a great work in improving the statement.

As for discrete log problem, I consider that its difficulty is far above medium. If one really tries to find a solution by himself, this puzzle is more likely a very-hard one.

1 Like
#28

Ideally, there would be some kind or revision/versioning/wiki-like system for the community contributions.

And there would also be a clear definition of what to expect in each level of difficulty (because that’s obviously completely arbitrary since they introduced difficulty levels for community puzzles).

As for ECC, hard difficulty made sense to me as you need to know about some (multiplicative) modular arithmetic and in particular modular inversion. @nicola1 (I guess) added a sentence to point out that “modular division” before moving it to medium, which also makes sense.

1 Like
#29

The difficulty levels should be revised when the puzzle is a bit old and when it’s clear that the number of solvers is not in the current difficulty’s rate.
I downgraded the difficulty because finding a modular inverse is everywhere on the internet and because I found that warning about trivial modular operations (+×−) but not about division had no sense.

#30

I can’t seem to figure out why my code is only failing for the 75 houses case in the actual submission. Any suggestions as to why the 75 houses case would be the only one failing?

#31

@devusr1234 Maybe some incorrect initialization when House(0) > House(1)?

#32

Thanks for replying, the way I’ve implemented the algorithm, House(0) and House(1) should have the same value after going through it in that case. Maybe my approach is flawed?

E: I’ve figured it out, I did not properly deal with negatives for House(0) and House(1). Thanks.

#33

I don’t understand condition. For example, when:
a 1
b 15
c 10
d 13
e 16
why we take b and e, but don’t take d? Help me, please.

#34

@AlexRyzhenko You can’t visit two neighboring houses.

when he robs in a house he avoids the 2 houses aside (left and right).

If you take b, then you can’t take a and/or c. If you take e, you can’t take d.

3 Likes
#35

I can’t understand which algorithm I should use! Greedy algorithm give wrong answer when amount of houses is more than 20.

#36

Me neither!
I’ve thought about just taking the largest ones first, but that wouldn’t work in this case for example:
(a; 15), (b: 16), (c; 15) - Since b would be robbed first and a + c would stay unrobbed.
Then I thought about comparing it to it’s neighboors. But I can’t see how that would help. Any tips or tricks?

#37

@AlexRyzhenko & @Danrice: Don’t be greedy! Assuming you know how to solve a given case, ask yourselves what you would do if an extra house was added at the end of it.

NB: I moved the problem to medium again.

2 Likes
#38

I saw the problem as a binary tree and used a recursive function. It solved all cases but 75 and 100 houses because it takes too much time…

#39

Search space is too large for brute force to be successful. Review your recursive steps. Probably you are re-calculating values of House1 + House3 + … a million times before memory exhausted or time out.
You know how to get the answer for 3 houses. Can you reuse the partial result of 3 houses to get the solution for 4 houses? No need to re-calculate them all over again.

4 Likes
#40

Spent days finding solution with greedy and recursive algorithms but couldn’t bypass 2 test cases. At then end after googling for “dynamic algorithm examples” (while having couple of beers) and appropriate hints from Niako and java_coffee_cup…I was finally able to resolve the problem in less than 30 mins :-). Thinking of it now, I wonder why I couldn’t find this easy solution before …probably some dynamism was missing :smiley:

I did something like this:

  1. Identified max value of only the first house. Saved it in a list (no hard coding though)
  2. Identified max value of the first two houses. Saved it in a list. Expressed it in terms of the 2nd house value and value from item 1
  3. Identified max value of the first three houses. Saved it in a list. Expressed it in terms of the 3rd house value and value from item 2
  4. for i in 0 to n …expressed max values of each index in terms of its value and previous 2 indexes and saved max value of each index
  5. at the end print the max value of n-1 item from the saved list
  6. Treat negative houses as houses with 0 value
4 Likes