Lattice Quadrilaterals on Project Euler

http://projecteuler.net/problem=453

by aabalkan • 12 years ago

21 19 12 years ago

projecteuler.net

throwaway_yy2Di7• 12 years ago

Suggestion: use rot13 if you say anything potentially spoiler-y.

throwaway_yy2Di7• 12 years ago

Frgf bs sbhe cbvagf ba gur ynggvpr qvivqr vagb sbhe qvfgvapg tebhcf:

1) Gubfr jvgu n ercrngrq cbvag

2) Gubfr jvgu ng yrnfg bar tebhc bs cbvagf ylvat pbyvarne

3) Gubfr jvgu bar cbvag va gur (fgevpg) vagrevbe bs n gevnatyr bs gur bgure guerr

4) Gubfr juvpu ner rdhny gb gurve pbairk uhyy

Lbh genafvgvba sebz (3) gb (4) ol zbivat gur vagrevbe cbvag bhg hagvy vg uvgf gur rqtr bs gur gevnatyr (glcr (2))), naq shegure hagvy vg rkgraqf gur pbairk uhyy, vagb n dhnqevygreny (4).

throwaway_yy2Di7• 12 years ago

Gubfr bs glcr (4) lvryq bar cbyltba bs gur glcr gur ceboyrz fcrpvsvrf -- n pbairk dhnqevyngreny. Nalguvat ryfr jbhyq sbepr n yvar pebffvat.

Gubfr bs glcr (3) nqzvg rknpgyl guerr cbyltbaf (aba-pbairk).

(1) naq (2) tvir lbh abguvat.

gizmo686• 12 years ago

Speaking of rot13, why is it in the bsdgames package?

thearn43• 12 years ago

Basically, you're looking for the rectangular equivalent of A189414 (http://oeis.org/A189414).

Tricky problem, even for PE. I started to retool some earlier success with it towards a quasi-DP approach, but have since got caught up in other things.

Bootvis2• 12 years ago

I've solved about 60 problems on Project Euler but I've no clue about problems where a mod suddenly shows up in the question. How do these type of questions work?

thearn43• 12 years ago

Usually, it either implies a possible simplification step (using something like Fermat's little theorem), or its to reduce a huge answer to a range that can feasibly be pasted into the input element on their site.

Bootvis2• 12 years ago

Thanks, I was thinking that mathematical techniques were used that I would never understand but this seems doable.

Someone• 12 years ago

It also may mean that there is some recurrence relation in a sequence that

For example, the Fibonacci sequence, taken modulo 3 repeats every 8 numbers:

   1  1  2  3  5  8 13 21 34 55 89
   1  1  2  0  2  2  1  0  1  1  2

That makes it easy to answer such questions as "What is fib(3567^368857) mod 3?". Just compute 3567^368857 mod 8, and be careful to do the lookup right.

huherto• 12 years ago

The obvious part. Calculate the result and get the mod. Use that as a response.

But probably the result is such a big number that you will not be able to calculate. That is where you to look for a trick to only calculate the mod. May be ignoring significant numbers as you do the calculation.

omn123• 12 years ago

Consider, for example, calculating binomial coefficients mod a large number.

It's not hard to realise that C(n,k+1) = (n-k)C(n,k)/(k+1) is one way to write the binomial coefficients. So if we want to compute C(10^10,50309) mod 10^8, for example, we only ever really need to carry numbers mod 10^8 around. And since (ab) mod c = (a mob c)(b mod c) we can avoid obtaining really large numbers and can safely hold them in unsigned long ints.

Since this problem is counting things, there is mostly like a recurrence-type relationship to it and at each step you would take the result mod N. Many combinatorics problems are like this. Although if you've only done 60 PE problems, then the ones in the 400s somewhat implicitly assume you've done the previous 400 since the ideas do built up.

ClayFerguson2• 12 years ago

Traveling Salesman Problem... Will this algorithm work?

Algorithm:

1) Take a square space and divide it into 4 squares.

2) Find all 94 quadrilaterals that the 'nodes' can form.

3) For each quadrilateral, that has points in common with the original, do recursion (I.e. go to step #1 for each of the 94)

4) Keep repeating until some minimal square size (resolution) is reached.

Find the path with the shortest 'Error' and that's an approximation to the traveling salesman problem.

'Error' is defined as the sum of the distances of all travel waypoints to the nearest quadrilateral path line.

ClayFerguson2• 12 years ago

Mind blower #2: How many different shapes can a brain with 4 neurons recognize? 94. Evolution of vision neurons actually would have started out using a "chance built" circuit that could solve this 94-item 'recognition' problem. Then the DNA that solved the 94 would run repeatedly to recursively form the rest of the retina, giving the brain higher resolution, but using only one 94-pattern-solving DNA recursively. I think the major advancements in neural nets will come about once we start "wiring up" brains in interesting ways like this rather than the current "layer training" approach...The brain is recursive, and needs recursive wiring to be simulated.

susi22• 12 years ago

Btw, the problem was solved by 61 people so far.

Random thoughts:

I think the mod is just there to distract or for hinting that you shouldn't come up with a brute force method.

Observations:

1. Assume an infinite grid. Add 3 random points _not_ on a line. Clearly, they'll be a convex set (a triangle).

2. Add a 4th point such that it is not on an existing line.

You've now a quadrilateral.

So for the case of Q(2,2) = 94 = choose(9,4) - 32. 32 is the number of points that would make 3 of the 4 points lie on a line.

Come up with a recurrence relations and solve it.

throwaway_yy2Di7• 12 years ago

You've now a quadrilateral.

Or possibly three. If one point is in the interior of the other three, you get three different, nonconvex quadrilaterals.

Lattice Quadrilaterals on Project Euler

Related Stories