class SkiRentalOnline:
    def __init__(self, buy_cost=300, rent_cost=30):
        self.buy_cost = buy_cost
        self.rent_cost = rent_cost
        self.has_bought = False
        self.total_cost = 0
        self.days_skied = 0
    
    def decide_daily(self):
        """Make decision for current day without knowing future"""
        self.days_skied += 1
        
        if self.has_bought:
            # Already bought, no additional cost
            return "use_owned_skis", 0
        
        # Decision: rent today or buy today?
        if self.should_buy():
            self.has_bought = True
            cost = self.buy_cost
            decision = "buy"
        else:
            cost = self.rent_cost
            decision = "rent"
        
        self.total_cost += cost
        return decision, cost
    
    def should_buy(self):
        # Simple strategy: buy after renting for 10 days
        return self.days_skied > 10

# Offline optimal solution for comparison
def ski_rental_offline(total_days, buy_cost=300, rent_cost=30):
    """Optimal solution knowing total days in advance"""
    rent_total = total_days * rent_cost
    if buy_cost < rent_total:
        return buy_cost, "buy_immediately"
    else:
        return rent_total, "rent_always"

from collections import OrderedDict
from typing import List, Tuple

class OnlinePaging:
    def __init__(self, cache_size: int):
        self.cache_size = cache_size
        self.cache = OrderedDict()  # Maintains insertion order
        self.total_cost = 0
        self.requests_served = 0
    
    def lru_strategy(self, page: int) -> Tuple[bool, int]:
        """Least Recently Used eviction strategy"""
        self.requests_served += 1
        
        if page in self.cache:
            # Cache hit - move to end (most recent)
            self.cache.move_to_end(page)
            return True, 0  # hit, no cost
        
        # Cache miss - need to fetch page
        cost = 1
        self.total_cost += cost
        
        if len(self.cache) >= self.cache_size:
            # Evict least recently used (first item)
            self.cache.popitem(last=False)
        
        self.cache[page] = True
        return False, cost  # miss, cost = 1
    
    def fifo_strategy(self, page: int) -> Tuple[bool, int]:
        """First In First Out eviction strategy"""
        self.requests_served += 1
        
        if page in self.cache:
            return True, 0  # hit, no cost
        
        # Cache miss
        cost = 1
        self.total_cost += cost
        
        if len(self.cache) >= self.cache_size:
            # Evict oldest (first inserted)
            self.cache.popitem(last=False)
        
        self.cache[page] = True
        return False, cost

# Simulate cache performance
def simulate_caching(pages: List[int], cache_size: int, strategy: str):
    cache = OnlinePaging(cache_size)
    
    hits, misses = 0, 0
    for page in pages:
        if strategy == "LRU":
            is_hit, cost = cache.lru_strategy(page)
        elif strategy == "FIFO":
            is_hit, cost = cache.fifo_strategy(page)
        
        if is_hit:
            hits += 1
        else:
            misses += 1
    
    return hits, misses, cache.total_cost

# Example usage
pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
hits, misses, cost = simulate_caching(pages, cache_size=3, strategy="LRU")
print(f"LRU: {hits} hits, {misses} misses, total cost: {cost}")

import heapq
from typing import List

class OnlineLoadBalancing:
    def __init__(self, num_machines: int):
        self.num_machines = num_machines
        # Use min-heap to track machine loads
        self.machine_loads = [0.0] * num_machines
        self.assignments = []
    
    def greedy_assignment(self, job_size: float) -> int:
        """Assign job to least loaded machine"""
        # Find machine with minimum load
        min_machine = min(range(self.num_machines), 
                         key=lambda i: self.machine_loads[i])
        
        # Assign job to this machine
        self.machine_loads[min_machine] += job_size
        self.assignments.append((len(self.assignments), min_machine, job_size))
        
        return min_machine
    
    def get_makespan(self) -> float:
        """Return maximum load across all machines"""
        return max(self.machine_loads)
    
    def get_total_load(self) -> float:
        """Return sum of all loads"""
        return sum(self.machine_loads)

def compare_online_offline_scheduling(jobs: List[float], num_machines: int):
    # Online greedy algorithm
    online_scheduler = OnlineLoadBalancing(num_machines)
    for job in jobs:
        online_scheduler.greedy_assignment(job)
    
    online_makespan = online_scheduler.get_makespan()
    
    # Lower bound for optimal offline (total_load / num_machines)
    total_load = sum(jobs)
    optimal_lower_bound = total_load / num_machines
    
    # Another lower bound (largest job size)
    max_job = max(jobs) if jobs else 0
    
    offline_lower_bound = max(optimal_lower_bound, max_job)
    
    competitive_ratio = online_makespan / offline_lower_bound if offline_lower_bound > 0 else float('inf')
    
    return {
        'online_makespan': online_makespan,
        'offline_lower_bound': offline_lower_bound,
        'competitive_ratio': competitive_ratio,
        'assignments': online_scheduler.assignments
    }

