0

The problem for Advent of Code Day 19 is specified as follows:

Elves numbered 1 to N sit in a circle. Each Elf brings a present. Then, starting with the first Elf, they take turns stealing all the presents from the Elf to their left. An Elf with no presents is removed from the circle and does not take turns. So, if N = 5, then:

  • Elf 1 takes Elf 2's present.
  • Elf 2 has no presents and is skipped
  • Elf 3 takes Elf 4's present.
  • Elf 4 has no presents and is also skipped.
  • Elf 5 takes Elf 1's two presents.
  • Neither Elf 1 nor Elf 2 have any presents, so both are skipped.
  • Elf 3 takes Elf 5's three presents, ending the game.

Who ends up with all the presents for general case of N?

After solving these problems, I always like to look at other's solutions to learn some new tricks. One of those solutions I read through was Peter Norvig's solution here, and I noticed he mentions deleting from the list for each elf whose presents are taken is O(N^2).

Empirically this makes sense because that's basically what I did and my solution was painfully slow, but I thought that deleting from a list, assuming linked list, was O(N) (or specifically O(N) to iterate to the point of deletion, and O(1) for the actual deletion).

My knowledge here is obviously lacking and I would greatly appreciate if anybody could help me understand a bit better how this is O(N^2). I can kind of see how it would be the case if you are deleting, and then after each deletion, trying to search from the beginning of the list again for the next elf, because in that case you have a cost of N for each deletion and N again to search for the next elf so N^2 total. What I was doing though was keeping a counter of where I was in the list, deleting an elf, and then iterating the counter to the next position. In that case I would expect to incur N cost for deletion, but not for indexing (maybe this is where I'm wrong, the indexing cost).

Endzeit
  • 4,810
  • 5
  • 29
  • 52
Solaxun
  • 2,732
  • 1
  • 22
  • 41
  • Looks like the Josephus Problem with k=2; see https://en.wikipedia.org/wiki/Josephus_problem#k.3D2 – m69's been on strike for years Oct 05 '17 at 01:07
  • With a linked list and k=2, it would take N steps for the first N/2 deletions, then N/2 for the next N/4 deletions, then N/4, N/8, and so on... That would result in 2xN, not N². The general case on the other hand, where k is not necessarily 2, would be N² when done with a linked list; maybe that's where the confusion comes from? – m69's been on strike for years Oct 05 '17 at 01:13
  • its definitely the Josephus problem, and I solved it, just very inefficiently. I'm more interested in a walk-through of how it's N^2 to successively delete one elf at a time until you have the last elf, to further my understanding. – Solaxun Oct 05 '17 at 01:56
  • If you consider k=2 to be a constant, then it takes 2xN steps, or O(N). If you want to be strict about it and consider k=2 to be a variable, then k could be anything up to N, and it could take up to NxN steps, and be O(N²). I guess it just depends on whether you see the k=2 case as a seperate algorithm, or as a specific case of the general algorithm with 0 – m69's been on strike for years Oct 05 '17 at 02:06
  • Btw, here are some examples of N.logN solutions if you want to generate the complete sequence, and not just calculate who will be left over at the end: https://stackoverflow.com/questions/43504632/take-every-k-th-element-from-the-1-n-natural-numbers-series/ – m69's been on strike for years Oct 05 '17 at 02:46

0 Answers0