Lattice Quadrilaterals on Project Euler
projecteuler.net
projecteuler.net
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.
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).
Gubfr bs glcr (3) nqzvg rknpgyl guerr cbyltbaf (aba-pbairk).
(1) naq (2) tvir lbh abguvat.
Bs pbhefr vg'f rnfl gb nppbhag sbe genafyngvba: gurer'f (O+1-N) genafyngvbaf bs fbzrguvat bs jvqgu N va na vagreiny bs jvqgu O. Fb (oebnqyl), lbh pna pbhag gur cbffvovyvgvrf vaibyivat jvqgu-N bowrpgf, naq whfg zhygvcyl gung pbhag ol O+1-N.
Njrfbzr - guvf jnf rknpgyl jung zl ynfg gubhtugf jrer ba gung.
[(zva n_k, znk_k)] K [zva n_l, znk n_l)]
('n' enatvat bire gur sbhe cbvagf)
Va gur pnfrf bs vagrerfg (3) be (4), ng yrnfg guerr bs gur cbvagf yvr ba gur rkgrevbe rqtr bs guvf uhyy. Vs (naq bayl vs) nyy sbhe qb, vg'f pnfr (4). Gur pbhag bs cbyltbaf sebz guvf vf fvzcyl gur pbhag bs havdhr frgf bs 4-cbvagf ylvat ba fhpu erpgnatyrf (pbzovangbevny sbezhyn: ovt grez vf N^2 O^2 (bar ba rnpu rqtr -- # vf whfg gur cebqhpg bs rqtr yratguf), cyhf gur pnfrf jurer cnvef bs cbvagf ner ba gur fnzr rqtr (funer k- be l-) (cbffvoyl gjb cnvef -- guvax (2,0) (1,0) (0,1) (0,2)), zvahf gur pnfrf jurer gurl uvg gur fnzr pbeare).
Va gur bgure pnfr, (3), guerr bs gur cbvagf ner ba gur erpgnatyr uhyy (cbffvoyl jvgu n cnve ba gur fnzr rqtr). Va rnpu pnfr, gur vagrevbe ertvba vf gur fhz+qvssrerapr bs frireny evtug gevnatyrf. Fb vs jr xrrc n ybbxhc gnoyr bs gur ~83 zvyyvba eryrinag evtug gevnatyrf, jr unir na B(1) pnyphyngvba sbe gur # bs cbvagf ba gur vagrevbe. (Jr trg guerr fbyhgvba cbyltbaf sbe rnpu bs gubfr, bar sbe rnpu cbvag vafvqr gur erpgnatyr ohg bhgfvqr gur gevnatyr, naq abar sbe gur barf juvpu yvr ba na rqtr).
Fb gung'f n fznyy B(1) pnyphyngvba sbe rnpu erpgnatyr. Jr pna whfg rahzrengr guebhtu nyy erpgnatyr fvmrf (nyfb ~83 zvyyvba) naq gung'f vg.
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.
Or possibly three. If one point is in the interior of the other three, you get three different, nonconvex quadrilaterals.
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.
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
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.
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.