# Example
jobs = [4, 3, 2, 8, 1, 5, 2, 6]
result = compare_online_offline_scheduling(jobs, num_machines=3)
print(f"Online makespan: {result['online_makespan']:.2f}")
print(f"Offline lower bound: {result['offline_lower_bound']:.2f}")
print(f"Competitive ratio: {result['competitive_ratio']:.2f}")

import math
from typing import List, Tuple

class KServerOnline:
    def __init__(self, k: int, positions: List[Tuple[float, float]]):
        self.k = k
        self.server_positions = positions[:k]  # Initial server positions
        self.total_cost = 0
        self.requests_served = 0
    
    def distance(self, pos1: Tuple[float, float], pos2: Tuple[float, float]) -> float:
        """Euclidean distance between two positions"""
        return math.sqrt((pos1[0] - pos2[0])**2 + (pos1[1] - pos2[1])**2)
    
    def nearest_server_strategy(self, request_pos: Tuple[float, float]) -> float:
        """Move nearest server to request position"""
        self.requests_served += 1
        
        # Check if any server is already at request position
        for i, server_pos in enumerate(self.server_positions):
            if self.distance(server_pos, request_pos) < 1e-9:  # Essentially at same position
                return 0  # No cost
        
        # Find nearest server
        distances = [self.distance(pos, request_pos) for pos in self.server_positions]
        nearest_idx = min(range(len(distances)), key=lambda i: distances[i])
        
        # Move nearest server and calculate cost
        cost = distances[nearest_idx]
        self.server_positions[nearest_idx] = request_pos
        self.total_cost += cost
        
        return cost

# Example usage
servers = [(0, 0), (10, 0), (0, 10)]  # 3 servers
k_server = KServerOnline(k=3, positions=servers)

requests = [(1, 1), (2, 2), (8, 1), (9, 9), (1, 8)]
for req in requests:
    cost = k_server.nearest_server_strategy(req)
    print(f"Request at {req}: moved server, cost = {cost:.2f}")

print(f"Total cost: {k_server.total_cost:.2f}")

def compare_paging_algorithms():
    # Both LRU and FIFO have competitive ratio k for cache size k
    # But they behave very differently on real workloads
    
    # Example: sequential access pattern
    sequential_pages = list(range(1, 21)) * 2  # [1,2,...,20,1,2,...,20]
    
    lru_hits, lru_misses, lru_cost = simulate_caching(sequential_pages, 3, "LRU")
    fifo_hits, fifo_misses, fifo_cost = simulate_caching(sequential_pages, 3, "FIFO")
    
    print("Sequential access pattern:")
    print(f"LRU:  {lru_hits} hits, {lru_misses} misses")
    print(f"FIFO: {fifo_hits} hits, {fifo_misses} misses")
    
    # Example: cyclic access pattern  
    cyclic_pages = [1, 2, 3, 1, 2, 3, 1, 2, 3] * 5
    
    lru_hits, lru_misses, lru_cost = simulate_caching(cyclic_pages, 2, "LRU")
    fifo_hits, fifo_misses, fifo_cost = simulate_caching(cyclic_pages, 2, "FIFO")
    
    print("\nCyclic access pattern:")
    print(f"LRU:  {lru_hits} hits, {lru_misses} misses")
    print(f"FIFO: {fifo_hits} hits, {fifo_misses} misses")

compare_paging_algorithms()

class BinarySearchWithAdvice:
    def __init__(self, sorted_array, target):
        self.array = sorted_array
        self.target = target
        self.advice_bits_used = 0
        self.comparisons = 0
    
    def search_with_advice(self, advice_string):
        """Binary search using advice bits"""
        left, right = 0, len(self.array) - 1
        advice_index = 0
        
        while left <= right:
            mid = (left + right) // 2
            self.comparisons += 1
            
            if self.array[mid] == self.target:
                return mid
            
            # Use advice bit to decide direction
            if advice_index < len(advice_string):
                advice_bit = int(advice_string[advice_index])
                self.advice_bits_used += 1
                advice_index += 1
                
                if advice_bit == 0:  # Go left
                    right = mid - 1
                else:  # Go right
                    left = mid + 1
            else:
                # No more advice, use standard comparison
                if self.array[mid] < self.target:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1  # Not found
    
    def generate_optimal_advice(self):
        """Generate advice string for optimal path"""
        advice = []
        left, right = 0, len(self.array) - 1
        
        while left <= right:
            mid = (left + right) // 2
            
            if self.array[mid] == self.target:
                break
            elif self.array[mid] < self.target:
                advice.append('1')  # Go right
                left = mid + 1
            else:
                advice.append('0')  # Go left
                right = mid - 1
        
        return ''.join(advice)

