Freaks City

Problem Description Given a number triangle, where each number is placed above two numbers in the row below, find the maximum possible sum of a path starting from the top and moving to adjacent numbers on the row below until the base of the triangle is reached. For example, consider the following triangle: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 ...

A player collects trading cards with n distinct types. Each draw yields card type i with probability pi. Duplicate cards convert to coins, where k coins can be exchanged for one missing card. The process continues until all card types are collected. Compute the expected number of draws required. Input Format First line: n (card types) and k (co ...

Shortest Path DAG and Convex Hull Optimization This problem involves processing a transportation network where we need to compute both the shortest travel time and the maximum possible delay while still arriving on time. Solution Approach First, we construct the shortest path DAG by running Dijkstra's algorithm from the source node. Any edge no ...

A. Ribbon Coloring Strategy Alice's optimal strategy is to color the ribbon in a repeating pattern like "123123...". Bob's optimal counter-strategy is to recolor the ribbon to the most frequent color. The most frequent color appears at least ⌈n/m⌉ times, leaving Bob with at most (n - ⌈n/m⌉) recoloring operations. Compare this value wi ...

Problem D: DiviDuelo Approach This problem requires number theory analysis and prime factorization techniques. The solution involves categorizing cases based on the prime factorization of the input number. The implementation uses advanced primality testing and factorization algorithms including Miller-Rabin and Pollard's rho method. Implementat ...

Problem Statement Given a sequence \(a_1, a_2, \dots, a_n\), select elements to delete such that the remaining subsequence maximizes the count of indices \(i\) where \(a_i = i\). The goal is to compute this maximum value. Initial Solution and Limitations A dynamic programming approach tracks the longest subsequence satisfying \(a_j = j\) after ...

Simulation problems, often labeled as "warm-up" or "signature" tasks in contests, require translating problem statements directly into code without relying on predefined algorithms. While they appear simple, their difficulty lies in accurately interpreting edge cases and constraints. A single oversight in boundary checks or ...

Problem 1: Equalizing Elements via Modulo Problem Statement Given an array of integers, determine if it is possible to make all elements equal by repeatedly applying a modulo operation with an integer $x \ge 2$. In each step, every element $a_i$ is replaced by $a_i \bmod x$. Analysis The core constraint lies in the behavior of small numbers und ...

Equalizing Card Piles (Greedy Approach) To distribute cards equally among $N$ piles, calculate the average number of cards per pile and subtract this value from each pile's count. This transforms the problem into finding the minimum number of moves to zero out the differences. Iterating from left to right, if a pile has a non-zero discrpeancy, ...

Resource Redistribution with Asymmetric Operations Given a sequence (a) of length (n) and two positive integers (x, y) where (y \le x). You may repeatedly pick two elements and transfer resources: subtract (x) from one and add (y) to the other, provided the first remains non‑negative. Determine the maximum possible value of any element after op ...