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.
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.
Rahzrengvat gur pnfrf; nal sbhe cbvagf qrsvar n erpnagthyne "uhyy":
[(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).
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?
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.
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.
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.
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.
