Locate an Occurrence in Symmetric Blocks
National Olympiad — Regional round (2019 season)
Submission name: sequence.cpp
Problem summary
Concatenate integer blocks [1],[1,2,1],[1,2,3,2,1],… and find the 1-based position of the k-th occurrence of n. Elements are integers, not decimal digits.
Input
n k.
Output
The occurrence position.
Constraints
1 ≤ n,k ≤ 10^6.
Worked example
Input and output for the worked example discussed below.
Input
3 3
Output
14
Solution analysis
- Block M has 2M−1 elements, so all previous blocks together contain (M−1)² elements. Number n first appears in block n at offset n.
- Each subsequent block has n twice, at offsets n and 2M−n. Occurrence k lies in M=n+floor(k/2); use offset n for even k and 2M−n for odd k. This also handles k=1.
- For n=3,k=3, block 4 contains the third occurrence at offset 5. Nine prior elements give position 14.
Why it works
Block lengths sum to squares and the one-first-then-paired occurrence pattern uniquely determines the location.
Complexity: O(1) time and O(1) space.
Watch out. Use long long for squared indices; do not split multi-digit values into digits.
Commented C++17 solution
An independently written complete program with standard headers.
// Block lengths sum to squares and the one-first-then-paired occurrence pattern uniquely determines the
// location.
#include<iostream>
using namespace std;
int main(){
long long value,occurrence;
cin>>value>>occurrence;
long long block=value+occurrence/2;
long long offset=occurrence%2==0?value:2*block-value;
cout<<(block-1)*(block-1)+offset<<'\n';
}