# Problems from KTH CSC Popup 2005

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

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

All Pairs Shortest Path | 7126 | 1271 | 18% | 0.02 | 854 | 600 | 70% | 5.6 | ||

Calculator | 970 | 330 | 34% | 0.00 | 289 | 231 | 80% | 4.0 | ||

Catalan Numbers | 1761 | 655 | 37% | 0.03 | 500 | 405 | 81% | 3.9 | ||

Chinese Remainder | 2186 | 538 | 25% | 0.00 | 382 | 288 | 75% | 5.3 | ||

Chinese Remainder Theorem (non-relatively prime moduli) | 1248 | 447 | 36% | 0.00 | 300 | 254 | 85% | 4.2 | ||

Closest Pair | 2583 | 488 | 19% | 0.06 | 318 | 172 | 54% | 7.5 | ||

Closest Pair (Uniform) | 2486 | 736 | 30% | 0.09 | 311 | 225 | 72% | 5.6 | ||

Convex Hull | 3577 | 915 | 26% | 0.01 | 650 | 443 | 68% | 5.3 | ||

Eulerian Path | 1524 | 500 | 33% | 0.01 | 231 | 180 | 78% | 5.8 | ||

Linear Equation Solver | 1392 | 429 | 31% | 0.01 | 172 | 128 | 74% | 6.7 | ||

Line Segment Distance | 878 | 349 | 40% | 0.00 | 224 | 191 | 85% | 4.2 | ||

Line Segment Intersection | 1490 | 339 | 23% | 0.00 | 186 | 141 | 76% | 6.6 | ||

Maximum Flow | 4300 | 1370 | 32% | 0.01 | 564 | 394 | 70% | 6.3 | ||

Maximum Number of Colinear Points | 805 | 305 | 38% | 0.05 | 168 | 141 | 84% | 5.0 | ||

Minimum Cost Maximum Flow | 1477 | 528 | 36% | 0.02 | 218 | 179 | 82% | 5.5 | ||

Minimum Spanning Tree | 5079 | 1295 | 25% | 0.05 | 769 | 611 | 79% | 4.2 | ||

Modular Arithmetic | 930 | 522 | 56% | 0.00 | 307 | 283 | 92% | 2.7 | ||

Partial Linear Equation Solver | 808 | 165 | 20% | 0.01 | 111 | 66 | 59% | 8.3 | ||

Point in Polygon | 1893 | 523 | 28% | 0.00 | 322 | 259 | 80% | 5.6 | ||

Polygon Area | 3029 | 1176 | 39% | 0.00 | 933 | 805 | 86% | 2.9 | ||

Prime Sieve | 5475 | 1772 | 32% | 0.00 | 986 | 703 | 71% | 5.3 | ||

Rational Arithmetic | 2894 | 922 | 32% | 0.00 | 665 | 565 | 85% | 3.2 | ||

Single source shortest path, negative weights | 4117 | 886 | 22% | 0.01 | 518 | 364 | 70% | 6.0 | ||

Single source shortest path, non-negative weights | 8557 | 2687 | 31% | 0.02 | 1318 | 1085 | 82% | 3.1 | ||

Single source shortest path, time table | 2216 | 719 | 32% | 0.01 | 431 | 360 | 84% | 3.9 | ||

String Matching | 4330 | 1302 | 30% | 0.01 | 789 | 597 | 76% | 4.5 | ||

String Multimatching | 1722 | 524 | 30% | 0.18 | 223 | 156 | 70% | 6.7 | ||

Suffix Sorting | 1373 | 568 | 41% | 0.03 | 223 | 178 | 80% | 5.8 |