# zeena's unofficial sol/observations for Grade-9 HCMOI (19/3/2024)
###### Author: zeena (i2225 PTNK)
Was a bit late for this one
**Note: My sol isn't 100% correct, im still a cyan**

## Problem 1:
TLDR: You are stuck in a matrix with size of $N*N$
The exit is at $(1,N)$ and you are at $(N,1)$. This means you have to go up and right to reach the exit.
You are given 4 integers $a,b,c,d$ where:
- a,b: you can go up by exactly either $a$ or $b$ squares
- c,d: you can go right by exactly either $c$ or $d$ squares

In each move you either choose one of these 4 integers. What is the minimum number of moves needed to reach the exit?
If there's no such answer, print $-1$

**My approach:**
Note that you can only go up to reach the row axis of $1$ and go right to reach the column axis of $n$
Let:
- The numbers of $a,b$ needed be $x,y$ respectively
- The numbers of $c,d$ needed be $x',y'$ respectively

With these, we have two equations (i guess):
- $n - (ax+by) = 1 <=> ax + by = n-1$
- $1 + (cx'+dy') = n <=> cx' + dy' = n-1$

We can now find the smallest pairs of (x,y) and (x',y') that are the answers for those two equations above.
If an answer doesn't exist, print $-1$.
The final answer to the problem is $x+y+x'+y'$.

:::spoiler **Implementation (C++, stdin)**

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mod = 1e9+7;

int find(int a, int b, int n) {
    if (a>b) swap(a,b);
    int res = mod;
    if (b==0) return -1;
    if (a==0) {
        if (n%b==0) return n/b;
        else return -1;
    }
    for (int i=0; a*i<=n; ++i) {
        if ((n-(a*i))%b==0) {
            res = min(res, i + (n-(a*i))/b);
        }
    }
    if (res==mod) return -1;
    else return res;
}

void solve() {
    int n; cin >> n;
    int a,b,c,d; cin >> a >> b >> c >> d;
    if (n==1) {
        cout << 0;
        return;
    }
    int ans1 = find(a,b,n-1);
    int ans2 = find(c,d,n-1);
    if (ans1==-1 || ans2==-1) {
        cout << -1;
        return;
    }
    cout << ans1+ans2;
}

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
}

:::

##### **Observation:** shit problem
##### Difficulty (CF Based): around 1000-1200
##### Tags: Adhoc, Math

## Problem 2:

TLDR: Given array $A$ of $n$ elements, how many pair $(i,j)$ such that sum of the elements from $a[i]$ to $a[j]$ is at least k or more.

**Constraints:**
$1 \le k, a[i] \le 10^9$
**- sub 1: 90% $1 \le n \le [10^3,10^4]$**
**- sub 2: 10% $1 \le n \le [10^5,10^6]$**

#### The naive approach:
just use 3 for loops everything works fine
**Time Complexity: $O(n^3)$**
**Memory Complexity: $O(n)$**
#### Sub 1 approach:
To complete sub 1, you can use a prefix sum to calculate the sum of elements quickly.
The time complexity is reduced down to $O(n^2)$, meanwhile the memory complexity stays the same.
#### Sub 2 approach:
Note that every element in the prefix sum is always increasing, thus we can use **binary search** to find for each $i$, the lowest $j$ so that $f(i-1) + K \le f(j)$, then add $n-j+1$ to the answer since from $j$ to $n$ every prefix sum element is larger than $f(i-1) + K$

With this, the time complexity becomes $O(n.log(n))$

Another solution possible is to use 2-pointer technique. However, due to my lazyness, im not talking about this sol here.

:::spoiler **Implementation (C++, stdin)**

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for (int i=(a); i<=(int)(b); ++i)
#define all(a,n,i) (a)+(i), (a)+(n)+(i)
typedef long long ll;

const int maxN = 1e6+5;
const int mod = 1e9+7;

int n; 
ll a[maxN], f[maxN], k;

void solve() {  
    cin >> n >> k;
    FOR(i,1,n) {
        cin >> a[i];
        f[i] = f[i-1] + a[i];
    }
    ll ans = 0;
    FOR(i,1,n) {
        int j = (lower_bound(all(f,n,1), (f[i-1]+k)) - f);
        ans+=(n-j+1);
    }    
    cout << ans;
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
}

:::

##### **Observation:** average problem imo
##### Difficulty (CF Based): for this i guess it's around 1100-1300
##### Tags: DS, BS, 2PT

## Problem 3:
TLDR: With $l,r$ denoting the number of digits $(l \le r)$ in $q$ queries, how many numbers whose number of digits is in range $[l,r]$ with sum of their digits are prime?
**Note: prime numbers are numbers with only 2 divisors: 1 and themselves except 0 and 1
The final answer may be large, print them modulo $10^9+7$**

**Constraints:**
**sub 1: 80% $1 \le l \le r \le 6; q \le10$**
**sub 2: 20% $1\le l \le r \le 250; q = 1$**

Since the maximum digit sum doesnt exceed $250*9$, we can use Dynamic Programming the technique for this problem.
Note that $dp[i]$ is the number of integers with first $i$ digits that their sum digits are prime integers. However, this approach wasn't way too possible since there were no way to calculate this alone, so we need another variable.
This ends up with $dp[i][j]$ = the number of integers with first $i$ digits that their sum digits are $j$
The number of integers whose sum of $i$ digits are primes is $dp[[1,i]][p]$ for all $1 \le p \le 250*9$, $p$ is a prime integer. Let this be $ans[i]$.
The final answer will be $|ans[r] - ans[l-1]|$ modulo $10^9+7$

:::spoiler **Implementation (C++, stdio)**

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for (int i=(a); i<=(int)(b); ++i)
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define all(a,n,i) (a)+(i), (a)+(n)+(i)
#define nl '\n'
typedef long long ll;

const int maxN = 250+5;
const int mod = 1e9+7;

bool isprime[maxN*9];
void eratos(int n) {
    rep(i,maxN*9) isprime[i] = 1;
    isprime[1] = isprime[0] = 0;
    for (int i=2; i*i<=n; i++) {
        if (isprime[i]) {
            for (int j = i*i; j<=n; j+=i) isprime[j] = 0;
        }
    }
}

ll dp[maxN][maxN*9] = {}, ans[maxN] = {};
void preprocess() {
    FOR(i,1,9) dp[1][i] = 1;
    FOR(i,2,250) FOR(j,1,i*9) FOR(d,0,min(j,9)) {
        dp[i][j] = (dp[i][j]%mod + dp[i-1][j-d]%mod) % mod;
    }
    FOR(i,1,250) {
        ans[i] = ans[i-1];
        FOR(j,1,9*maxN)  
        if (isprime[j]) {
            ans[i] = (ans[i]%mod + dp[i][j]%mod)%mod;
        }
    }
}

void solve() {
    eratos(250*9);
    preprocess();
    int q; cin >> q;
    while (q--) {
        int l,r; cin >> l >> r;
        ll ansa = ans[r];
        ll ansb = ans[l-1];
        if (ansa < ansb) {
            cout << ansa - ansb + mod << nl;
        }
        else {
            cout << ansa - ansb << nl;
        }
    }
}

int main() {
    cin.tie(nullptr) -> sync_with_stdio(0);
    solve();
}

:::

##### **Observation:** this problem was actually pretty nice DP Digit one. However how is a DP digit problem possible in HCMOI Grade 9 💀
##### Difficulty (CF Based): should be 1500-1600-ish
##### Tags: DP (DP Digit)

### zeena sucks at ielts writing 😭😭😭😭😭😭😭😭😭😭😭😭😭😭