# Example usage
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7

searcher = BinarySearchWithAdvice(array, target)
optimal_advice = searcher.generate_optimal_advice()

print(f"Optimal advice string: {optimal_advice}")
print(f"Advice bits needed: {len(optimal_advice)}")

result = searcher.search_with_advice(optimal_advice)
print(f"Target found at index: {result}")
print(f"Advice bits used: {searcher.advice_bits_used}")
print(f"Comparisons made: {searcher.comparisons}")

import math
from typing import Dict, List

class AdviceComplexityAnalyzer:
    def __init__(self, problem_name: str):
        self.problem_name = problem_name
        self.results = {}
    
    def compute_advice_vs_ratio(self, max_advice_bits: int, input_size: int):
        """Compute advice-competitive ratio trade-off"""
        trade_off = {}
        
        if self.problem_name == "paging":
            k = input_size  # cache size
            for b in range(max_advice_bits + 1):
                if b == 0:
                    # No advice: competitive ratio is k
                    ratio = k
                elif b >= input_size * math.log2(k):
                    # Enough advice for optimal: ratio = 1
                    ratio = 1.0
                else:
                    # Approximate intermediate values
                    ratio = max(1.0, k * (1 - b / (input_size * math.log2(k))))
                
                trade_off[b] = ratio
        
        elif self.problem_name == "ski_rental":
            for b in range(max_advice_bits + 1):
                if b == 0:
                    ratio = 2.0  # Classical result
                elif b >= math.log2(input_size):
                    ratio = 1.0  # Optimal with enough advice
                else:
                    # Linear interpolation (simplified)
                    ratio = 2.0 - b / math.log2(input_size)
                
                trade_off[b] = ratio
        
        return trade_off
    
    def plot_trade_off(self, trade_off: Dict[int, float]):
        """Print trade-off table"""
        print(f"\nAdvice-Performance Trade-off for {self.problem_name}:")
        print("Advice Bits | Competitive Ratio")
        print("------------|------------------")
        for bits, ratio in sorted(trade_off.items()):
            print(f"{bits:11d} | {ratio:16.2f}")

# Example analysis
analyzer = AdviceComplexityAnalyzer("paging")
trade_off = analyzer.compute_advice_vs_ratio(max_advice_bits=10, input_size=4)
analyzer.plot_trade_off(trade_off)

analyzer = AdviceComplexityAnalyzer("ski_rental")
trade_off = analyzer.compute_advice_vs_ratio(max_advice_bits=8, input_size=100)
analyzer.plot_trade_off(trade_off)

import math

class SkiRentalWithAdvice:
    def __init__(self, buy_cost=300, rent_cost=30):
        self.buy_cost = buy_cost
        self.rent_cost = rent_cost
        self.breakeven = buy_cost // rent_cost  # 10 days
        
    def generate_advice(self, total_days):
        """Generate advice string encoding total days"""
        if total_days <= 0:
            return ""
        
        # Encode total_days in binary
        advice_bits = math.ceil(math.log2(total_days + 1))
        advice_string = format(total_days, f'0{advice_bits}b')
        return advice_string
    
    def decode_advice(self, advice_string):
        """Decode advice to get total days"""
        if not advice_string:
            return None
        return int(advice_string, 2)
    
    def strategy_with_advice(self, advice_string):
        """Optimal strategy given advice about total days"""
        total_days = self.decode_advice(advice_string)
        
        if total_days is None:
            # No advice - use 2-competitive strategy
            return self.strategy_no_advice()
        
        if total_days * self.rent_cost <= self.buy_cost:
            # Rent for all days
            return "rent_always", total_days * self.rent_cost
        else:
            # Buy immediately
            return "buy_immediately", self.buy_cost
    
    def strategy_no_advice(self):
        """2-competitive strategy without advice"""
        # Buy after renting for breakeven days
        return "buy_after_breakeven", None
    
    def simulate_with_advice(self, total_days):
        """Simulate ski rental with optimal advice"""
        advice = self.generate_advice(total_days)
        strategy, cost = self.strategy_with_advice(advice)
        
        # Optimal offline cost
        optimal_cost = min(total_days * self.rent_cost, self.buy_cost)
        
        return {
            'total_days': total_days,
            'advice_bits': len(advice),
            'advice_string': advice,
            'strategy': strategy,
            'online_cost': cost,
            'optimal_cost': optimal_cost,
            'competitive_ratio': cost / optimal_cost if optimal_cost > 0 else 1
        }

