# Problems from KTH CSC Popup 2005

Submissions | Users | |||||||||
---|---|---|---|---|---|---|---|---|---|---|

Name | Total | Acc. | Ratio | Fastest | Total | Acc. | Ratio | Difficulty | ||

All Pairs Shortest Path | 6743 | 1195 | 18% | 0.02 | 801 | 552 | 69% | 6.0 | ||

Calculator | 885 | 283 | 32% | 0.00 | 254 | 200 | 79% | 4.1 | ||

Catalan Numbers | 1624 | 612 | 38% | 0.03 | 465 | 374 | 80% | 3.9 | ||

Chinese Remainder | 2034 | 487 | 24% | 0.00 | 359 | 266 | 74% | 5.7 | ||

Chinese Remainder Theorem (non-relatively prime moduli) | 1121 | 388 | 35% | 0.00 | 266 | 223 | 84% | 4.5 | ||

Closest Pair | 2439 | 430 | 18% | 0.06 | 293 | 155 | 53% | 7.7 | ||

Closest Pair (Uniform) | 2338 | 669 | 29% | 0.09 | 299 | 214 | 72% | 5.7 | ||

Convex Hull | 3257 | 799 | 25% | 0.01 | 578 | 384 | 66% | 6.0 | ||

Eulerian Path | 1471 | 473 | 32% | 0.01 | 221 | 170 | 77% | 5.9 | ||

Linear Equation Solver | 1249 | 396 | 32% | 0.01 | 162 | 118 | 73% | 6.9 | ||

Line Segment Distance | 788 | 295 | 37% | 0.00 | 199 | 168 | 84% | 4.3 | ||

Line Segment Intersection | 1314 | 283 | 22% | 0.00 | 169 | 125 | 74% | 6.8 | ||

Maximum Flow | 3879 | 1268 | 33% | 0.01 | 524 | 371 | 71% | 6.3 | ||

Maximum Number of Colinear Points | 710 | 256 | 36% | 0.14 | 150 | 123 | 82% | 5.4 | ||

Minimum Cost Maximum Flow | 1419 | 513 | 36% | 0.02 | 213 | 175 | 82% | 5.6 | ||

Minimum Spanning Tree | 4586 | 1165 | 25% | 0.05 | 696 | 550 | 79% | 4.4 | ||

Modular Arithmetic | 828 | 448 | 54% | 0.00 | 276 | 252 | 91% | 2.8 | ||

Partial Linear Equation Solver | 802 | 164 | 20% | 0.01 | 108 | 65 | 60% | 8.3 | ||

Point in Polygon | 1690 | 455 | 27% | 0.00 | 295 | 231 | 78% | 5.9 | ||

Polygon Area | 2804 | 1079 | 38% | 0.00 | 872 | 752 | 86% | 2.9 | ||

Prime Sieve | 5062 | 1575 | 31% | 0.00 | 937 | 662 | 71% | 5.4 | ||

Rational Arithmetic | 2787 | 887 | 32% | 0.00 | 646 | 547 | 85% | 3.3 | ||

Single source shortest path, negative weights | 3827 | 815 | 21% | 0.01 | 485 | 342 | 71% | 5.7 | ||

Single source shortest path, non-negative weights | 7741 | 2360 | 30% | 0.02 | 1148 | 928 | 81% | 3.4 | ||

Single source shortest path, time table | 1945 | 627 | 32% | 0.01 | 382 | 317 | 83% | 3.8 | ||

String Matching | 3967 | 1137 | 29% | 0.01 | 729 | 540 | 74% | 4.9 | ||

String Multimatching | 1562 | 456 | 29% | 0.18 | 192 | 130 | 68% | 7.0 | ||

Suffix Sorting | 1268 | 526 | 41% | 0.03 | 208 | 166 | 80% | 5.8 |