cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2022 · MediumDistance Transform

Distinct Nearest Differences

National Olympiad — National round

Submission name: mindiff.cpp

Solve in Editor →

Problem summary

Generate A of length N by Ai=(i·L) mod P, then negate its first F entries. Generate B of length M by Bi=(i·R) mod Q, then negate its first G entries. Indices start at one. For every B value find its minimum absolute difference from any A value. Output the distinct resulting differences in descending order.

Input

N L P F on the first line; M R Q G on the second.

Output

Number of distinct differences; then those differences in descending order.

Constraints

1 ≤ N,M ≤ 20000000; 0 ≤ F ≤ N; 0 ≤ G ≤ M; 1 ≤ L,P,R,Q ≤ 4000000.

Worked example

An independently prepared example for this explanation.

Input

3 2 7 0
3 1 5 0

Output

2
1 0

Solution analysis

  1. All values lie in [−3999999,3999999]. Mark A values in an array over this bounded domain, generating residues incrementally.
  2. Scan left to right and right to left to compute distance to the nearest marked value for every coordinate.
  3. Stream B and mark each queried distance; print marked distances descending. The sequences themselves need not be stored.

Why it works

In one dimension, a nearest marked coordinate lies immediately to the left or right. The two scans compute the distance to these possibilities, and their minimum is exact. Streaming B then gives exactly the distinct requested answers.

Complexity: O(N+M+U) time and O(U) space, where U=2·max(P,Q)−1.

Watch out. Apply negation after generating the modular residue; negating the recurrence state changes later values incorrectly.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: In one dimension, a nearest marked coordinate lies immediately to the left or right. The
// two scans compute the distance to these possibilities, and their minimum is exact.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<iterator>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,l,p,f,m,r,q,g;
    cin>>n>>l>>p>>f>>m>>r>>q>>g;
    int bound=max(p,q)-1,U=2*bound+1,INF=100000000;
    vector<int>d(U,INF);
    int a=0;
    for(int i=1;i<=n;i++){
        a=(a+l)%p;
        d[(i<=f?-a:a)+bound]=0;
    }
    for(int i=1;i<U;i++){
        d[i]=min(d[i],d[i-1]+1);
    }
    for(int i=U-2;i>=0;i--){
        d[i]=min(d[i],d[i+1]+1);
    }
    vector<unsigned char>found(U);
    int b=0,count=0;
    for(int i=1;i<=m;i++){
        b=(b+r)%q;
        int v=d[(i<=g?-b:b)+bound];
        if(!found[v]){
            found[v]=1;
            count++;
        }
    }
    cout<<count<<'\n';
    for(int i=U-1;i>=0;i--){
        if(found[i]){
            cout<<i<<' ';
        }
    }
    cout<<'\n';
}

Source: Arena Olimpiici ↗