But the solver count depends on the number of people who have seen it.

That is probably higher for easy problems.

# [Community Puzzle] Robbery optimisation

**eulerscheZahl**#21

**TheYoungPyro**#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) ?

**Niako**#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.

**JBM**#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.

**TheYoungPyro**#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.

**Stilgart**#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.

**Niako**#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.

**nicola1**#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.

**devusr1234**#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?

**devusr1234**#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.

**AlexRyzhenko**#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.

**Niako**#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**.

**AlexRyzhenko**#35

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

**Danrice**#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?

**Niako**#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.

**TheYoungPyro**#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âŚ

**java_coffee_cup**#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.

**Neel**#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

I did something like this:

- Identified max value of
**only**the first house. Saved it in a list (no hard coding though) - 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 - 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 - 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
- at the end print the max value of n-1 item from the saved list
- Treat negative houses as houses with 0 value