# Problems from KTH CSC Popup 2005

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

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

All Pairs Shortest Path | 13408 | 2542 | 19% | 0.00 | 1619 | 1165 | 72% | 5.7 | ||

Calculator | 2262 | 807 | 36% | 0.00 | 732 | 603 | 82% | 3.6 | ||

Catalan Numbers | 3177 | 1251 | 39% | 0.00 | 940 | 777 | 83% | 3.8 | ||

Chinese Remainder | 4157 | 1107 | 27% | 0.00 | 755 | 574 | 76% | 5.4 | ||

Chinese Remainder Theorem (non-relatively prime moduli) | 2859 | 1045 | 37% | 0.00 | 686 | 578 | 84% | 3.9 | ||

Closest Pair | 4602 | 823 | 18% | 0.06 | 567 | 285 | 50% | 7.9 | ||

Closest Pair (Uniform) | 4496 | 1351 | 30% | 0.09 | 533 | 375 | 70% | 6.4 | ||

Convex Hull | 8609 | 2243 | 26% | 0.01 | 1476 | 1070 | 72% | 4.0 | ||

Eulerian Path | 3300 | 1013 | 31% | 0.01 | 463 | 357 | 77% | 6.0 | ||

Linear Equation Solver | 2621 | 796 | 30% | 0.01 | 329 | 246 | 75% | 6.5 | ||

Line Segment Distance | 1507 | 630 | 42% | 0.00 | 417 | 349 | 84% | 4.3 | ||

Line Segment Intersection | 3094 | 688 | 22% | 0.00 | 381 | 282 | 74% | 6.5 | ||

Maximum Flow | 9146 | 2722 | 30% | 0.01 | 1155 | 806 | 70% | 5.5 | ||

Maximum Number of Colinear Points | 1693 | 631 | 37% | 0.04 | 325 | 266 | 82% | 5.1 | ||

Minimum Cost Maximum Flow | 2687 | 934 | 35% | 0.02 | 390 | 313 | 80% | 5.2 | ||

Minimum Spanning Tree | 10739 | 2874 | 27% | 0.05 | 1542 | 1255 | 81% | 4.3 | ||

Modular Arithmetic | 2188 | 1062 | 49% | 0.00 | 682 | 590 | 87% | 3.3 | ||

Partial Linear Equation Solver | 1650 | 309 | 19% | 0.01 | 200 | 132 | 66% | 7.5 | ||

Point in Polygon | 4059 | 1080 | 27% | 0.00 | 617 | 479 | 78% | 5.9 | ||

Polygon Area | 5265 | 2110 | 40% | 0.00 | 1612 | 1401 | 87% | 2.9 | ||

Prime Sieve | 9997 | 3287 | 33% | 0.00 | 1700 | 1267 | 75% | 4.7 | ||

Rational Arithmetic | 5202 | 1714 | 33% | 0.00 | 1140 | 975 | 86% | 3.4 | ||

Single source shortest path, negative weights | 9138 | 2061 | 23% | 0.01 | 1099 | 809 | 74% | 4.8 | ||

Single source shortest path, non-negative weights | 17445 | 5417 | 31% | 0.02 | 2505 | 2094 | 84% | 3.5 | ||

Single source shortest path, time table | 3978 | 1393 | 35% | 0.01 | 791 | 685 | 87% | 3.6 | ||

String Matching | 7632 | 2465 | 32% | 0.01 | 1488 | 1136 | 76% | 4.2 | ||

String Multimatching | 4235 | 1051 | 25% | 0.10 | 493 | 325 | 66% | 7.3 | ||

Suffix Sorting | 2612 | 919 | 35% | 0.03 | 435 | 334 | 77% | 5.6 |