We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #68: Magic N-gon ring
Project Euler #68: Magic N-gon ring
Sort by
recency
|
10 Discussions
|
Please Login in order to post a comment
I have a question about how many digits to employ. Given n & s, how do i know how many digits to use? In the example, it indicated only 1-6 digits.
I first sorted results in numerical order, failing test cases # 5, 8, 9, and 11-21. Then I read the problem description again, found that results should be sorted in alphabetical order, which let me pass all of the test cases.
Another one of those problems where I started to invent a "rocket ship" when actually there was no need for. Thus I would advise to make a solution you know will work for small n-s and it might just happen that you find out that it works for larger n-s as well.
Is there any trick to quickly get the sequence of inner elements given their corresponding sum? (e.g. given the sums
5 4 3
, results in2, 3; 3, 1; 1, 2
)Previously without such method, my implementation uses permutations to generate inner sequence which is very slow. For it runs like forever.
EDIT: Got a function to generate the inner sequence. This function starts with picking (from the chosen inner elements) two valid elements according to their sum, and use them as the first two elements of the inner sequence, and then all the rest can be calculated based on the outer sequence (if it exists). But the problem with this method is that plenty of time is wasted on invalid set of chosen inner elements, where it can only be quitted when it hits the end of the loop.
Still getting TLE #13 to #21 (with Pypy, #15 to #21). Could I be completely wrong from the very beginning to start with multichoosing outer elements? I already have a guard to skip choices of outer sequence which does not satisfy
sum(outer) == 2 * N * (2 * N + 1) - S * N
, but still no hope.EDIT 2: Finally cleared everything without switching to another language. As it turns out, if we start over and get rid of the mindset from the original problem, it's not that difficult.
The key insight here is to think about the triplets and combinations at the same time (somehow a hybrid method). I first generate an array of valid triplets (whose index is the sum of the 3 elements) similar to how we generate a list of factors of composite numbers.
We are concerned only about
triplets[S]
. Based on the multichoose combinations of the outer sequence and thesum(outer) == 2 * N * (2 * N + 1) - S * N
condition, we getouter
andinner
without knowing their positions yet, exceptouter[0]
.To make it more clear, I also created
out_triplets
whose elements are list of[inn1, inn2]
andinn_triplets
whose elements are list of[out, inn2]
. Then we use adeque()
which starts by appending elements fromout_triplets[outer[0]]
(bothout, inn1, inn2
andout, inn2, inn1
).After that, we can use the last
inn2
frompopleft()
as the index ofinn_triplets
to find all the valid (there's some conditions to it, such as no repeatingout
, no repeatinginn2
except if it is the last element etc) nextout, inn1, inn2
to add to the queue. When the sequence we get frompopleft()
is of desirable length, add it to theanswers
pool and don't add it to the queue. Repeat untill the queue is empty. Then do that again with another multichoose combination with brand newout_triplets
andinn_triplets
...This implementation may look complicated, but once you get it straight, it is sort of clean and beautiful. The slowest test I got was 1.82s #21, and it is Python 2! That's of comparable speed to another C++ solution I found on the web.
And if you got WA #18, #20 and #21, make sure you sort the answers after joining them as string, not before joining.
EDIT 3: It's a solid 0.64s with Pypy. Fantastic.
I suggest looking at this link to get a clearer picture of what an N-gon ring looks like for N > 3, and which numbers are used for the N-gon ring. https://projecteuler.net/problem=68