Wondering for a better approach to this problem

Revision en17, by SPyofgame, 2020-11-28 11:53:17

I come to a fun problem, and after I tried hard to solve it, I curiously to find better algorithm, but I cant.



The problem is:

There are $$$N$$$ buildings with $$$a_1, a_2, \dots, a_n$$$ metters height. These days are hard, the heavy raining weather still not ended yet. In day $$$d$$$, every building with height $$$h$$$ only have $$$x_d = \lfloor \frac{h}{d} \rfloor$$$ height left of good space to use, while others are sunk underwater. Every building having the same value $$$x_d$$$ on day $$$d$$$ will group together (including $$$x_d = 0$$$ which sunk completely underwater) in a way that no other building with same value $$$x_d$$$ in another group.



The question is:

Output $$$N$$$ lines, in each size $$$s$$$ from $$$1$$$ to $$$n$$$, what is the earliest day $$$d$$$ that have at least one group of size $$$s$$$ (if there is no suitable day then output -1)



The constraints are:

  • Subtaks 1: $$$n \leq 100~ and ~a_i \leq 2.10^5$$$
  • Subtaks 2: $$$n \leq 300~ and ~a_i \leq 3.10^6$$$
  • Subtaks 3: $$$n \leq 300~ and ~a_i \leq 5.10^7$$$


The examples are:

Example 1

Input:

3
1 2 5

Output:

1
3
6

Explanation:

Day 1: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$$$ } $$$=$$$ { $$$1, 2, 5$$$ } — First group of size 1: Any of {$$$1$$$} {$$$2$$$} {$$$5$$$}

Day 2: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$$$ } $$$=$$$ { $$$0, 1, 2$$$ }

Day 3: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ } — First group of size 2: Only {$$$1, 2$$$}

Day 4: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{4} \rfloor, \lfloor \frac{2}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }

Day 5: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{5} \rfloor, \lfloor \frac{2}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }

Day 6: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{6} \rfloor, \lfloor \frac{2}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ } — First group of size 3: Only {$$$1, 2, 5$$$}

Example 2

Input:

3
1 1 5

Output:

1
1
6

Explanation:

Day 1: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{1} \rfloor, \lfloor \frac{1}{1} \rfloor, \lfloor \frac{5}{1} \rfloor$$$ } $$$=$$$ { $$$1, 1, 5$$$ } — First group of size 1: Any of {$$$1$$$} {$$$1$$$} {$$$5$$$}

Day 2: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{2} \rfloor, \lfloor \frac{1}{2} \rfloor, \lfloor \frac{5}{2} \rfloor$$$ } $$$=$$$ { $$$0, 0, 2$$$ } — First group of size 2: Only {$$$1, 1$$$}

Day 3: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{3} \rfloor, \lfloor \frac{1}{3} \rfloor, \lfloor \frac{5}{3} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }

Day 4: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{4} \rfloor, \lfloor \frac{1}{4} \rfloor, \lfloor \frac{5}{4} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }

Day 5: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{5} \rfloor, \lfloor \frac{1}{5} \rfloor, \lfloor \frac{5}{5} \rfloor$$$ } $$$=$$$ { $$$0, 0, 1$$$ }

Day 6: $$$x[d] = $$$ { $$$ \lfloor \frac{1}{6} \rfloor, \lfloor \frac{1}{6} \rfloor, \lfloor \frac{5}{6} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ } — First group of size 3: Only {$$$1, 2, 5$$$}

Example 3

Input:

3
2 2 2

Output:

-1
-1
2

Explanation:

Day 1: $$$x[d] = $$$ { $$$ \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor$$$ } $$$=$$$ { $$$2, 2, 2$$$ } — First group of size 3: Only {$$$2, 2, 2$$$}

Day 2: $$$x[d] = $$$ { $$$ \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ }

Day 3: $$$x[d] = $$$ { $$$ \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ }

Day 3 $$$\leq k \rightarrow \infty$$$: $$$x[d] = $$$ { $$$ \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor$$$ } $$$=$$$ { $$$0, 0, 0$$$ } — There are no group of size 1 and 2



My approach to this problem:

Observation: Harmonic Sequence