# Analysis
ski_rental = SkiRentalWithAdvice()

print("Ski Rental with Advice Analysis:")
print("=" * 50)

test_cases = [1, 5, 10, 15, 20, 50, 100]
for days in test_cases:
    result = ski_rental.simulate_with_advice(days)
    print(f"Days: {days:3d} | Advice: {result['advice_bits']:2d} bits | "
          f"Ratio: {result['competitive_ratio']:.2f} | Strategy: {result['strategy']}")

class PagingWithAdvice:
    def __init__(self, cache_size, page_universe_size):
        self.k = cache_size
        self.page_universe = page_universe_size
        self.cache = set()
        self.total_cost = 0
        
    def generate_optimal_advice(self, request_sequence):
        """Generate advice for optimal paging strategy"""
        advice_bits = []
        cache_state = set()
        
        for i, page in enumerate(request_sequence):
            if page in cache_state:
                # Cache hit - no advice needed
                continue
            
            # Cache miss - need to decide which page to evict
            if len(cache_state) < self.k:
                # Cache not full - just add page
                cache_state.add(page)
                continue
            
            # Cache full - need to evict one page
            # Find which current page is requested furthest in future
            future_requests = request_sequence[i+1:]
            evict_candidates = list(cache_state)
            
            # Find page with furthest next request (or never requested again)
            furthest_page = None
            furthest_distance = -1
            
            for candidate in evict_candidates:
                try:
                    next_request = future_requests.index(candidate)
                except ValueError:
                    # Page never requested again - evict this one
                    furthest_page = candidate
                    break
                
                if next_request > furthest_distance:
                    furthest_distance = next_request
                    furthest_page = candidate
            
            # Encode which page to evict (log k bits)
            evict_index = evict_candidates.index(furthest_page)
            bits_needed = math.ceil(math.log2(self.k)) if self.k > 1 else 1
            advice_bits.extend([int(b) for b in format(evict_index, f'0{bits_needed}b')])
            
            # Update cache state
            cache_state.remove(furthest_page)
            cache_state.add(page)
        
        return advice_bits
    
    def simulate_with_advice(self, request_sequence, advice_bits):
        """Simulate paging algorithm with advice"""
        cache = set()
        cost = 0
        advice_index = 0
        
        for page in request_sequence:
            if page in cache:
                continue  # Cache hit
            
            # Cache miss
            cost += 1
            
            if len(cache) < self.k:
                cache.add(page)
                continue
            
            # Need to evict - use advice
            bits_per_eviction = math.ceil(math.log2(self.k)) if self.k > 1 else 1
            
            if advice_index + bits_per_eviction <= len(advice_bits):
                # Decode which page to evict
                evict_bits = advice_bits[advice_index:advice_index + bits_per_eviction]
                evict_index = sum(bit * (2 ** (bits_per_eviction - 1 - i)) 
                                for i, bit in enumerate(evict_bits))
                advice_index += bits_per_eviction
                
                cache_list = list(cache)
                if evict_index < len(cache_list):
                    evict_page = cache_list[evict_index]
                    cache.remove(evict_page)
            else:
                # No more advice - use LRU or arbitrary eviction
                cache.pop()
            
            cache.add(page)
        
        return cost, advice_index

# Example analysis
paging = PagingWithAdvice(cache_size=3, page_universe_size=10)
requests = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]

print("\nPaging with Advice Analysis:")
print("Request sequence:", requests)

advice_bits = paging.generate_optimal_advice(requests)
online_cost, bits_used = paging.simulate_with_advice(requests, advice_bits)

print(f"Advice bits generated: {len(advice_bits)}")
print(f"Advice bits used: {bits_used}")
print(f"Online cost with advice: {online_cost}")

# Compare with LRU (no advice)
lru_hits, lru_misses, lru_cost = simulate_caching(requests, 3, "LRU")
print(f"LRU cost (no advice): {lru_cost}")
print(f"Improvement ratio: {lru_cost / online_cost:.2f}")

