13 files changed, 1119 insertions, 0 deletions
diff --git a/kattis-open/almostunionfind/Cargo.lock b/kattis-open/almostunionfind/Cargo.lock
new file mode 100644
index 0000000..8c10bd2
--- /dev/null
+++ b/kattis-open/almostunionfind/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "almostunionfind"
+version = "0.1.0"
diff --git a/kattis-open/almostunionfind/Cargo.toml b/kattis-open/almostunionfind/Cargo.toml
new file mode 100644
index 0000000..92e2ba8
--- /dev/null
+++ b/kattis-open/almostunionfind/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "almostunionfind"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/kattis-open/almostunionfind/bad.py b/kattis-open/almostunionfind/bad.py
new file mode 100755
index 0000000..1d4cbec
--- /dev/null
+++ b/kattis-open/almostunionfind/bad.py
@@ -0,0 +1,53 @@
+#!/usr/bin/python
+
+while True:
+    try:
+        line = input()
+    except EOFError:
+        break
+    n, m = map(int, line.split())
+
+    u = [[i + 1] for i in range(n)]
+
+    for _ in range(m):
+        line = input().split()
+        p = int(line[1])
+        if line[0] != '3':
+            q = int(line[2])
+
+        if line[0] == '1': # union
+            a, b = False, False
+            for s in u:
+                if p in s:
+                    a = s
+                if q in s:
+                    b = s
+            if a == False or b == False:
+                raise ValueError(f"could not find {p} or {q} in {u}")
+            if a != b:
+                for i in b:
+                    a.append(i)
+                b.clear()
+                u.remove(b)
+        elif line[0] == '2': # move
+            a, b = False, False
+            for s in u:
+                if p in s:
+                    a = s
+                if q in s:
+                    b = s
+            if a == False or b == False:
+                raise ValueError(f"could not find {p} or {q} in {u}")
+            if a != b:
+                a.remove(p)
+                b.append(p)
+                if not a:
+                    u.remove(a)
+        elif line[0] == '3':
+            for s in u:
+                if p in s:
+                    print(len(s), sum(s))
+                    break
+            else:
+                raise ValueError(f"could not find {p} in {u}")
+        # print(u)
diff --git a/kattis-open/almostunionfind/geninput.py b/kattis-open/almostunionfind/geninput.py
new file mode 100755
index 0000000..5eef1f3
--- /dev/null
+++ b/kattis-open/almostunionfind/geninput.py
@@ -0,0 +1,15 @@
+#!/usr/bin/python
+
+from random import randint as rand
+
+n, m = rand(10, 1000), rand(10, 1000)
+print(n, m)
+
+for _ in range(m):
+    t = rand(1, 3)
+    if t < 3:
+        p, q = rand(1, n), rand(1, n)
+        print(t, p, q)
+    else:
+        p = rand(1, n)
+        print(t, p)
diff --git a/kattis-open/almostunionfind/in2.txt b/kattis-open/almostunionfind/in2.txt
new file mode 100644
index 0000000..1bb97fe
--- /dev/null
+++ b/kattis-open/almostunionfind/in2.txt
@@ -0,0 +1,8 @@
+9 7
+1 6 1
+1 7 2
+1 5 2
+1 8 6
+1 5 8
+2 8 4
+3 5
diff --git a/kattis-open/almostunionfind/in3.txt b/kattis-open/almostunionfind/in3.txt
new file mode 100644
index 0000000..1a27497
--- /dev/null
+++ b/kattis-open/almostunionfind/in3.txt
@@ -0,0 +1,241 @@
+429 240
+3 245
+2 141 372
+1 300 23
+3 184
+1 91 179
+2 45 232
+1 203 425
+2 393 12
+1 399 339
+2 302 138
+2 204 132
+2 429 139
+3 233
+1 88 315
+1 59 318
+3 259
+2 173 166
+1 322 420
+1 72 386
+3 212
+3 417
+1 409 127
+3 118
+3 113
+2 89 208
+3 365
+2 79 406
+1 109 29
+1 385 59
+2 406 409
+1 29 297
+3 48
+1 211 297
+3 147
+2 24 161
+3 1
+3 130
+3 266
+2 338 92
+1 143 302
+2 317 367
+3 294
+2 401 220
+1 170 273
+3 25
+1 296 329
+1 255 214
+2 153 177
+2 228 55
+2 79 311
+2 374 51
+2 373 65
+2 386 35
+2 388 103
+1 429 395
+1 229 82
+1 62 416
+1 6 272
+3 81
+2 15 310
+1 414 375
+3 309
+1 122 259
+3 410
+3 6
+3 330
+2 201 390
+1 377 69
+3 310
+3 233
+2 157 246
+3 24
+2 168 108
+3 216
+2 282 5
+2 190 156
+3 427
+1 109 334
+3 37
+2 384 412
+1 324 74
+2 296 262
+3 412
+1 7 109
+2 31 317
+3 214
+1 55 164
+3 349
+3 202
+3 255
+1 27 278
+1 156 379
+2 429 328
+2 136 385
+1 199 188
+2 275 368
+3 164
+2 313 190
+2 324 182
+1 286 279
+3 311
+3 415
+2 330 146
+2 176 343
+2 281 20
+3 164
+3 134
+2 128 258
+1 258 335
+1 408 363
+1 413 110
+3 374
+1 31 28
+2 86 247
+3 416
+1 245 51
+3 27
+2 125 303
+1 111 227
+3 335
+3 305
+2 111 78
+2 411 77
+1 57 26
+3 425
+2 222 209
+3 251
+2 111 115
+3 328
+1 127 394
+1 89 387
+3 352
+3 346
+1 135 338
+3 407
+3 372
+2 51 41
+3 284
+2 153 411
+2 225 316
+1 180 257
+1 89 127
+3 150
+3 218
+2 242 249
+3 317
+1 371 83
+2 201 145
+3 336
+2 92 10
+1 199 18
+1 318 184
+2 333 306
+2 375 416
+2 198 245
+3 337
+3 331
+2 401 429
+1 239 260
+3 197
+1 89 421
+3 315
+2 219 91
+3 172
+1 56 273
+1 225 48
+1 89 238
+1 424 418
+1 162 296
+3 416
+2 376 265
+1 96 354
+2 55 326
+1 248 105
+1 425 247
+1 37 87
+2 166 254
+3 315
+3 80
+3 273
+1 191 139
+1 181 159
+2 135 158
+2 158 392
+2 179 84
+1 251 422
+1 152 218
+1 12 287
+2 47 330
+1 245 386
+2 199 423
+1 204 35
+2 6 227
+3 209
+3 98
+3 60
+3 79
+3 38
+3 417
+1 11 409
+1 23 151
+2 226 39
+3 173
+3 225
+2 92 376
+2 123 107
+1 331 60
+3 399
+2 96 249
+2 365 177
+1 410 325
+2 8 61
+2 5 199
+2 279 107
+2 303 329
+2 237 366
+2 91 335
+3 145
+3 52
+1 301 254
+3 395
+1 278 70
+1 233 341
+1 164 193
+3 365
+3 34
+3 50
+2 147 121
+3 278
+2 63 131
+2 328 87
+2 29 206
+1 320 238
+3 304
+2 183 414
+3 10
+2 178 8
+1 10 243
+3 20
+2 142 417
diff --git a/kattis-open/almostunionfind/input.txt b/kattis-open/almostunionfind/input.txt
new file mode 100644
index 0000000..315b418
--- /dev/null
+++ b/kattis-open/almostunionfind/input.txt
@@ -0,0 +1,41 @@
+17 40
+2 14 11
+2 3 13
+2 5 8
+2 13 15
+2 13 1
+2 4 6
+3 9
+2 2 7
+2 5 12
+2 14 1
+2 4 13
+3 6
+1 16 5
+3 12
+1 4 16
+1 15 3
+3 6
+3 3
+2 13 4
+3 16
+1 10 11
+3 6
+2 2 2
+3 4
+3 7
+3 3
+2 16 8
+2 7 2
+1 9 15
+3 14
+1 6 5
+2 17 3
+2 12 5
+3 17
+2 11 10
+3 2
+2 12 9
+1 17 2
+2 15 16
+1 3 15
diff --git a/kattis-open/almostunionfind/pyout.txt b/kattis-open/almostunionfind/pyout.txt
new file mode 100644
index 0000000..63fdad2
--- /dev/null
+++ b/kattis-open/almostunionfind/pyout.txt
@@ -0,0 +1,281 @@
+1 309
+1 500
+1 112
+1 142
+1 366
+1 575
+1 113
+1 126
+1 496
+1 349
+1 23
+1 103
+1 339
+1 30
+1 436
+1 311
+3 416
+1 184
+1 548
+1 561
+1 568
+1 45
+1 206
+1 329
+1 544
+1 478
+1 352
+1 555
+1 103
+2 1036
+1 541
+3 530
+4 1205
+2 723
+1 459
+1 453
+1 52
+1 74
+1 258
+1 11
+3 1435
+2 345
+1 411
+3 708
+1 100
+1 576
+1 277
+1 574
+2 650
+1 460
+1 316
+1 48
+1 164
+1 75
+2 638
+4 1205
+1 190
+1 496
+3 747
+1 466
+1 371
+1 558
+1 573
+2 927
+1 104
+2 563
+1 127
+1 311
+1 151
+2 932
+1 596
+1 187
+1 543
+2 93
+2 811
+1 154
+1 498
+6 2215
+1 248
+1 250
+1 548
+3 747
+1 47
+1 370
+2 992
+5 945
+1 292
+1 108
+1 327
+3 693
+2 992
+2 334
+2 334
+3 799
+2 784
+2 439
+5 1721
+1 231
+1 442
+1 377
+1 53
+2 658
+1 552
+4 1674
+3 958
+4 1674
+3 797
+4 1007
+1 22
+3 1231
+2 432
+3 1383
+1 475
+1 111
+2 1138
+2 686
+1 211
+3 918
+1 504
+2 177
+5 1941
+2 586
+1 507
+1 48
+1 332
+1 77
+17 5984
+1 364
+2 811
+2 500
+26 9440
+1 146
+2 500
+1 66
+1 537
+1 532
+1 74
+4 1540
+1 132
+1 405
+1 469
+3 385
+1 443
+4 1422
+3 1393
+1 11
+4 1422
+3 653
+4 892
+3 922
+2 737
+1 377
+1 232
+3 592
+1 128
+1 289
+1 452
+2 638
+2 986
+1 299
+2 439
+4 767
+1 120
+1 48
+2 214
+3 1393
+4 794
+2 500
+1 286
+2 932
+3 1311
+43 14918
+1 61
+2 584
+2 555
+1 63
+1 232
+2 742
+6 2007
+1 275
+1 75
+1 3
+4 1104
+2 1138
+1 73
+2 533
+4 1110
+1 299
+1 330
+17 4452
+6 1568
+4 1651
+5 802
+6 2007
+2 555
+1 354
+46 15564
+1 203
+11 3264
+1 249
+2 605
+1 338
+1 324
+7 2383
+3 1187
+1 510
+3 1018
+3 1176
+10 2671
+3 954
+2 439
+3 1187
+1 443
+57 18251
+59 18690
+1 578
+1 63
+2 492
+8 2710
+8 2710
+2 326
+2 326
+51 14428
+4 1479
+1 50
+65 21427
+1 228
+2 675
+1 362
+65 21556
+5 1683
+3 753
+2 477
+65 21556
+2 732
+5 1377
+51 14428
+51 14428
+1 528
+51 14225
+1 237
+2 932
+1 132
+7 1842
+5 1552
+64 21578
+1 458
+2 360
+3 555
+2 410
+51 14024
+1 407
+8 1910
+8 1910
+72 23820
+11 3914
+73 24655
+9 2532
+77 25911
+75 22332
+75 22332
+5 1377
+1 287
+1 200
+76 22868
+3 1031
+3 1041
+4 1244
+7 1468
+5 1525
+15 5005
+77 22896
+5 1466
+1 43
+3 781
+1 514
+7 1358
+2 1011
+1 374
+1 225
+7 1468
diff --git a/kattis-open/almostunionfind/rustout.txt b/kattis-open/almostunionfind/rustout.txt
new file mode 100644
index 0000000..63fdad2
--- /dev/null
+++ b/kattis-open/almostunionfind/rustout.txt
@@ -0,0 +1,281 @@
+1 309
+1 500
+1 112
+1 142
+1 366
+1 575
+1 113
+1 126
+1 496
+1 349
+1 23
+1 103
+1 339
+1 30
+1 436
+1 311
+3 416
+1 184
+1 548
+1 561
+1 568
+1 45
+1 206
+1 329
+1 544
+1 478
+1 352
+1 555
+1 103
+2 1036
+1 541
+3 530
+4 1205
+2 723
+1 459
+1 453
+1 52
+1 74
+1 258
+1 11
+3 1435
+2 345
+1 411
+3 708
+1 100
+1 576
+1 277
+1 574
+2 650
+1 460
+1 316
+1 48
+1 164
+1 75
+2 638
+4 1205
+1 190
+1 496
+3 747
+1 466
+1 371
+1 558
+1 573
+2 927
+1 104
+2 563
+1 127
+1 311
+1 151
+2 932
+1 596
+1 187
+1 543
+2 93
+2 811
+1 154
+1 498
+6 2215
+1 248
+1 250
+1 548
+3 747
+1 47
+1 370
+2 992
+5 945
+1 292
+1 108
+1 327
+3 693
+2 992
+2 334
+2 334
+3 799
+2 784
+2 439
+5 1721
+1 231
+1 442
+1 377
+1 53
+2 658
+1 552
+4 1674
+3 958
+4 1674
+3 797
+4 1007
+1 22
+3 1231
+2 432
+3 1383
+1 475
+1 111
+2 1138
+2 686
+1 211
+3 918
+1 504
+2 177
+5 1941
+2 586
+1 507
+1 48
+1 332
+1 77
+17 5984
+1 364
+2 811
+2 500
+26 9440
+1 146
+2 500
+1 66
+1 537
+1 532
+1 74
+4 1540
+1 132
+1 405
+1 469
+3 385
+1 443
+4 1422
+3 1393
+1 11
+4 1422
+3 653
+4 892
+3 922
+2 737
+1 377
+1 232
+3 592
+1 128
+1 289
+1 452
+2 638
+2 986
+1 299
+2 439
+4 767
+1 120
+1 48
+2 214
+3 1393
+4 794
+2 500
+1 286
+2 932
+3 1311
+43 14918
+1 61
+2 584
+2 555
+1 63
+1 232
+2 742
+6 2007
+1 275
+1 75
+1 3
+4 1104
+2 1138
+1 73
+2 533
+4 1110
+1 299
+1 330
+17 4452
+6 1568
+4 1651
+5 802
+6 2007
+2 555
+1 354
+46 15564
+1 203
+11 3264
+1 249
+2 605
+1 338
+1 324
+7 2383
+3 1187
+1 510
+3 1018
+3 1176
+10 2671
+3 954
+2 439
+3 1187
+1 443
+57 18251
+59 18690
+1 578
+1 63
+2 492
+8 2710
+8 2710
+2 326
+2 326
+51 14428
+4 1479
+1 50
+65 21427
+1 228
+2 675
+1 362
+65 21556
+5 1683
+3 753
+2 477
+65 21556
+2 732
+5 1377
+51 14428
+51 14428
+1 528
+51 14225
+1 237
+2 932
+1 132
+7 1842
+5 1552
+64 21578
+1 458
+2 360
+3 555
+2 410
+51 14024
+1 407
+8 1910
+8 1910
+72 23820
+11 3914
+73 24655
+9 2532
+77 25911
+75 22332
+75 22332
+5 1377
+1 287
+1 200
+76 22868
+3 1031
+3 1041
+4 1244
+7 1468
+5 1525
+15 5005
+77 22896
+5 1466
+1 43
+3 781
+1 514
+7 1358
+2 1011
+1 374
+1 225
+7 1468
diff --git a/kattis-open/almostunionfind/src/main.rs b/kattis-open/almostunionfind/src/main.rs
new file mode 100644
index 0000000..6563043
--- /dev/null
+++ b/kattis-open/almostunionfind/src/main.rs
@@ -0,0 +1,153 @@
+// https://open.kattis.com/problems/almostunionfind
+
+use std::{
+    io::{stdin, Read},
+    iter::once,
+};
+
+enum Node {
+    Root { count: u32, sum: u64 },
+    Child(usize),
+    Invalid,
+}
+
+impl Node {
+    fn count(&self) -> u32 {
+        match self {
+            &Root { count, .. } => count,
+            _ => unreachable!(),
+        }
+    }
+}
+
+use Node::*;
+
+fn root(uf: &mut [Node], mut node: usize) -> usize {
+    let mut root = node;
+    while let Child(parent) = uf[root] {
+        root = parent
+    }
+    while let Child(parent) = uf[node] {
+        uf[node] = Child(root);
+        node = parent;
+    }
+    root
+}
+
+fn join(uf: &mut [Node], a: usize, b: usize) {
+    let mut a = root(uf, a);
+    let mut b = root(uf, b);
+
+    if a == b {
+        return;
+    }
+
+    if uf[a].count() < uf[b].count() {
+        let tmp = a;
+        a = b;
+        b = tmp;
+    }
+
+    let (b_count, b_sum) = match uf[b] {
+        Root { count, sum } => (count, sum),
+        _ => unreachable!(),
+    };
+    match &mut uf[a] {
+        Root { count, sum } => {
+            *count += b_count;
+            *sum += b_sum;
+        }
+        _ => unreachable!(),
+    }
+    uf[b] = Child(a);
+}
+
+fn mov(
+    uf: &mut [Node],
+    free_index: &mut usize,
+    current_index_of: &mut [usize],
+    a: usize,
+    a_val: u64,
+    b: usize,
+) {
+    let a_root = root(uf, a);
+    let b_root = root(uf, b);
+    if a_root == b_root {
+        return;
+    }
+    match &mut uf[a_root] {
+        Root { count, sum } => {
+            *count -= 1;
+            *sum -= a_val;
+        }
+        _ => unreachable!(),
+    }
+    match &mut uf[b_root] {
+        Root { count, sum } => {
+            *count += 1;
+            *sum += a_val;
+        }
+        _ => unreachable!(),
+    }
+    uf[*free_index] = Child(b_root);
+    current_index_of[a_val as usize] = *free_index;
+    *free_index += 1;
+}
+
+fn main() {
+    let mut input = String::new();
+    stdin().lock().read_to_string(&mut input).unwrap();
+    let mut ints = input
+        .trim()
+        .split(|c| c == ' ' || c == '\n')
+        .map(|i| i.parse::<usize>().unwrap());
+    let mut get = || ints.next();
+
+    while let Some(n) = get() {
+        let m = get().unwrap();
+
+        let mut uf: Vec<Node> = (0..n + m)
+            .map(|i| {
+                if i < n {
+                    Root {
+                        count: 1,
+                        sum: i as u64 + 1,
+                    }
+                } else {
+                    Invalid
+                }
+            })
+            .collect();
+        let mut free_index = n;
+        let mut current_index_of: Vec<usize> = (once(0).chain(0..n)).collect();
+
+        for _ in 0..m {
+            match get().unwrap() {
+                1 => {
+                    let (p, q) = (get().unwrap(), get().unwrap());
+                    join(&mut uf, current_index_of[p], current_index_of[q]);
+                }
+                2 => {
+                    let (p, q) = (get().unwrap(), get().unwrap());
+                    let (pi, qi) = (current_index_of[p], current_index_of[q]);
+                    mov(
+                        &mut uf,
+                        &mut free_index,
+                        &mut current_index_of,
+                        pi,
+                        p as u64,
+                        qi,
+                    );
+                }
+                _ => {
+                    let p = get().unwrap();
+                    let r = root(&mut uf, current_index_of[p]);
+                    match uf[r] {
+                        Root { count, sum } => println!("{} {}", count, sum),
+                        _ => unreachable!(),
+                    }
+                }
+            }
+        }
+    }
+}
diff --git a/kattis-open/sperhling/Cargo.lock b/kattis-open/sperhling/Cargo.lock
new file mode 100644
index 0000000..5a98a2d
--- /dev/null
+++ b/kattis-open/sperhling/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "sperhling"
+version = "0.1.0"
diff --git a/kattis-open/sperhling/Cargo.toml b/kattis-open/sperhling/Cargo.toml
new file mode 100644
index 0000000..394fda5
--- /dev/null
+++ b/kattis-open/sperhling/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "sperhling"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/kattis-open/sperhling/src/main.rs b/kattis-open/sperhling/src/main.rs
new file mode 100644
index 0000000..93b1ed1
--- /dev/null
+++ b/kattis-open/sperhling/src/main.rs
@@ -0,0 +1,16 @@
+use std::io::{stdin, BufRead};
+
+fn main() {
+    let stdin = stdin();
+    let mut lines = stdin.lock().lines();
+    let s1 = lines.next().unwrap().unwrap();
+    let s2 = lines.next().unwrap().unwrap();
+
+    let lcp = s1
+        .bytes()
+        .zip(s2.bytes())
+        .take_while(|&(a, b)| a == b)
+        .count();
+
+    println!("{}", s1.len() + s2.len() - 2 * lcp);
+}