We consider this Harmonic Sequence: $$$S = $$$ {$$$\lfloor \frac{n}{x} \rfloor\ |\ x = 1\dots n$$$} = {$$$ \lfloor \frac{n}{1} \rfloor, \lfloor \frac{n}{2} \rfloor, \lfloor \frac{n}{3} \rfloor, \dots , \lfloor \frac{n}{n - 1} \rfloor , \lfloor \frac{n}{n} \rfloor$$$}

And lets $$$L$$$ is Unique Harmonic Sequence. $$$L = $$$ {$$$x\ |\ x \in S$$$} or/and ($$$\forall (i \neq j) \in L \rightarrow L_i \neq L_j$$$) (I will use the set $$$L$$$ beneath)

Then the number of unique element in array is atmost $$$2 \sqrt{N}$$$. Hence $$$|L| \leq 2 \sqrt{N}$$$

Subtask 1: A[i] <= 2 * 10^5

Since day $$$k > max(a[i])$$$ will make all array always being as $$$x[k] =$$$ {$$$0, 0, \dots, 0$$$}, we only need to check for each value $$$k \in [1, d]$$$. Then we can calculate how many group of size $$$s$$$ in day $$$k$$$. My approach is to increase the value $$$f[\lfloor \frac{a_i}{k} \rfloor] = s$$$ means in day $$$\lfloor \frac{a_i}{k} \rfloor$$$ have group of size $$$s$$$, then minimize the first day we have the group of size $$$s$$$

This approach is $$$O(n \times max(a_i))$$$

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;
    int k = *max_element(all(a)) + 1;

    vector<int> f(k + 1, 0);
    vector<int> q(n + 1, +INF);
    for (int x = 1; x <= k; ++x) /// Checking possible dividing value
    {
        for (int t : a) ++f[t / x];               /// Calculating value f[] for each day [t / x]
        for (int t : a) minimize(q[f[t / x]], x); /// Minimize first day have group of size k
        for (int t : a) --f[t / x];               /// Reset the array
    }

    for (int i = 1; i <= n; ++i)
        cout << (q[i] == +INF ? -1 : q[i]) << '\n';
    
    return 0;
}
Subtask 2: A[i] <= 3 * 10^6

Lets $$$setL$$$ be a set of good potential $$$k$$$ for dividing. Since there are some $$$k$$$ that having group of size $$$s$$$ but never will be good enough to be the smallest day. That is for each $$$a_i$$$, we find all $$$k$$$ that have smallest day $$$d$$$ that might appear a group of size $$$\lfloor \frac{a_i}{k} \rfloor$$$ and insert into $$$setL$$$.

The upper bound complexity is $$$O(n\ \times k\ log(k))$$$ where $$$k = |setL| = O(n \times \sqrt{max(a_i)})$$$ but since $$$a_i$$$ is small, and the bigger $$$n$$$ is, the more number of duplicate values will all be eliminated by using $$$set<>$$$. It would reduce both complexity and constant factor significantly.

int main()
{
    int n;
    cin >> n;

    set<int> setL;
    vector<int> a(n);
    for (int &x : a)
    {
        cin >> x;

        int sqrtx = sqrt(x);
        for (int t = 1; t <= sqrt(x); ++t)
        {
            setL.insert(x / t + 1);
            setL.insert(t + 1);
        }
        setL.insert(x + 1);
        setL.insert(1);
    }

    vector<int> res(n + 1, +INF);
    for (int x : setL)
    {
        map<int, int> F;
        for (int t : a) ++F[t / x];                 /// Calculating value f[] for each day [t / x]
        for (int t : a) minimize(res[F[t / x]], x); /// Minimize first day have group of size k
    }

    for (int g = 1; g <= n; ++g) cout << (res[g] == +INF ? -1 : res[g]) << '\n';
    return 0;
}
Subtask 3: A[i] <= 5 * 10^7

With $$$T = \sqrt{max(a_i)}$$$ then all such $$$k \leq T$$$ are potential. We only care for such $$$k > T$$$ which we can use branch and bound to reduce constant matter.

By using map, we can calculate faster by ignoring duplicates. Iterating through map reducing the $$$O(log)$$$ factor each query.

