FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.

Search by name or topic

RoundYearContent

Easy42

Geometry 1

Geometry & formulas 1

Strings 1

Prefix balance 1

Interval distance 1

Array extrema 1

Distance to a rectangle 1

Sieve 1

Reachability DP 1

Interval union 1

Breadth-first search 1

Sparse counting 1

Subarray counting 1

Expression parsing 1

Big integers 1

Modular arithmetic 1

Dynamic programming 4

Enumeration 1

Frequency counting 1

Board simulation 1

Two pointers 1

Binary search 2

Permutation adjacency 1

Recurrences & base three 1

Two pointers 1

Sorting & contributions 1

Prime numbers 1

Unbounded knapsack 1

Counting contributions 1

Tree traversal 1

Unbounded knapsack 1

Game dynamic programming 1

Binary search on answer 1

Algebraic aggregation 1

Flood fill 1

Prefix XOR 1

Matrix exponentiation 1

Disjoint set union 1

Medium68

Permutations 1

Backtracking 1

Enumeration 2

Knapsack 1

Disjoint sets 1

Breadth-first search 2

Coordinate compression 1

Big integers 1

Disjoint set union 1

Dynamic programming 1

Greedy coverage 1

Persistent stack 1

Normalized directions 1

0-1 BFS 1

Dynamic programming 1

Heaps 1

Two-dimensional knapsack 1

Multidimensional prefix sums 1

Circular intervals & sweep line 1

Counting tree embeddings 1

Dynamic programming 1

Subset sum 1

Topological sorting 1

Binary search 1

Z algorithm 1

Grid dynamic programming 1

Pythagorean triples 1

Prefix sums & integer search 1

Greedy scheduling 1

Algebraic enumeration 1

Gray code 1

Stacks 1

Prime sieve 1

Subsequence dynamic programming 1

Digit counting 1

Bitsets 1

Functional graphs 1

Parity disjoint sets 1

Extended Euclidean algorithm 1

Longest bitonic subsequence 1

Prefix parity 1

Sorting 1

Monotone stacks & DAG DP 1

Prefix sums 1

Rank dynamic programming 1

Interval dynamic programming 1

Suffix enumeration 1

Fenwick order statistics 1

Sweep line 2

Sliding window & DP 1

Bitwise subarray counting 1

Stern-Brocot tree 1

Subset dynamic programming 1

Ordered sets 1

Triangle inequality & prefix minima 1

Computational geometry 1

Interactive bit recovery 1

Earliest deadline scheduling 1

DAG dynamic programming 1

Prefix maxima 1

Convex hull 1

Game theory 1

Segment intersection & DSU 1

Palindrome dynamic programming 1

Dynamic programming & monotonic queues 1

Hard69

Diophantine equations 1

Tree rerooting 1

Rectangle nesting sweep 2

Monotone stack 1

Implicit graph reachability 1

Expression trees 1

Computational geometry 1

DFS & ordered sets 1

Tree path decomposition 1

Number theory 1

Bipartite matching 1

Offline heavy/light decomposition 1

Sweep line 1

Tree binary lifting 1

Bellman–Ford & zero cycles 1

Truncated big integers 1

Interval dynamic programming 1

Topological sorting 1

KMP borders & expected waiting time 1

Interactive topological sorting 1

Monotone stack and DAG 1

Combinatorial recurrence 1

Convex optimization 1

Difference arrays and Fenwick tree 1

Matrix segment tree 1

Dynamic programming 1

Cached comparison sorting 1

Matrix exponentiation 1

Combinatorial unranking 1

Upper convex hull tangents 1

Greedy path decomposition 1

Lexicographic topological ordering 1

Vertex-disjoint paths 1

Tree rerooting 1

Incremental bipartite matching 1

Partition dynamic programming 1

Lowest common ancestor 1

Suffix array and LCP 1

Monotonic stack 1

Multiset reconstruction 1

Rectangle dynamic programming 1

Flow and binary search 1

Inclusion–exclusion & linear sieve 1

Euler totient and divisors 1

Computational geometry 1

Digit dynamic programming 1

Permutation parity 1

Monotone stacks & binary lifting 1

Möbius inversion 1

Aho–Corasick and KMP 1

Path-integrated updates 1

Bounded precomputation 1

Constraint propagation 1

Articulation points and binary search 1

Polynomials & offline queries 1

Two-dimensional range maximum 1

Convex rearrangement 1

Bitmask game dynamic programming 1

Range minimum queries 1

Polynomial construction 1

Heavy-light counting 1

Bitsets and short cycles 1

Recursive interval aggregation 1

Expression interval dynamic programming 1

Sweep line and binary search 1

Offline sweep and Fenwick tree 1

