FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.

Search by name or topic

Round / tournamentYearContent

Easy96

Counting 2

Digits 1

Arithmetic 1

Simulation 1

Sorting 2

Big integers 1

Counting 1

Number Theory 1

Strings 1

Arrays and counting 2

Simulation 1

Frequency counting 5

Grid simulation 1

Arithmetic indexing 1

Integer indexing 1

Sets and distinct values 1

Grid scanning 1

Sorting and checking 1

String conversion 1

Run counting 1

Arithmetic and greedy choice 1

Triangle inequalities 1

Combinatorial counting 1

Contribution counting 1

Geometry and boundary updates 1

Prefix sums 2

Arithmetic and digit scanning 1

String arithmetic 1

Digit sequences 1

Strings and positional weights 1

Character frequencies 1

String parsing 2

String scanning 2

Array scanning 2

Prime exponents 1

Permutations 1

Inverse permutations 1

Sequence scanning 1

Circular simulation 1

Digits and divisibility 1

Combinatorics 1

Number bases 1

Geometry enumeration 1

Digit frequency counting 1

Prefix sums and compact storage 1

Circular arrays 1

Periodic simulation 1

Digit arithmetic 1

Suffix maxima 1

Bounded enumeration 2

Sorting by elapsed time 1

Sequence simulation 2

Time simulation 1

Distinct graph neighbours 1

Coordinate geometry 1

Binary Search 1

Interval intersections 1

Calendar arithmetic 1

Geometric sums 1

Previous and next occurrence arrays 1

Precomputation 1

Sorting and simulation 1

Range queries 1

GCD and divisibility 1

Sequence generation 1

Grid rotation 1

Set intersection 1

LCM and arithmetic progressions 1

Euclidean algorithm 1

Window enumeration 1

Bijective base conversion 1

Frequency counting and sorting 1

Divisor enumeration 1

Two pointers on sorted arrays 1

Periodic prefix sums 1

Sorting distinct values 1

Numeral systems 1

Difference arrays 1

Digit sorting 1

Grid components 1

Sequence trend runs 1

Calendar simulation 1

Integer halving bounds 1

Medium142

Ranked Choice Simulation 1

Exhaustive search 2

Arrays and matrices 1

Number theory 1

Simulation 2

Sorting 1

Enumeration 1

Two Pointers 1

Number Theory 1

Strings and simulation 1

Big integers 1

Binary search 1

Binary Search 2

Strings 2

Arrays and counting 1

Sorting and greedy 1

Two pointers 1

Simulation 1

Rational Arithmetic 2

Combinatorial geometry 1

Invariants 1

Modular arithmetic 1

Arithmetic interval counting 1

Binary enumeration 1

Unbounded dynamic programming 1

Streaming digit sequence 1

Big integers 1

Digits and modular arithmetic 1

Fixed-event simulation 1

Frequency counting 2

Bounded-state simulation 1

Two-dimensional prefix sums 1

Prime factorization 3

Frequency inversion 1

Precomputation 1

Prefix and suffix maxima 1

Sorting and greedy 1

Bounding rectangles 1

String runs and simulation 1

Exact rational arithmetic 1

Permutation cycles 1

Partition dynamic programming 1

Sorting and runs 1

Greedy two pointers 1

Sorting and decimal subtraction 1

Boyer–Moore voting 1

Sieve and prefix sums 1

Functional graphs 1

Prime sieve and combinatorics 1

Packed presence bitmap 1

Counting formulas 1

Implicit sequence indexing 1

Constructive geometry 1

Big integer base conversion 1

Prime sieve and prefix sums 1

Geometry and indexing 1

Greedy interval traversal 1

Sorting by concatenation 1

Modular arithmetic and dates 1

Linear recurrence 1

Greedy representation 1

Two Pointers 2

Ordered set and streaming 1

Divisor enumeration 1

Cyclic shifts 1

Breadth-first search 1

Grid dynamic programming 2

Prime sieve 1

Area bounds and enumeration 1

Big integer arithmetic 1

Unbounded knapsack 1

Divisors and formulas 1

Local invariant updates 1

Divisor sieve and prefix sums 1

Sets and symmetry 1

Decimal arithmetic 1

Blocked-grid runs 1

Stacks and subset enumeration 1

Odd divisors 1

Prefix sums 2

Rectangle enumeration 1

Bitmask enumeration 1

Priority queue simulation 1

Big integer doubling 1

Prefix and suffix products 1

Greedy swaps 1

Date enumeration 1

Josephus formula 1

Hypothesis enumeration 1

Grid path invariants 1

Greedy 1

Big integer multiplication 1

Matrix exponentiation 1

String permutation 1

Sorting and two pointers 1

Digit arithmetic 1

Two pointers on positions 1

Stacks and dynamic programming 1

Dynamic programming 1

Sorting and sliding windows 1

Segmented multiple marking 1

Pair-sum preprocessing 1

Periodic indexing 1