Since we solve each potential $$$k$$$ from large to smaller, the value $$$cur$$$ will be from small to larger, so we dont have to use $$$min(a, b)$$$ function, and only update for each $$$res[x]$$$ once. We exit when all $$$N$$$ query are found or we tried all potential $$$k$$$

Hence, the complexity is $$$O(n\ log\ n + n \times (k + \sqrt{max(a_i)}) + k\ log\ k)$$$ where $$$k = |setL|$$$

int n;
int cnt = 0;
vector<int> a;
map<int, int> b;
map<int, int>::iterator it;
vector<int> res;

void out()
{
    for (int i = 1; i <= n; ++i) cout << (res[i] == +INF ? -1 : res[i]) << '\n';
    exit(0);
}
void solve(int x)
{
    int sum = 0, val = -1;
    for (it = b.begin(); it != b.end(); ++it)
    {
        int cur = it->first / x;
        if (cur != val)
        {
            val = cur;
            if (sum && res[sum] == +INF) { res[sum] = x; if (++cnt == n) out(); }
            sum = 0;
        }
        sum += it->second;
    }
    if (sum && res[sum] == +INF) { res[sum] = x; if (++cnt == n) out(); }
}

int main()
{
    cin >> n;
    a.resize(n);
    for (int &x : a)
    {
        cin >> x;
        ++b[x];
    }

    
    res.assign(n + 1, +INF);
    int k = ceil(sqrt(*max_element(all(a))));
    for (int x = 1; x <= k; ++x) solve(x);

    if (k > 1)
    {
        set<int> setL;
        for (it = b.begin(); it != b.end(); ++it)
        {
            int x = it->first;
            int lim = min(k, x / (k - 1));
            for (int t = 1; t <= lim; ++t)
            {
                int v = x / t + 1;
                setL.insert(v);
            }
        }
        for (int x : setL) solve(x);
    }
    out();
    return 0;
}


My question

  • Is there a better algorithm for larger $$$N$$$ ? (upto $$$10^4, 10^6$$$)

  • Is there a better algorithm for larger $$$a_i$$$ ? (upto $$$10^{12}, 10^{16}, 10^{18}$$$)

  • Can I use combinatorics or euclidian algorithm for this problem ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English SPyofgame 2020-11-28 11:53:17 1 Tiny change: '----------\n\n------' -> '---------- \n\n------'
en16 English SPyofgame 2020-11-28 11:52:43 587
en15 English SPyofgame 2020-11-23 08:27:18 1 Tiny change: 'nificantly\n\n```cpp' -> 'nificantly.\n\n```cpp'
en14 English SPyofgame 2020-11-12 20:11:18 4
en13 English SPyofgame 2020-11-10 17:15:42 71
en12 English SPyofgame 2020-11-10 10:12:24 28 Tiny change: ' cant.\n\n### **' -> ' cant.\n\n----------\n\n----------\n\n### **'
en11 English SPyofgame 2020-11-09 18:34:14 43
en10 English SPyofgame 2020-11-09 18:33:31 106
en9 English SPyofgame 2020-11-09 18:23:14 222
en8 English SPyofgame 2020-11-08 20:55:42 2 Tiny change: '$a_i \leq 3 * 10^7$\n' -> '$a_i \leq 5 * 10^7$\n'
en7 English SPyofgame 2020-11-08 20:43:41 6 Tiny change: '$a_i \leq 10^9$\n\n\n---' -> '$a_i \leq 3 * 10^7$\n\n\n---'
en6 English SPyofgame 2020-11-08 20:13:13 249
en5 English SPyofgame 2020-11-08 20:10:58 923 Tiny change: 'ty is $O(n log n \times ' -> 'ty is $O(n\ log\ n + n \times ' (published)
en4 English SPyofgame 2020-11-08 19:44:15 4420
en3 English SPyofgame 2020-11-08 18:42:32 3161 Tiny change: ': $x[d] = {\lfloor \' -> ': $x[d] = \{\lfloor \'
en2 English SPyofgame 2020-11-02 19:58:26 186
en1 English SPyofgame 2020-10-28 15:51:50 865 Initial revision (saved to drafts)