def advice_complexity_bounds():
    """Summary of known advice complexity results"""
    
    results = {
        "Paging (cache size k)": {
            "no_advice": f"Competitive ratio: k",
            "optimal_advice": f"log k bits per miss for ratio 1",
            "total_bits": f"O(m log k) for m misses",
            "lower_bound": f"Ω(m log k) bits needed for ratio 1"
        },
        
        "Ski Rental": {
            "no_advice": f"Competitive ratio: 2",
            "optimal_advice": f"log n bits for ratio 1",
            "interpolation": f"b bits → ratio 2 - b/log n",
            "lower_bound": f"Ω(log n) bits needed for ratio < 2"
        },
        
        "k-Server (metric spaces)": {
            "no_advice": f"Competitive ratio: k",
            "optimal_advice": f"O(n log k) bits for ratio 1",
            "lower_bound": f"Ω(n log k) bits needed in worst case"
        },
        
        "Load Balancing (m machines)": {
            "no_advice": f"Competitive ratio: 2 - 1/m",
            "optimal_advice": f"O(n log m) bits for ratio 1",
            "partial_advice": f"O(log m) bits per job → ratio 1 + ε"
        }
    }
    
    return results

# Print summary
bounds = advice_complexity_bounds()
for problem, result in bounds.items():
    print(f"\n{problem}:")
    for metric, bound in result.items():
        print(f"  {metric}: {bound}")

import random

