Clasa a XII-a · high schoolCitește în română
Grade 12 algorithmsClasa a XII-a
The grade 12 part of the collection, chapter by chapter. Read the idea, run the code against the examples and track what you've learned.
- 50algorithms
- 6chapters
- 1grade
50 algorithms
Grade 12Clasa a XII-a
0%0%
Big numbers
Numere mari · 9 algorithms
- Adding two big numbersAdunarea a două numere mariWe add as on paper, from the units to the left. At position i we compute s = a[i] + b[i] + carry; the result digit is s % 10, and the new carry is s…
- Reading and printing a big numberCitirea și afișarea unui număr mareA number with tens or hundreds of digits does not fit in long long, so we read it as a string and keep its digits in an array, starting with the…
- Comparing two big numbersCompararea a două numere mariWithout leading zeros, the number with more digits is larger. If they have the same number of digits, we compare them from the most significant…
- Factorial as a big numberFactorialul unui număr mareAlready 21! exceeds long long, but n! = 1 * 2 * ... * n can be built by repeatedly multiplying a big number by a small one. We start from the array…
- The n-th Fibonacci term (big number)Termenul n din șirul lui Fibonacci (număr mare)The sequence is F(1) = F(2) = 1 and F(i) = F(i - 1) + F(i - 2). The terms grow exponentially (F(93) no longer fits in long long), so we keep them as…
- Dividing a big number by a small numberÎmpărțirea unui număr mare la un număr micUnlike addition, division starts from the most significant digit, exactly like long division on paper. We keep the remainder r; for every digit we…
- Multiplying two big numbersÎnmulțirea a două numere mariThe digit a[i] (rank 10^i) multiplied by the digit b[j] (rank 10^j) contributes to rank 10^(i+j). We first add all the products into c[i + j],…
- Multiplying a big number by a small numberÎnmulțirea unui număr mare cu un număr micThe small number k (at most 10^9) fits in an int, so it does not need to be split into digits. For every digit a[i], from the units, we compute t =…
- Subtracting two big numbersScăderea a două numere mariWe compute A - B. If A < B, we compute B - A and put a minus sign in front. We subtract from the units: d = a[i] - b[i] - borrow; if d comes out…
0%
Grid algorithms: Lee and flood fill
Algoritmi pe grile: Lee și fill · 6 algorithms
- Flood fill: the largest regionFill — cea mai mare zonăThe same matrix of 0s and 1s, but now we want the number of cells of the largest region of 1s (adjacency through sides). This time the fill is done…
- Flood fill: the number of regionsFill — numărul de zoneThe matrix has n rows and m columns, with 1 for land and 0 for water. A region is a maximal group of 1 cells connected through their sides (up,…
- Islands in 8 directionsInsule în 8 direcțiiLike counting regions, but two land cells (1) belong to the same island if they touch even at a corner, i.e. the neighbourhood has 8 directions. The…
- Lee with multiple sourcesLee cu mai multe surseThe grid holds 0 (free), 1 (wall) and 2 (source, for example a well). For every free cell we want the minimum number of steps to the nearest source.…
- Lee: the shortest path in a gridLee — drumul minim într-o grilăThe grid has n rows and m columns: 0 = free, 1 = obstacle. We can move up, down, left, right. Lee's algorithm is a breadth-first search: d[xs][ys] =…
- Lee with path reconstructionLee cu reconstituirea drumuluiAfter Lee has filled the distance matrix, the path is rebuilt from the end towards the start: if we are in a cell with value k, one of its…
0%
Math for programming
Matematică pentru programare · 9 algorithms
- Smallest-prime-factor sieve and fast factorizationCiur cu cel mai mic divizor prim și factorizare rapidăA variant of the Sieve of Eratosthenes: instead of only marking 'composite', we store in dp[x] the smallest prime divisor of x. For every prime p…
- Combinations modulo a primeCombinări modulo un număr primWe compute C(n, k) mod P, with P = 1,000,000,007 (prime) and n ≤ 10^6. We have C(n, k) = n! / (k! * (n-k)!), but division cannot be done directly on…
- Extended Euclidean algorithmAlgoritmul lui Euclid extinsBesides d = gcd(a, b), we find integers x and y with a * x + b * y = d. If b = 0, then d = a, x = 1, y = 0. Otherwise we solve recursively for (b, a…
- Modular exponentiationExponențierea modularăWe compute a^n mod m for n up to 10^18. We use the same idea as fast exponentiation, but after every multiplication we take the remainder modulo m:…
- Fast exponentiationExponențierea rapidăWe compute a^n with about log2(n) multiplications instead of n. The idea: a^n = (a^2)^(n/2) if n is even and a^n = a * a^(n-1) if n is odd. The…
- Number and sum of divisors from the prime factorizationNumărul și suma divizorilor din descompunerea în factori primiIf n = p1^e1 * p2^e2 * ... * pk^ek, a divisor chooses for every prime an exponent between 0 and ei, so the number of divisors is (e1 + 1) * (e2 + 1)…
- Number of multiples of k in a rangeNumărul multiplilor lui k dintr-un intervalHow many numbers in [a, b] are divisible by k? The numbers in [1, x] divisible by k are k, 2k, ..., (x / k) * k, i.e. x / k of them (integer…
- Sum of an arithmetic progression: formula vs. loopSuma unei progresii aritmetice: formulă vs. buclăThe progression has first term a, common difference r and n terms: a, a + r, ..., a + (n-1) * r. The loop adds the terms one by one, so it takes n…
- Pascal's triangle (combinations)Triunghiul lui Pascal (combinări)The combinations C(i, j), the number of j-element subsets of an i-element set, satisfy C(i, j) = C(i-1, j-1) + C(i-1, j): either we choose element…
0%
Advanced techniques: two pointers, binary search on the answer, monotonic stacks
Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone · 7 algorithms
- Binary search on the answerCăutare binară pe răspunsWe have n chapters with a[i] pages, in order, and k proofreaders. Every proofreader gets a run of consecutive chapters. We want the busiest…
- Two pointers: pairs with sum x in a sorted arrayDoi pointeri — perechi cu suma x într-un vector sortatThe array has n distinct values in strictly increasing order. We want the position pairs i < j with a[i] + a[j] = x. Instead of trying all n * (n-1)…
- Majority element (Boyer-Moore)Element majoritar (Boyer-Moore)The majority element appears more than n / 2 times. The voting algorithm keeps a candidate and a counter: a value equal to the candidate increases…
- Sliding window: the longest subarray with sum ≤ SFereastra glisantă — cea mai lungă secvență cu suma ≤ SAll numbers are strictly positive. We keep a window [st, dr] and its sum. We always extend the right end by one element; while the sum exceeds S, we…
- Monotonic stack: the next greater elementStiva monotonă — următorul element mai mareFor every a[i] we look for the first strictly greater value to its right (or -1). We keep a stack with the positions still 'waiting' for a greater…
- Generating subsets with bitmasksGenerarea submulțimilor cu măști de bițiA subset of {a[0], ..., a[n-1]} can be encoded as a number masca between 0 and 2^n - 1: bit i of the mask is 1 if a[i] belongs to the subset. Bit i…
- 2D prefix sumsSume parțiale pe matrices[i][j] = the sum of the elements in the rectangle with corners (1, 1) and (i, j). It is computed once: s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] -…
0%
Data structures and the STL
Structuri de date și STL · 9 algorithms
- deque: sliding window minimum of length kdeque — minimul pe ferestre de lungime kFor every run of k consecutive elements we want the minimum. We keep the 'candidate' positions in a deque, with values increasing from front to…
- queue: elimination in a circle (Josephus)queue — eliminarea din cercn children, numbered from 1 to n, stand in a circle. We count k at a time, and the child where the count stops leaves the game; counting continues…
- pair: union of intervalspair — reuniunea intervalelorpair<int, int> groups two values (first, second) and compares lexicographically: first by first, then by second. So sort on an array of pairs orders…
- stack: checking bracketsstack — verificarea parantezelorA string with the brackets (), [] and {} is correct if every closing bracket matches the last opening bracket still left open. 'Last opened, first…
- priority_queue: the k largest valuespriority_queue — cele mai mari k valoripriority_queue is a heap: top() gives the 'most important' element, and push and pop cost O(log size). By default the top is the maximum; with…
- set and map: word frequencyset și map — frecvența cuvintelorWe read words (lowercase letters) until the end of the input. A set<string> keeps every word once, in alphabetical order, so size() gives the number…
- Sorting with a comparatorSortare cu comparatorsort(begin, end, cmp) orders by our own rule: cmp(x, y) returns true if x must come before y. Here we sort the contestants of a competition by score…
- Disjoint-set forests (union-find)Păduri de mulțimi disjuncte (union-find)We have n elements, each initially in its own set. Operation 1 x y joins the sets of x and y, and operation 2 x y asks whether x and y are in the…
- The STL vector containerContainerul vector din STLvector<int> is an array that manages its own memory: push_back adds at the end (O(1) on average), size() gives the number of elements, and v[i]…
0%
Baccalaureate exam review
Recapitulare pentru bacalaureat · 10 algorithms
- File: the largest and smallest number formed from given digitsFișier — cel mai mare și cel mai mic număr format din cifre dateThe task (exam part III.3 style): the file date.in holds at most 10^6 digits separated by spaces. Using all the digits, each exactly once, print on…
- File: pairs of numbers with the same digit sumFișier — perechi de numere cu aceeași sumă a cifrelorThe task (exam part III.3 style): the file date.in holds n (2 ≤ n ≤ 10^6) on the first line, then n natural numbers with at most 9 digits. Print how…
- File: the longest run of terms with the same parityFișier — cea mai lungă secvență de termeni cu aceeași paritateThe task (exam part III.3 style): the file date.in holds a sequence of at most 10^6 natural numbers with at most 9 digits. A parity run is a run of…
- File: the common values of two sorted sequencesFișier — valorile comune a două șiruri ordonateThe task (exam part III.3 style): the file date.in holds n and m (1 ≤ n, m ≤ 10^5) on the first line, n natural numbers in increasing order on the…
- File: the values that appear exactly onceFișier — valorile care apar o singură datăThe task (exam part III.3 style): the file date.in holds at most 10^6 natural numbers with at most three digits, separated by spaces. Print on the…
- Matrix: concentric bordersMatrice — contururi concentriceThe task (exam part III.2 style): n is read (2 ≤ n ≤ 20). Build in memory a matrix with n rows and n columns in which the elements on the outer…
- Subprogram: the number formed from the even digitsSubprogram — numărul format din cifrele pareThe task (exam part III.1 style): the subprogram pare has a parameter n (0 ≤ n ≤ 10^9) and returns the number formed from the even digits of n, in…
- Subprogram: how many numbers in a range have an odd number of divisorsSubprogram — câte numere dintr-un interval au un număr impar de divizoriThe task (exam part III.1 style): the subprogram impare has the parameters a and b (1 ≤ a ≤ b ≤ 10^12) and returns how many numbers in [a, b] have…
- Subprogram: removing the elements with k digits from an arraySubprogram — eliminarea elementelor cu k cifre dintr-un tablouThe task (exam part III.1 style): the subprogram elimina has the parameters v (an array of n natural numbers), n and k; it deletes from v all…
- Text: reversing the words of even lengthText — inversarea cuvintelor de lungime parăThe task (exam part III.2 style): a text of at most 100 characters is read, made of lowercase words separated by single spaces. Print the text in…