# Problems from KTH CSC Popup 2005

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

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

All Pairs Shortest Path | 9060 | 1613 | 18% | 0.00 | 1112 | 785 | 71% | 5.7 | ||

Calculator | 1309 | 491 | 38% | 0.00 | 433 | 362 | 84% | 3.3 | ||

Catalan Numbers | 2227 | 849 | 38% | 0.02 | 642 | 530 | 83% | 3.6 | ||

Chinese Remainder | 2543 | 632 | 25% | 0.00 | 463 | 348 | 75% | 5.4 | ||

Chinese Remainder Theorem (non-relatively prime moduli) | 1873 | 638 | 34% | 0.00 | 431 | 371 | 86% | 3.7 | ||

Closest Pair | 3578 | 640 | 18% | 0.06 | 420 | 207 | 49% | 8.0 | ||

Closest Pair (Uniform) | 2825 | 824 | 29% | 0.09 | 381 | 272 | 71% | 5.8 | ||

Convex Hull | 4890 | 1276 | 26% | 0.01 | 947 | 662 | 70% | 4.8 | ||

Eulerian Path | 1851 | 604 | 33% | 0.01 | 280 | 222 | 79% | 5.6 | ||

Linear Equation Solver | 1631 | 490 | 30% | 0.01 | 204 | 156 | 76% | 6.5 | ||

Line Segment Distance | 1054 | 422 | 40% | 0.00 | 272 | 232 | 85% | 4.1 | ||

Line Segment Intersection | 1746 | 416 | 24% | 0.00 | 222 | 170 | 77% | 6.4 | ||

Maximum Flow | 6311 | 1988 | 32% | 0.01 | 777 | 539 | 69% | 6.3 | ||

Maximum Number of Colinear Points | 1081 | 416 | 38% | 0.04 | 219 | 183 | 84% | 4.9 | ||

Minimum Cost Maximum Flow | 1833 | 706 | 39% | 0.02 | 283 | 237 | 84% | 5.3 | ||

Minimum Spanning Tree | 7573 | 1913 | 25% | 0.05 | 1085 | 880 | 81% | 3.9 | ||

Modular Arithmetic | 1183 | 609 | 51% | 0.00 | 383 | 345 | 90% | 2.9 | ||

Partial Linear Equation Solver | 923 | 184 | 20% | 0.01 | 126 | 81 | 64% | 7.9 | ||

Point in Polygon | 2695 | 687 | 25% | 0.00 | 402 | 330 | 82% | 5.3 | ||

Polygon Area | 3651 | 1414 | 39% | 0.00 | 1147 | 994 | 87% | 2.8 | ||

Prime Sieve | 6909 | 2228 | 32% | 0.00 | 1199 | 876 | 73% | 4.4 | ||

Rational Arithmetic | 3414 | 1088 | 32% | 0.00 | 794 | 674 | 85% | 3.3 | ||

Single source shortest path, negative weights | 6035 | 1357 | 22% | 0.01 | 728 | 534 | 73% | 5.1 | ||

Single source shortest path, non-negative weights | 12240 | 3744 | 31% | 0.02 | 1836 | 1520 | 83% | 3.4 | ||

Single source shortest path, time table | 2569 | 836 | 33% | 0.01 | 513 | 431 | 84% | 3.8 | ||

String Matching | 5099 | 1555 | 30% | 0.01 | 978 | 735 | 75% | 4.4 | ||

String Multimatching | 2635 | 718 | 27% | 0.18 | 301 | 212 | 70% | 6.6 | ||

Suffix Sorting | 1614 | 647 | 40% | 0.03 | 267 | 216 | 81% | 5.5 |