class RandomizedSkiRentalWithAdvice:
    def __init__(self, buy_cost=300, rent_cost=30):
        self.buy_cost = buy_cost
        self.rent_cost = rent_cost
        self.breakeven = buy_cost // rent_cost
    
    def randomized_strategy_no_advice(self, total_days):
        """Classical randomized strategy: buy at random time"""
        # Buy at day chosen uniformly from [1, breakeven]
        buy_day = random.randint(1, self.breakeven)
        
        if total_days <= buy_day:
            # Rent for all days
            return total_days * self.rent_cost
        else:
            # Rent for buy_day days, then own
            return buy_day * self.rent_cost + self.buy_cost
    
    def advice_enhanced_randomized(self, total_days, advice_bits):
        """Use advice to improve randomized strategy"""
        if len(advice_bits) == 0:
            return self.randomized_strategy_no_advice(total_days)
        
        # Use advice bits to determine buy day more intelligently
        # This is a simplified example
        advice_value = sum(bit * (2**i) for i, bit in enumerate(advice_bits))
        
        # Adjust randomization based on advice
        if advice_value % 2 == 0:  # Even advice suggests skiing longer
            buy_day = random.randint(self.breakeven // 2, self.breakeven)
        else:  # Odd advice suggests shorter trip
            buy_day = random.randint(1, self.breakeven // 2)
        
        if total_days <= buy_day:
            return total_days * self.rent_cost
        else:
            return buy_day * self.rent_cost + self.buy_cost

# Randomized algorithms can achieve better competitive ratios
# For ski rental: randomized ratio is e/(e-1) ≈ 1.58 vs deterministic 2

import math
import random
from abc import ABC, abstractmethod
from typing import List, Dict, Tuple, Any

class OnlineProblem(ABC):
    """Abstract base class for online problems"""
    
    @abstractmethod
    def generate_advice(self, input_sequence: List[Any]) -> List[int]:
        """Generate optimal advice for given input"""
        pass
    
    @abstractmethod
    def solve_with_advice(self, input_sequence: List[Any], advice: List[int]) -> float:
        """Solve problem using advice, return cost"""
        pass
    
    @abstractmethod
    def solve_without_advice(self, input_sequence: List[Any]) -> float:
        """Solve problem without advice, return cost"""
        pass
    
    @abstractmethod
    def optimal_offline_cost(self, input_sequence: List[Any]) -> float:
        """Return optimal offline cost"""
        pass

class AdviceComplexityTester:
    def __init__(self, problem: OnlineProblem):
        self.problem = problem
    
    def analyze_trade_off(self, input_sequence: List[Any], max_advice_bits: int = None):
        """Analyze advice-performance trade-off"""
        optimal_advice = self.problem.generate_advice(input_sequence)
        optimal_cost = self.problem.optimal_offline_cost(input_sequence)
        no_advice_cost = self.problem.solve_without_advice(input_sequence)
        
        if max_advice_bits is None:
            max_advice_bits = len(optimal_advice)
        
        results = []
        
        for b in range(0, min(max_advice_bits + 1, len(optimal_advice) + 1)):
            if b == 0:
                cost = no_advice_cost
            else:
                # Use first b bits of advice
                partial_advice = optimal_advice[:b]
                cost = self.problem.solve_with_advice(input_sequence, partial_advice)
            
            competitive_ratio = cost / optimal_cost if optimal_cost > 0 else 1
            
            results.append({
                'advice_bits': b,
                'cost': cost,
                'optimal_cost': optimal_cost,
                'competitive_ratio': competitive_ratio
            })
        
        return results
    
    def print_analysis(self, results: List[Dict]):
        """Print formatted analysis results"""
        print("\nAdvice Complexity Analysis:")
        print("=" * 60)
        print(f"{'Advice Bits':<12} {'Cost':<10} {'Optimal':<10} {'Ratio':<10}")
        print("-" * 60)
        
        for result in results:
            print(f"{result['advice_bits']:<12} "
                  f"{result['cost']:<10.2f} "
                  f"{result['optimal_cost']:<10.2f} "
                  f"{result['competitive_ratio']:<10.2f}")

# Example implementation for List Update Problem
class ListUpdateProblem(OnlineProblem):
    """List Update: maintain list, move-to-front when accessed"""
    
    def __init__(self, list_size: int):
        self.list_size = list_size
    
    def generate_advice(self, access_sequence: List[int]) -> List[int]:
        """Generate advice for optimal list management"""
        advice = []
        current_list = list(range(1, self.list_size + 1))
        
        for item in access_sequence:
            if item in current_list:
                position = current_list.index(item)
                # Encode position in binary
                bits_needed = math.ceil(math.log2(self.list_size))
                advice.extend([int(b) for b in format(position, f'0{bits_needed}b')])
                
                # Move to front for next iteration
                current_list.remove(item)
                current_list.insert(0, item)
        
        return advice
    
    def solve_with_advice(self, access_sequence: List[int], advice: List[int]) -> float:
        """Solve using move-to-front with advice"""
        current_list = list(range(1, self.list_size + 1))
        total_cost = 0
        advice_index = 0
        bits_per_access = math.ceil(math.log2(self.list_size))
        
        for item in access_sequence:
            if item in current_list:
                if advice_index + bits_per_access <= len(advice):
                    # Use advice to find position
                    position_bits = advice[advice_index:advice_index + bits_per_access]
                    position = sum(bit * (2 ** (bits_per_access - 1 - i)) 
                                 for i, bit in enumerate(position_bits))
                    advice_index += bits_per_access
                else:
                    # No advice available - find position
                    position = current_list.index(item)
                
                total_cost += position + 1  # Cost is position + 1
                
                # Move to front
                current_list.remove(item)
                current_list.insert(0, item)
        
        return total_cost
    
    def solve_without_advice(self, access_sequence: List[int]) -> float:
        """Move-to-front heuristic without advice"""
        current_list = list(range(1, self.list_size + 1))
        total_cost = 0
        
        for item in access_sequence:
            if item in current_list:
                position = current_list.index(item)
                total_cost += position + 1
                
                # Move to front
                current_list.remove(item)
                current_list.insert(0, item)
        
        return total_cost
    
    def optimal_offline_cost(self, access_sequence: List[int]) -> float:
        """Compute optimal offline cost (simplified approximation)"""
        # This is a simplified calculation
        # Real optimal offline for list update is complex
        return len(access_sequence) * (self.list_size + 1) / 2

# Example usage
list_problem = ListUpdateProblem(list_size=5)
tester = AdviceComplexityTester(list_problem)

access_sequence = [1, 3, 2, 1, 4, 2, 5, 1, 3]
results = tester.analyze_trade_off(access_sequence, max_advice_bits=20)
tester.print_analysis(results)

class PracticalCacheWithPrediction:
    """Cache with machine learning predictions about future accesses"""
    
    def __init__(self, cache_size: int):
        self.cache_size = cache_size
        self.cache = {}
        self.access_times = {}
        self.prediction_accuracy = 0.8  # 80% accurate predictions
    
    def predict_next_access(self, page: int, current_time: int) -> int:
        """Predict when page will be accessed next (simulated ML model)"""
        # Simplified prediction model
        if random.random() < self.prediction_accuracy:
            # Accurate prediction
            return current_time + random.randint(1, 10)
        else:
            # Inaccurate prediction
            return current_time + random.randint(50, 100)
    
    def cache_with_prediction(self, request_sequence: List[int]):
        """Cache algorithm using ML predictions as 'advice'"""
        total_cost = 0
        current_time = 0
        
        for page in request_sequence:
            current_time += 1
            
            if page in self.cache:
                # Cache hit
                self.access_times[page] = current_time
                continue
            
            # Cache miss
            total_cost += 1
            
            if len(self.cache) < self.cache_size:
                # Cache not full
                self.cache[page] = True
                self.access_times[page] = current_time
            else:
                # Cache full - evict page with furthest predicted next access
                evict_page = None
                furthest_prediction = -1
                
                for cached_page in self.cache:
                    next_access = self.predict_next_access(cached_page, current_time)
                    if next_access > furthest_prediction:
                        furthest_prediction = next_access
                        evict_page = cached_page
                
                # Evict and add new page
                del self.cache[evict_page]
                del self.access_times[evict_page]
                self.cache[page] = True
                self.access_times[page] = current_time
        
        return total_cost

# Compare prediction-based caching with standard algorithms
prediction_cache = PracticalCacheWithPrediction(cache_size=3)
requests = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] * 3

pred_cost = prediction_cache.cache_with_prediction(requests)
lru_hits, lru_misses, lru_cost = simulate_caching(requests, 3, "LRU")

print(f"\nPractical Application Comparison:")
print(f"Prediction-based cache cost: {pred_cost}")
print(f"LRU cache cost: {lru_cost}")
print(f"Improvement: {(lru_cost - pred_cost) / lru_cost * 100:.1f}%")

class DistributedLoadBalancerWithAdvice:
    """Load balancer using predictions about job characteristics"""
    
    def __init__(self, num_servers: int):
        self.num_servers = num_servers
        self.server_loads = [0.0] * num_servers
        self.server_specializations = {}  # Server capabilities
    
    def assign_with_job_prediction(self, jobs: List[Tuple[float, str]]):
        """Assign jobs using predicted job types as advice"""
        total_makespan = 0
        
        for job_size, job_type in jobs:
            # Use job type as "advice" to make better assignment
            best_server = 0
            best_score = float('inf')
            
            for i in range(self.num_servers):
                # Score = current_load + job_size + type_penalty
                type_penalty = 0
                if job_type in self.server_specializations.get(i, set()):
                    type_penalty = -0.2 * job_size  # 20% efficiency bonus
                
                score = self.server_loads[i] + job_size + type_penalty
                
                if score < best_score:
                    best_score = score
                    best_server = i
            
            # Assign job to best server
            self.server_loads[best_server] += job_size
            
            # Update server specialization (learning)
            if best_server not in self.server_specializations:
                self.server_specializations[best_server] = set()
            self.server_specializations[best_server].add(job_type)
        
        return max(self.server_loads)

# Example with job type predictions
jobs = [
    (4.0, "CPU"), (3.0, "IO"), (2.0, "CPU"), (8.0, "Memory"),
    (1.0, "IO"), (5.0, "CPU"), (2.0, "Memory"), (6.0, "IO")
]

lb_with_advice = DistributedLoadBalancerWithAdvice(num_servers=3)
makespan_with_advice = lb_with_advice.assign_with_job_prediction(jobs)

# Compare with simple greedy (no job type information)
simple_jobs = [job[0] for job in jobs]  # Just sizes
result = compare_online_offline_scheduling(simple_jobs, num_machines=3)

print(f"\nLoad Balancing with Job Type Advice:")
print(f"With job type advice: {makespan_with_advice:.2f}")
print(f"Simple greedy: {result['online_makespan']:.2f}")
print(f"Improvement: {(result['online_makespan'] - makespan_with_advice) / result['online_makespan'] * 100:.1f}%")

class OnlineLearningWithAdvice:
    """Online learning algorithm with advice about data distribution"""
    
    def __init__(self, num_features: int):
        self.num_features = num_features
        self.weights = [0.0] * num_features
        self.learning_rate = 0.1
        self.total_regret = 0
    
    def online_gradient_descent(self, data_stream, advice_about_optimum=None):
        """Online gradient descent with optional advice about optimum"""
        for i, (features, label) in enumerate(data_stream):
            # Make prediction
            prediction = sum(w * f for w, f in zip(self.weights, features))
            loss = (prediction - label) ** 2
            
            # Compute gradient
            gradient = [2 * (prediction - label) * f for f in features]
            
            # Update with advice if available
            if advice_about_optimum and i < len(advice_about_optimum):
                # Use advice to adjust learning rate
                advised_direction = advice_about_optimum[i]
                current_direction = [-g for g in gradient]
                
                # If advice aligns with gradient, increase learning rate
                alignment = sum(a * c for a, c in zip(advised_direction, current_direction))
                adaptive_lr = self.learning_rate * (1 + 0.5 * max(0, alignment))
            else:
                adaptive_lr = self.learning_rate
            
            # Update weights
            self.weights = [w - adaptive_lr * g for w, g in zip(self.weights, gradient)]
            self.total_regret += loss
        
        return self.total_regret

# This represents an active area of research combining
# traditional advice complexity with modern ML techniques

class EnergyEfficientSchedulingWithAdvice:
    """Schedule tasks with energy advice (renewable energy predictions)"""
    
    def __init__(self, num_processors: int):
        self.num_processors = num_processors
        self.processor_states = ['idle'] * num_processors  # idle, active, sleep
        self.energy_consumed = 0
        
    def schedule_with_energy_forecast(self, tasks, energy_forecast):
        """Schedule tasks using renewable energy predictions"""
        time = 0
        
        for task_duration in tasks:
            # Use energy forecast as advice
            if time < len(energy_forecast):
                renewable_available = energy_forecast[time]
            else:
                renewable_available = 0.5  # Assume average availability
            
            # Choose processor and frequency based on renewable energy
            if renewable_available > 0.8:
                # High renewable energy - use high frequency
                frequency_multiplier = 1.5
                energy_cost = task_duration * 0.8  # Efficient with renewables
            elif renewable_available > 0.4:
                # Medium renewable energy - standard frequency
                frequency_multiplier = 1.0
                energy_cost = task_duration * 1.0
            else:
                # Low renewable energy - reduce frequency to save energy
                frequency_multiplier = 0.7
                energy_cost = task_duration * 1.3  # Less efficient but lower total energy
            
            # Execute task
            execution_time = task_duration / frequency_multiplier
            self.energy_consumed += energy_cost
            time += execution_time
        
        return self.energy_consumed, time

# Example usage
tasks = [2, 4, 1, 3, 2, 5]  # Task durations
energy_forecast = [0.9, 0.7, 0.3, 0.8, 0.6, 0.4]  # Renewable energy availability

scheduler = EnergyEfficientSchedulingWithAdvice(num_processors=2)
total_energy, total_time = scheduler.schedule_with_energy_forecast(tasks, energy_forecast)

print(f"\nEnergy-Efficient Scheduling:")
print(f"Total energy consumed: {total_energy:.2f}")
print(f"Total execution time: {total_time:.2f}")

class AdviceComplexityProofFramework:
    """Framework for constructing advice complexity proofs"""
    
    @staticmethod
    def adversary_argument(problem_name: str, advice_bits: int):
        """Construct adversarial input based on advice bits"""
        if problem_name == "paging":
            # Classical adversary for paging
            print(f"Adversary construction for paging with {advice_bits} advice bits:")
            print("1. Force k+1 distinct pages to cause k misses")
            print("2. With b advice bits, can encode 2^b different strategies")
            print("3. Adversary can choose from 2^b + 1 pages to defeat any strategy")
            print(f"4. Lower bound: Ω({advice_bits}) bits needed for significant improvement")
    
    @staticmethod
    def information_theoretic_bound(input_space_size: int, optimal_solutions: int):
        """Compute information-theoretic lower bound"""
        bits_needed = math.ceil(math.log2(optimal_solutions))
        print(f"Information-theoretic analysis:")
        print(f"Input space size: {input_space_size}")
        print(f"Number of distinct optimal solutions: {optimal_solutions}")
        print(f"Bits needed to encode optimal solution: {bits_needed}")
        return bits_needed
    
    @staticmethod
    def reduction_proof(problem_a: str, problem_b: str):
        """Show advice complexity relationship via reduction"""
        print(f"Reduction from {problem_a} to {problem_b}:")
        print("1. Given instance of problem A")
        print("2. Construct instance of problem B")
        print("3. Show that advice for B yields advice for A")
        print("4. Conclude advice complexity relationship")

# Example proof framework usage
proof_framework = AdviceComplexityProofFramework()

proof_framework.adversary_argument("paging", advice_bits=10)
print()
proof_framework.information_theoretic_bound(input_space_size=1000, optimal_solutions=256)
print()
proof_framework.reduction_proof("ski_rental", "paging")

def create_research_toolkit():
    """Tools for conducting advice complexity research"""
    
    toolkit = {
        "simulation_framework": "For testing algorithms on various inputs",
        "visualization_tools": "Plot advice-performance trade-offs",
        "proof_verification": "Check mathematical arguments",
        "benchmark_problems": "Standard problem instances for comparison"
    }
    
    # Example: Benchmark problem generator
    def generate_benchmark_instances(problem_type: str, size: int):
        if problem_type == "paging":
            # Generate challenging paging sequences
            instances = []
            for i in range(10):
                # Create sequence with known optimal cost
                sequence = list(range(1, size + 2)) * (i + 1)
                random.shuffle(sequence)
                instances.append(sequence)
            return instances
        
        elif problem_type == "load_balancing":
            # Generate job sequences with different characteristics
            instances = []
            for i in range(10):
                jobs = [random.uniform(0.1, 10.0) for _ in range(size)]
                instances.append(jobs)
            return instances
    
    return toolkit, generate_benchmark_instances

toolkit, benchmark_gen = create_research_toolkit()
paging_benchmarks = benchmark_gen("paging", size=20)
print(f"Generated {len(paging_benchmarks)} paging benchmark instances")