# Problems from KTH CSC Popup 2005

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

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

All Pairs Shortest Path | 6130 | 1056 | 17% | 0.02 | 728 | 507 | 70% | 5.8 | ||

Calculator | 809 | 253 | 31% | 0.00 | 239 | 185 | 77% | 4.4 | ||

Catalan Numbers | 1565 | 593 | 38% | 0.03 | 447 | 359 | 80% | 3.9 | ||

Chinese Remainder | 1827 | 424 | 23% | 0.00 | 320 | 230 | 72% | 5.7 | ||

Chinese Remainder Theorem (non-relatively prime moduli) | 814 | 325 | 40% | 0.00 | 224 | 185 | 83% | 4.8 | ||

Closest Pair | 2379 | 416 | 17% | 0.06 | 282 | 148 | 52% | 7.7 | ||

Closest Pair (Uniform) | 2296 | 652 | 28% | 0.09 | 284 | 200 | 70% | 5.8 | ||

Convex Hull | 3097 | 764 | 25% | 0.01 | 542 | 360 | 66% | 6.1 | ||

Eulerian Path | 1227 | 387 | 32% | 0.01 | 187 | 142 | 76% | 6.0 | ||

Linear Equation Solver | 971 | 305 | 31% | 0.01 | 144 | 105 | 73% | 6.8 | ||

Line Segment Distance | 686 | 283 | 41% | 0.00 | 188 | 160 | 85% | 4.4 | ||

Line Segment Intersection | 1260 | 268 | 21% | 0.00 | 161 | 121 | 75% | 6.8 | ||

Maximum Flow | 3358 | 1056 | 31% | 0.01 | 481 | 333 | 69% | 6.5 | ||

Maximum Number of Colinear Points | 706 | 252 | 36% | 0.14 | 149 | 122 | 82% | 5.4 | ||

Minimum Cost Maximum Flow | 1317 | 459 | 35% | 0.03 | 196 | 160 | 82% | 5.8 | ||

Minimum Spanning Tree | 3554 | 933 | 26% | 0.05 | 598 | 467 | 78% | 5.0 | ||

Modular Arithmetic | 764 | 413 | 54% | 0.00 | 258 | 238 | 92% | 2.7 | ||

Partial Linear Equation Solver | 608 | 115 | 19% | 0.01 | 97 | 56 | 58% | 8.7 | ||

Point in Polygon | 1510 | 437 | 29% | 0.00 | 285 | 222 | 78% | 6.0 | ||

Polygon Area | 2577 | 1014 | 39% | 0.00 | 833 | 722 | 87% | 2.8 | ||

Prime Sieve | 4890 | 1522 | 31% | 0.00 | 889 | 627 | 71% | 5.6 | ||

Rational Arithmetic | 2577 | 809 | 31% | 0.00 | 609 | 511 | 84% | 3.4 | ||

Single source shortest path, negative weights | 3285 | 661 | 20% | 0.01 | 432 | 299 | 69% | 6.4 | ||

Single source shortest path, non-negative weights | 6242 | 1901 | 30% | 0.02 | 1001 | 798 | 80% | 4.1 | ||

Single source shortest path, time table | 1637 | 514 | 31% | 0.01 | 330 | 267 | 81% | 4.1 | ||

String Matching | 3672 | 1059 | 29% | 0.01 | 659 | 495 | 75% | 4.6 | ||

String Multimatching | 1409 | 390 | 28% | 0.18 | 176 | 114 | 65% | 7.4 | ||

Suffix Sorting | 1168 | 460 | 39% | 0.03 | 192 | 150 | 78% | 6.0 |