Hey everyone!
I haven't had much experience with problems that mainly require math(number theory, combinatorics, algebra, etc.) and am looking for a nice collection of such problems.
Thanks in advance :)
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
Hey everyone!
I haven't had much experience with problems that mainly require math(number theory, combinatorics, algebra, etc.) and am looking for a nice collection of such problems.
Thanks in advance :)
Name |
---|
Project euler?
ProjectEuler+ ?
Maybe projecteuler.net.
https://a2oj.com/category?ID=86
it is a collection of math problems on different websites .
On recent Insomnia quali. there were 3 math problems."Remember the name" was pure mathematical and too easy."Walter and Sklyer" had some simple combinatorial elements and finding modular inverse,nice medium problem in my opinion."Meth Cooking" also looks like mostly math problem but I came up with false conclusion on contest and after that couldn't make any progress :(
Total Meth was also a counting problem.
Good day to you,
well I found a few problems recently, but I can't guarantee that all will be "math you like" — anyway guess it won't harm anyone so here is a list:
Math & Number theory:
http://mirror.codeforces.com/contest/731/problem/F 4
12031 UVA (8)
http://mirror.codeforces.com/contest/722/problem/F (8)
http://mirror.codeforces.com/contest/716/problem/C 4
http://mirror.codeforces.com/contest/711/problem/E (8)
http://mirror.codeforces.com/contest/710/problem/D (6)
13154 (UVA) 7
13166 (UVA) 5
11962 (UVA) 2
11718 UVA 3
11510 UVA (5)
11538 UVA (3) //good one — just math
11556 UVA (1)
http://mirror.codeforces.com/contest/757/problem/E (8)
http://mirror.codeforces.com/contest/758/problem/F (7)
11481 UVA (4)
11237 UVA (4) //Nice — seems like knapsbag but it it not
11155 UVA (4) //Almost as previous problem
11038 UVA (3) //counting digits on interval
http://mirror.codeforces.com/contest/763/problem/C (7)
11087 UVA (4) //Sums of two numbers divisible with <=500 (10^5)
http://mirror.codeforces.com/contest/678/problem/C 2 //LCM
http://mirror.codeforces.com/problemset/problem/665/F (8) //p^3 | p*q
http://www.spoj.com/problems/LCMSUM/ //Vzorec v knihovničce
http://www.spoj.com/problems/FRNDZND/ (2) // (size 1 == 1, else 0)
http://www.spoj.com/problems/EXPOR/ //bit-by-bit (+ formula)
http://www.spoj.com/problems/FACTDIV/ (5) //dyn-update of ans/factors GOOD
http://www.spoj.com/problems/PAIRDIV/ (6) //cyka möbius -_-
http://www.spoj.com/problems/FCDC/ (4) //keep factorized factorial
http://www.spoj.com/problems/NTHPRIME/ (7) // BS + NumPrime GOOD!!
http://www.spoj.com/problems/DIVFACT3/ (7) // Sieve 10^8 + sqrt search
http://www.spoj.com/problems/DIVFACT4/ (8) // Prime count
http://mirror.codeforces.com/contest/776/problem/C (4) //segments div. by number
http://mirror.codeforces.com/contest/776/problem/E (6) //vypsat cisla: f(N)=Phi(N),g(N)=N
http://www.spoj.com/problems/PHT/ (2) //easy BS (NN+2N) mby math?
http://www.spoj.com/problems/GCDEX/ (7) //OEIS A006579 — enough [well imp]
http://www.spoj.com/problems/APS/ (3) //just sieve + generate
http://www.spoj.com/problems/WPC5I/ (3)//fc: C[a]!=C[b]:F[a]^max(C[a],C[b])
http://www.spoj.com/problems/SPEC_SET/ N→N/k→N/k/k
http://www.spoj.com/problems/DCEPC11B/ (5) //Wilson't theorem!
http://www.spoj.com/problems/FACTMULN/ (5) //each f[i]/c[i] separately
http://www.spoj.com/problems/SPCM/ (4) //just factorisation + prime check (10^12)
http://www.spoj.com/problems/TWOGAME/ (5) //gcd == Power of 3 => YES
http://www.spoj.com/problems/MKEQUAL/ (2) //Chceck if sum is divisible by N
http://www.spoj.com/problems/TIPTOP/ (3) //sqrt(N)==N? NICE!!
http://www.spoj.com/problems/PSYCHON/ (4) // fast factorisation
http://www.spoj.com/problems/ENIGMATH/ (1) // swap and div by gcd
http://www.spoj.com/problems/SNGPG/ (3) // prime gen + check
http://mirror.codeforces.com/contest/795/problem/A (2) //brute-force
http://mirror.codeforces.com/contest/801/problem/E (6) //NICE! — Clique-DAG + inversion
http://mirror.codeforces.com/contest/798/problem/C (4) //GCD == at the beginning OR 2
http://mirror.codeforces.com/contest/803/problem/C (3) //Only "low" K and just divisors
10830 (4) //simple add 2→ sqrt(N) + their mirrors
http://mirror.codeforces.com/contest/817/problem/A (2) //check division + parity
13209 UVA (3) //Simple simulation of division (+states rememberance)
http://mirror.codeforces.com/contest/834/problem/C (4) //Has cube-root + both num divisible by cuberoot
http://mirror.codeforces.com/contest/837/problem/E (5) //Factorisation + GCD attributes
http://www.spoj.com/problems/SUMMATION/ (3) //Number contribution: 2^(N-1)
http://www.spoj.com/problems/SECTORS/ (4) //Odd len OR sum of odd indices == sum of even
http://www.spoj.com/problems/IITKWPCM/ (6) //VERY NICE — Gauss's generalisation of Wilsons Theorem
http://www.spoj.com/problems/UCV2013A/ (4) //N*(N^L-1)/(N-1)
http://www.spoj.com/problems/KIMO1/ (4) //NICE — Adding/Subing by modulus
http://www.spoj.com/problems/AFS2/ (4) //Sum of divisort (sqrt(N)) — (+128int)
http://www.spoj.com/problems/FUNNUMS/ (4) //Permutations (get ith + guess ith)
Some combinatorics:
12001 UVA (3)
12034 UVA (4)
11719 UVA (5)
11798 UVA (5)
11282 UVA (4) //dearrangement
11174 UVA (4)
http://mirror.codeforces.com/contest/666/problem/C 7
http://www.spoj.com/problems/JOKER1/ 3 prod(Ai-i)
http://www.spoj.com/problems/ANTP/ //4
http://mirror.codeforces.com/contest/645/problem/E (5) //formula: A[i]=Sum(A)+1
http://www.spoj.com/problems/SPCE/ (5) // N^{K-2}*Prod(comp_size)
http://mirror.codeforces.com/contest/785/problem/D (5) // F'(' C"(+)-1","("
13184 UVA (3)
http://mirror.codeforces.com/contest/816/problem/D (5) // Observation
13214 (4) //OEIS? : C(N+M-2,N-1)
http://mirror.codeforces.com/contest/844/problem/B (2) //Easy — pro prvaky
http://www.spoj.com/problems/JOSWAP/ (3) //Frequence array
http://www.spoj.com/problems/UCV2013E/ (4) //NICE&EASY: Choose steps to direction
http://www.spoj.com/problems/PARCARD1/ (4) //Partition function (raw)
http://www.spoj.com/problems/GOODB/ (2) //Easy (NICE): Choose [order]
http://www.spoj.com/problems/LOOPEXP/ (4) //A000254/N!
http://www.spoj.com/problems/DTPOLY/ (5) //DP might work too
http://www.spoj.com/problems/DTPOLY2/ (7) //Harder version of above (NICE but hell)
Euler:
http://www.spoj.com/problems/NAJPWG/ 4 //Gauss-Euler
http://www.spoj.com/problems/DCEPC12G/ (5) //Do what is written there
Factorisation:
12005 UVA (7)
12062 UVA (6)
11960 UVA (3)
http://www.spoj.com/problems/FACTCG2/ (3)
http://www.spoj.com/problems/FACT0/ (4)
http://mirror.codeforces.com/contest/546/problem/D 5
http://mirror.codeforces.com/contest/222/problem/C 6
http://www.spoj.com/problems/COMDIV/ 3
http://www.spoj.com/problems/SINEGGS/ 3
http://www.spoj.com/problems/BDOI16B/ 4
http://www.spoj.com/problems/HG/ 4 //Map == OK
11099 UVA (3) //factor + recursion
13194 UVA (3) //factorize+generate /or just check
13191 UVA (6) //Pollard-Rho
http://mirror.codeforces.com/contest/818/problem/E (4) // Efficient + Two Pointers
http://mirror.codeforces.com/contest/831/problem/F (6) //MAGIC
http://mirror.codeforces.com/contest/839/problem/D (4) // Combinatorics + IE
http://www.spoj.com/problems/SAS002/ (5) //Find all divisors (big numbers)
http://www.spoj.com/problems/GCDS/ (4) //Lowest unused prime
http://www.spoj.com/problems/IITKWPCF/ (4) //Nonprime divisors of N/2
http://www.spoj.com/problems/PUCMMT02/ (7) //wrong bounds- but ll OK
Geometry:
12173 UVA 3
12194 UVA 4
11894 UVA 3
11769 UVA 7
11665 UVA 5
11509 UVA 4
11355 UVA 5
11265 UVA 6 //Nice one | polygon — cut/pt-check/area
11123 UVA 4 //Counting trapezoids
11177 UVA 6 //BS+Polygon/Circle intersection
11186 UVA 3
11008 UVA 5 //with DP → #intersected triangles
11012 UVA 5 //Nejvzdálenější body (Manhatton 3D)
11072 UVA 4 //Body v poly gonu
http://mirror.codeforces.com/problemset/problem/682/E 6 (biggest triangle)
http://mirror.codeforces.com/contest/672/problem/C 4 //easy — just think it up
http://mirror.codeforces.com/contest/667/problem/A 2 //vzorecky
http://mirror.codeforces.com/contest/793/problem/C 5 //EASY but beware of epsilons (NICE)
http://mirror.codeforces.com/contest/794/problem/B 2 //Can be done with BS
http://mirror.codeforces.com/contest/814/problem/D 5 //+DP on trees (NICE — but low geom.)
10750 UVA 3 //Closest points — try all pairs
http://mirror.codeforces.com/contest/820/problem/B 3 //Polygon angle find!
13213 UVA 5 //VERY NICE — Voronoi diagram (low constraints so not actually needed)
13215 UVA 3 //EASY — Sum areas and find side lengths
http://www.spoj.com/problems/IITKWPCC/ (5) //VERY VERY NICE — Nqrt(N)log(N)
http://www.spoj.com/problems/NNS/ (5) Closest points query [fake geometry] {__128}
Matrix expo.
11551 UVA (4)
11486 UVA (5)
10743 UVA (5) //A001169 [easy multi / hard to come with recurence]
http://mirror.codeforces.com/contest/821/problem/E (6) //Not trivial to come-up with matrix
Some sequences:
12004 UVA 2
11273 UVA 5 //https://oeis.org/A001088
11077 UVA 3 //https://oeis.org/A094638
http://www.spoj.com/problems/VECTAR5/ 3 //https://oeis.org/A038721
http://www.spoj.com/problems/ESYRCRTN/ 2 //generate and see
http://www.spoj.com/problems/IITWPC4B/ 3 //http://oeis.org/A005044
http://www.spoj.com/problems/POLCONST/ (4) //A003401+Fermat Number (Prime)
http://www.spoj.com/problems/CUTCAKE/ (3) // pattern [1 22 333 4444 55555]
10872 UVA 3 //Alcuin's Sequence
Prime testing:
http://www.spoj.com/problems/ABA12A/ (3)
10871 UVA (3) //Easy — fermat not necessary
http://www.spoj.com/problems/POP1/ (4) //Fast primality testing (or somehow)
http://www.spoj.com/problems/POP2/ (5) //NICE — same as above (yet with ll)
http://www.spoj.com/problems/POP3/ (6) //same as above (yet with big)
Additional:
http://www.spoj.com/problems/ADATEAMS/
http://www.spoj.com/problems/ADAHACK/
http://www.spoj.com/problems/ADAHW/
http://www.spoj.com/problems/ADADUNG/
http://www.spoj.com/problems/ADAGCD/
http://www.spoj.com/problems/ADACAROT/
http://www.spoj.com/problems/ADAPICK/
http://www.spoj.com/problems/ADAGIFT/
http://www.spoj.com/problems/ADAPANEL/
I'm sorry but it is hard for me to guess what is/isn't math :'(
Anyway this is the list — so feel free to ignore the comments :P
Have nice day,
Good Luck to you!
~/Morass
* Sploosh *
The longest comment i have ever seen :)
I was very surprised that there are no topcoder problems in the very very long comment. Why? Topcoder has many mathematics-like problems.
Well,
I'm not a clever guy, so I wasn't able to manage to create account + the software (anyhow) on topcoder ... so I didn't solve any problems out there :/
With round 432 it looks like you are in luck.
I already gave the IndiaHacks finals, so I can't.