Can someone solve this Competitive Programming Problem in Elixir?

Questions / Help
1

I challenged this problem with Elixir, but my code is display TLE (TLE is runtime over. runtime should be less than 2.0s).

My code is here.

I want to add an element to the end of the list fast and flip that list (to pop the maximum value in the list)

Do you have any good ideas?

1 Like
2

I haven’t had my coffee yet, but an idea: yeah that append_tail function smells, I wouldn’t be happy with a single Enum.reverse inside an hot loop, but two!

What about keeping the lists in the wrong order, so append_tail becomes prepend_head which is a simple [element | list], and you do reversing at the end of the tail loop? I imagine where you’re doing Enum.sum(as) + Enum.sum(acc) would be a good place.

Usually works for me whenever I’m manipulating lists: they’re the wrong order until they’re returned to the caller.

3

Instead of:

def append_and_recurse([h | t], m), do: append_and_recurse(append(t, f(h)), m-1)

"recurse with t and then f(h)"

def recurse_then_reverse([h | t], m), do: recurse_then_reverse([h | t], [], m)
def recurse_then_reverse([h | t], rest, m), do: recurse_then_reverse(t, [f(h) | rest], m-1)
def recurse_then_reverse([], rest, m), do: recurse_then_reverse(Enum.reverse(rest), m)

This keeps the list of “things to evaluate next” in reverse order until the first list is empty, then uses a single Enum.reverse.

Take a look at the Erlang stdlib’s :queue module for references and more examples of this approach.

1 Like
4

Thank you for your reply and good information!!

I have rewritten my code to use :queue, then the execution completed in time :sparkles:

1 Like