- #1

RaamGeneral

- 50

- 1

- TL;DR Summary
- given a list of integers, find the minimum value of a certain property given by pairing the elements

Hello. Sorry if the title is a bit vague.

I'm doing this challenge (google foobar) and even though it's not very elegant to ask for help, it's not like I'm going to win any kind of prize for it. In any case I'd like some suggestions since my current solution fails 2 tests on 5. The most probable reasons might be:

- the algorithm is not correct (maybe it doesn't correctly evaluate some cases)

- the algorithm is too slow, which I'm pretty sure it is.

Given any two integers ##a## and ##b##, suppose that ##a<b##, and consider the function ##f(a,b)=(2a, b-a)##. There are certain pairs such that repeated applications of ##f## produce a loop of results. I discovered that this does not happen when $$\frac{a}{a+b}=\frac{\mathrm{odd_number}}{2^k}$$ with ##a/(a+b)## reduced to their lowest terms: in this case I say that the pair (two elements) ends up in a draw.

The problem: you're given a list of non negative integers and must find the minimum amount of draws possible. I suppose that if the list contains an odd number of elements, one will never be paired and may be considered a draw too (one element).

For this problem I couldn't get a better algorithm than this one, although I tried a few other ways which made not much difference in run time (for certain cases).

I tried to avoid creating new lists (new_seq) and other "traversal strategies", but actually I'm still not sure where (if) the trick is (maybe to decrease the amount of possible checks/computations to make). I kind of see that this problems may have something to do with graphs or trees, but I don't find it simple to visualize the correct structure. I also have found a "matrix" representation, but again I'm not sure how to best manipulate such matrix to achieve the result.

A small suggestion is welcome. Thank you.

I'm doing this challenge (google foobar) and even though it's not very elegant to ask for help, it's not like I'm going to win any kind of prize for it. In any case I'd like some suggestions since my current solution fails 2 tests on 5. The most probable reasons might be:

- the algorithm is not correct (maybe it doesn't correctly evaluate some cases)

- the algorithm is too slow, which I'm pretty sure it is.

Given any two integers ##a## and ##b##, suppose that ##a<b##, and consider the function ##f(a,b)=(2a, b-a)##. There are certain pairs such that repeated applications of ##f## produce a loop of results. I discovered that this does not happen when $$\frac{a}{a+b}=\frac{\mathrm{odd_number}}{2^k}$$ with ##a/(a+b)## reduced to their lowest terms: in this case I say that the pair (two elements) ends up in a draw.

The problem: you're given a list of non negative integers and must find the minimum amount of draws possible. I suppose that if the list contains an odd number of elements, one will never be paired and may be considered a draw too (one element).

For this problem I couldn't get a better algorithm than this one, although I tried a few other ways which made not much difference in run time (for certain cases).

Python:

```
def find_least_draws(seq):
n = len(seq)
if n <= 1:
return n
R = n
for i in range(1, n):
if seq[0] == seq[i]:
continue
# it returns 0 or 2
A = does_draw(seq[0], seq[i])
new_seq = [el for j, el in enumerate(seq) if j != 0 and j != i]
B = find_least_draws(new_seq)
C = A + B
if C == n % 2:
return C
if C < R:
R = C
return R
```

I tried to avoid creating new lists (new_seq) and other "traversal strategies", but actually I'm still not sure where (if) the trick is (maybe to decrease the amount of possible checks/computations to make). I kind of see that this problems may have something to do with graphs or trees, but I don't find it simple to visualize the correct structure. I also have found a "matrix" representation, but again I'm not sure how to best manipulate such matrix to achieve the result.

A small suggestion is welcome. Thank you.