Bipartite matching strategy 1

Greedy finite trajectory coverage 1

Very hard38

Greedy contraction & priority queue 1

Transfer matrices 1

Interactive divide and conquer 1

Geometric coverage 1

Monge dynamic programming 1

Function monoid & lazy segment tree 1

Periodic digit arithmetic 1

String dynamic programming 1

Number theory enumeration 1

Layered 0–1 BFS in a stack language 1

Lazy segment trees by digit length 1

Heavy-light decomposition and lazy assignment 1

Bitmask Kruskal 1

Interactive periodicity 1

Algebraic scored construction 1

Lipschitz branch and bound 1

Geometry and compressed walk counting 1

Offline subset sums and blocked bit ranks 1

Implicit Dijkstra and segment trees 1

Bipartite matching 1

Sweep line 1

Constructive geometry 1

Cactus graph 1

Ghost trajectories and binary search 1

Suffix array and reverse processing 1

Tree coverage dynamic programming 1

Linear greedy skyline 1

Counterfactual regret minimization 1

Information-state search 1

Interactive elimination 1

Finite-state randomness recycling 1

DFS graph encoding 1

Bayesian Monte Carlo 1

Convex envelope search 1

Persistent heapsort 1

Dynamic Euler-tour aggregates 1

Geometric construction 1

Communication protocol 1

Try the problem yourself before reading the analysis. Solutions use C++17. Special grader headers and compiler requirements are explained on affected tasks.

GROUP AB2016 · MediumStern-Brocot tree

Common Ancestor of Fractions

National Olympiad — National round (2016 season)

Submission name: rat.cpp

Solve in Editor →

Problem summary

In the Stern–Brocot tree rooted at 1/1, find the fraction at the lowest common ancestor of a node specified by its breadth-first index and a node specified by its reduced fraction.

Input

Index n1, then numerator a2 and denominator b2.

Output

Ancestor numerator and denominator.

Constraints

1 < n1 < 10^18; 0 < a2,b2 < 10^9; gcd(a2,b2)=1; the two specified nodes are different and neither is the root.

Worked example

An independently prepared example for this explanation.

Input

5
1 4

Output

1 2

Solution analysis

The binary expansion of a breadth-first index begins with the root bit 1. Each remaining bit is a tree direction: 0 goes left and 1 goes right. This first node has fewer than 60 directions.
Generate the path toward a2/b2 only as far as those directions. Maintain lower bound 0/1 and upper bound 1/0; their mediant is the current node. Compare the target fraction with the mediant to determine left or right. Stop on equality or at the first differing direction.
Index 5 is binary 101, giving left then right and fraction 2/3. The path to 1/4 begins left then left. Their common prefix is one left move, whose node is 1/2. There is no need to construct a potentially enormous full path to 1/4 or another fraction.

Why it works

A node’s root path uniquely identifies its ancestors, and the deepest shared prefix identifies its lowest common ancestor. Binary index directions recover the first path exactly. Stern–Brocot mediant comparisons recover every required direction of the second path. Stopping at their first divergence or at an endpoint therefore returns precisely the deepest shared ancestor.

Complexity: O(log n1) time and space. At each comparison, the current node is an ancestor of the target fraction, so its numerator and denominator do not exceed the target components. Thus cross-products are below 10^18 and fit signed 64-bit.

Watch out. Do not follow subtractive Euclid all the way to a target with huge depth. Only the first node’s short path can belong to the common prefix.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: The binary expansion of a breadth-first index begins with the root bit 1.
using namespace std;
int main(){
    long long index,numerator,denominator;
    cin>>index>>numerator>>denominator;
    vector<int>directions;
    while(index>1){
        directions.push_back(static_cast<int>(index%2));
        index/=2;
    }
    reverse(directions.begin(),directions.end());
    long long leftNum=0,leftDen=1,rightNum=1,rightDen=0;
    for(int direction:directions){
        long long currentNum=leftNum+rightNum;
        long long currentDen=leftDen+rightDen;
        long long targetSide=numerator*currentDen-denominator*currentNum;
        if(targetSide==0||(targetSide>0)!=(direction==1)){
            break;
        }
        if(direction==0){
            rightNum=currentNum;
            rightDen=currentDen;
        }
        else{
            leftNum=currentNum;
            leftDen=currentDen;
        }
    }
    cout<<leftNum+rightNum<<' '<<leftDen+rightDen<<'\n';
}

Source: Arena Olimpiici ↗

Proficient.Put your skills to the test.

Common Ancestor of Fractions

Problem summary

Input

Output

Constraints

Worked example

Input

Output

Solution analysis

Why it works

Commented C++17 solution

Choose your next challenge.

Proficient.
Put your skills to the test.