# Problems from KTH CSC Popup 2005

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

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

All Pairs Shortest Path | 7271 | 1293 | 18% | 0.02 | 870 | 612 | 70% | 5.8 | ||

Calculator | 992 | 340 | 34% | 0.00 | 299 | 239 | 80% | 4.1 | ||

Catalan Numbers | 1798 | 669 | 37% | 0.03 | 509 | 414 | 81% | 3.7 | ||

Chinese Remainder | 2246 | 541 | 24% | 0.00 | 385 | 289 | 75% | 5.4 | ||

Chinese Remainder Theorem (non-relatively prime moduli) | 1330 | 472 | 35% | 0.00 | 320 | 267 | 83% | 4.3 | ||

Closest Pair | 2635 | 494 | 19% | 0.06 | 326 | 175 | 54% | 7.7 | ||

Closest Pair (Uniform) | 2504 | 742 | 30% | 0.09 | 315 | 230 | 73% | 5.6 | ||

Convex Hull | 3785 | 977 | 26% | 0.01 | 699 | 483 | 69% | 5.1 | ||

Eulerian Path | 1539 | 502 | 33% | 0.01 | 234 | 182 | 78% | 5.9 | ||

Linear Equation Solver | 1415 | 434 | 31% | 0.01 | 173 | 130 | 75% | 6.6 | ||

Line Segment Distance | 885 | 353 | 40% | 0.00 | 228 | 194 | 85% | 4.2 | ||

Line Segment Intersection | 1496 | 341 | 23% | 0.00 | 188 | 142 | 76% | 6.6 | ||

Maximum Flow | 4746 | 1546 | 33% | 0.01 | 619 | 444 | 72% | 5.9 | ||

Maximum Number of Colinear Points | 834 | 312 | 37% | 0.05 | 172 | 145 | 84% | 5.0 | ||

Minimum Cost Maximum Flow | 1507 | 545 | 36% | 0.02 | 231 | 190 | 82% | 5.6 | ||

Minimum Spanning Tree | 5214 | 1320 | 25% | 0.05 | 787 | 624 | 79% | 4.4 | ||

Modular Arithmetic | 944 | 532 | 56% | 0.00 | 314 | 290 | 92% | 2.7 | ||

Partial Linear Equation Solver | 817 | 167 | 20% | 0.01 | 112 | 67 | 60% | 8.3 | ||

Point in Polygon | 1958 | 543 | 28% | 0.00 | 336 | 271 | 81% | 5.5 | ||

Polygon Area | 3114 | 1216 | 39% | 0.00 | 967 | 836 | 86% | 2.8 | ||

Prime Sieve | 5622 | 1816 | 32% | 0.00 | 1005 | 720 | 72% | 5.0 | ||

Rational Arithmetic | 2925 | 938 | 32% | 0.00 | 673 | 573 | 85% | 3.2 | ||

Single source shortest path, negative weights | 4232 | 906 | 21% | 0.01 | 530 | 371 | 70% | 6.0 | ||

Single source shortest path, non-negative weights | 8782 | 2773 | 32% | 0.02 | 1363 | 1125 | 83% | 3.1 | ||

Single source shortest path, time table | 2223 | 722 | 32% | 0.01 | 434 | 362 | 83% | 3.9 | ||

String Matching | 4388 | 1321 | 30% | 0.01 | 801 | 608 | 76% | 4.5 | ||

String Multimatching | 1752 | 531 | 30% | 0.18 | 227 | 158 | 70% | 6.7 | ||

Suffix Sorting | 1390 | 579 | 42% | 0.03 | 228 | 182 | 80% | 5.7 |