Digit dynamic programming 1

Grid scanning 1

Positional digit counting 1

Integer binary search 1

Counting 1

Coprime directions and inclusion-exclusion 1

Multi-source BFS 1

Piecewise volume simulation 1

LCM and modular arithmetic 1

Decimal convolution 1

Number Theory 1

Divisor pairs and LCM 1

Greedy matching 1

Sorting and grouping 1

Graphs 1

Greedy stack simulation 1

Robot Without Reversing 12

Hard32

String algorithms 1

Prefix Sums 1

Number Theory 1

Bitmasks 1

Fenwick order statistics 1

Monotonic stack 1

Bitset dynamic programming 1

Digit constraints 1

Big integers and enumeration 1

Number Theory 1

Fibonacci enumeration 1

Geometry and arithmetic sums 1

Prime sieve 1

Exact rational arithmetic 1

Linear recurrence and counting 1

Greedy digit allocation 1

Flood fill and geometry 1

Suffix DP and lexicographic reconstruction 1

Simulation 1

Monotonic stacks and contributions 1

Greedy string repair 1

Exhaustive search and construction 1

Lexicographic unranking 1

Coordinate compression and BFS 1

Divisors and remainder pairing 1

Cached grid simulation 1

Dijkstra on a hexagonal grid 1

Digit DP and big integers 1

Grid Hamiltonian cycle 1

Divisors and packing 1

Geometry and sweep line 1

Minimum-cost bipartite matching 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 D2016 · MediumDynamic programming

Minimum-Score Slalom

National Olympiad — National round (2016 season)

Submission name: slalom.cpp

Solve in Editor →

Problem summary

Pass gates in index order, optionally skipping any gate. Each visited gate and the finish add one point; travelled straight-line distances and skipped-gate penalties also add to the score. Find the smallest total.

Source clarification. One original score sentence prints a minus before penalties, but the stated penalty rule and official sample require adding them. This implementation follows that intended nonnegative penalty convention.

Input

Start and finish coordinates, M, then M rows x y penalty.

Output

The optimum score to three digits after the decimal point.

Constraints

0 ≤ M ≤ 25; coordinates and penalties are integers from 0 to 1000.

Worked example

Input and output for the worked example discussed below.

Input

0 0 100 100
3
30 30 90
60 60 80
10 90 10

Output

154.421

Solution analysis

Treat the start as vertex 0 and the finish as M+1. If the previous visited vertex is i and the next is j>i, the transition adds their Euclidean distance, one visit point, and all penalties of gates strictly between them.
Use prefix sums of penalties to obtain skipped penalties in O(1). Then dp[j] is the minimum over every earlier i of dp[i]+distance(i,j)+1+skippedPenalty(i,j), with dp[0]=0. This is a shortest path in an index-ordered DAG.
In the sample, visit gates 1 and 2 and skip gate 3. Start, gate 1, gate 2 and finish lie on the main diagonal, so distance is sqrt(20000); add three visit points and penalty 10, yielding 154.421.

Why it works

The last visited predecessor partitions every valid route uniquely into an optimal earlier route and one transition containing exactly its skipped penalties.

Complexity: O(M²) time for all predecessor pairs and O(M) space for coordinates, prefix sums and DP.

Watch out. The start earns no visit point, while the finish does. Penalties are added; the original text contains a contradictory minus sign in one sentence, but its penalty rule and sample require addition.

Commented C++17 solution

An independently written complete program with standard headers.

// The last visited predecessor partitions every valid route uniquely into an optimal earlier route and one
// transition containing exactly its skipped penalties..
#include<cmath>
#include<iomanip>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
    int sx,sy,fx,fy;
    cin>>sx>>sy>>fx>>fy;
    int gates;
    cin>>gates;
    vector<int>x(gates+2),y(gates+2),penalty(gates+2),prefix(gates+2);
    x[0]=sx;
    y[0]=sy;
    x[gates+1]=fx;
    y[gates+1]=fy;
    for(int gate=1;gate<=gates;gate++){
        cin>>x[gate]>>y[gate]>>penalty[gate];
        prefix[gate]=prefix[gate-1]+penalty[gate];
    }
    vector<double>best(gates+2,numeric_limits<double>::infinity());
    best[0]=0;
    for(int next=1;next<=gates+1;next++){
        for(int previous=0;previous<next;previous++){
            double distance=hypot(x[next]-x[previous],y[next]-y[previous]);
            best[next]=min(best[next],best[previous]+distance+1+prefix[next-1]-prefix[previous]);
        }
    }
    cout<<fixed<<setprecision(3)<<best.back()<<'\n';
}

Source: Arena Olimpiici ↗

Intermediate.Put your skills to the test.

Minimum-Score Slalom

Problem summary

Input

Output

Constraints

Worked example

Input

Output

Solution analysis

Why it works

Commented C++17 solution

Choose your next challenge.

Intermediate.
Put your skills to the test.