robert-king

"""
Rusty Rob
https://x.com/robertkingNZ

For this hard problem I discovered that an innovative linear solution exists and thought it was worth sharing.

Problem statement
https://www.facebook.com/codingcompetitions/hacker-cup/2020/qualification-round/problems/D2

TLDR Problem statement:

robert-king

/*
Problem E: Wildcard Submissions
https://www.facebook.com/codingcompetitions/hacker-cup/2024/round-1/problems/E
I didn't participate but I coded up the solution to E after reading over the contest analysis
*/

use rayon::prelude::*;
use std::io::{stdin, BufRead};

const MODULO: u64 = 998_244_353;

robert-king

struct Node {
    next: Option<Box<Node>>,
    val: i32,
}

impl Node {
    fn new(val: i32) -> Self {
        Node { next: None, val }
    }

robert-king

use std::hash::Hash;
use std::{collections::HashMap, thread, time::Duration};

fn factorial(n: i32) -> i32 {
    if n <= 1 {
        return 1;
    }
    thread::sleep(Duration::from_millis(100));
    factorial(n - 1).wrapping_mul(n)
}

robert-king

#![allow(dead_code)]

/*
we use hashmaps for the linkedlist to sidestep the borrow checker.
we use proptest strategy to generate series of operations across the linkedlist and compare to a VecDeque for correctness.
We can add subtle bugs and proptest manages to catch them 
and shrink down to a minimal reproduction which we can then copy and paste to create a new test case.

PROPTEST_CASES=1000000 PROPTEST_MAX_SHRINK_ITERS=100000000 cargo test --release
cargo test copy_test_case

robert-king

/*
- Blazing fast, highly accurate cheating detection algorithm
- by Robert King, https://www.linkedin.com/in/robertkingnz/
- Youtube walkthrough: https://youtu.be/CnIQkIseLGs
- X https://x.com/robertkingNZ

- BACKGROUND
- The Google Code Jam team presented their 90% accurate algorithm after google code jam 2021.
- During the contest, Rob discovered a ~100% accurate algorithm and so thought it was worth sharing.

robert-king

// https://youtu.be/zhF-L_BgCHo

use std::sync::{mpsc::channel, Arc, Mutex};
use std::thread;
use std::time::Instant;

fn is_prime(n: i32) -> bool {
    if n < 2 {
        return false;
    }

robert-king

// youtube walkthrough: https://youtu.be/mRW8Kbb1YlA?si=lBe4mNvfBYxe9ALl

const DATA: &str = "Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green";

#[derive(Debug)]
enum Color {

robert-king

// Robert on X: https://x.com/robertkingNZ
// Video walkthrough of solution: https://youtu.be/p2L-uvMlFaE?si=9PU_dHG4uDyPFQZz
// Problem statement: https://www.facebook.com/codingcompetitions/hacker-cup/2023/practice-round/problems/D

use std::thread;
use std::collections::{HashSet, VecDeque};
use std::io::{StdinLock, StdoutLock};
use segment_tree::SegmentPoint;
use segment_tree::ops::Min;

robert-king

/**
* https://codingcompetitions.withgoogle.com/codejam/round/0000000000432dfc/0000000000433101
* @robertkingnz
**/

use std::collections::{HashMap, HashSet};

fn get_line() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();