SPyofgame's blog

By SPyofgame, history, 3 weeks ago, In English


Teleporter: [Previous] | | | [Next]

Table of content

Teleporter Description
I. STATEMENT Taking about the problem
II. EXAMPLE To understand the problem better
III. Solution for small number of element — N How much will you get in each possible subset ?
IV. Solution for small sum of weight — C[i] What is the maximum value possible when your bag is exact $$$W$$$ weight ?
V. Solution for small sum of value — V[i] What is the minimum bag weight possible when it is exact $$$S$$$ sum value ?
VI. Tracing for selected elements Which next state will lead to the best result ?
VII. Online Algorithm How to solve the problem when you need to output the result whenever you receive new item ?
VIII. Optimizations and Heuristic How to improve the algorithm faster, shorter, simpler, safetier or saving space
IX. Debugging Support you when you are in a trouble that you cant find your bug
X. Knapsack Variation and Practice Problems In case you need a place to practice or submitting
XI. Blog status The current progress and contributor of this blogs




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

I. STATEMENT

Taking about the problem

Problem: During midnight, a thief breaks into a jewelry shop. There are $$$N$$$ priceful items whose value and weight are known. The item $$$p$$$ can be sold for $$$V_p$$$ money but having $$$C_p$$$ weight. There is a bag with infinity amount of space, means that any item can be pinto it while the item's value in the bag remain unchanged ! But, it can only hold maximumly $$$W$$$ weight.

Question: What is the value $$$V$$$ that the thief can steal from the shop.





















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

II. EXAMPLE

To understand the problem better



  • Input
3 8
2 10
4 20
6 30

  • Output
40

  • Explanation:
There are 8 possible cases
{} -> 0 value, 0 weight
{1} -> 10 value, 2 weight
{2} -> 20 value, 4 weight
{3} -> 30 value, 6 weight
{1, 2} -> 30 value, 6 weight
{1, 3} -> 40 value, 8 weight - optimal
{2, 3} -> 50 value, 10 weight - invalid weight
{1, 2, 3} -> 60 value, 12 weight - invalid weight




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

III. Solution for small number of element — N

How much will you get in each possible subset ?



A. Permutation Approach (Bad) — $$$O(n!)$$$ time — $$$O(n)$$$ space
  • For each possible permutation, pick elements until it weight too much

  • The result is the maximum value sum, for which weight sum is not greater than $$$W$$$


Code


B. Bitmasking Approach (Good) — $$$O(2^n)$$$ time — $$$O(n)$$$ space
  • Because the order isnt important, we just need to test all every possible subset

  • The result is the maximum value sum, for which weight sum is not greater than $$$W$$$

Code


C. Meet-in-the-middle Approach (Better) — $$$O(2^{n/2})$$$ time — $$$O(2^{n/2})$$$ space
  • Split the array into two halves $$$L$$$ and $$$R$$$. In each half, we will calculate every possible subsets. And in each subset we store a pair of $$$(value\ sum, weight\ sum)$$$

  • For each element $$$X(value_X, weight_X) \in L$$$, we need to find suitable element $$$Y(value_Y, weight_Y) \in R$$$ that satisfying maximum $$$value_R$$$ and $$$weight_L + weight_R \leq W$$$

  • Therefore, we can sort all the $$$R$$$ set by increasing weight. Let $$$maxval_Y = max(value_E | E \in R, weight_E \leq weight_Y)$$$. Then for each $$$X \in L$$$, we can find its suitable $$$Y$$$ by binary search in $$$O(log\ |R|)$$$ with $$$O(|R|)$$$ precalculation

Code




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

IV. Solution for small sum of weight — C[i]

What is the maximum value possible when your bag is exact $$$W$$$ weight ?



A) Recursive Dynamic Programming — $$$O(N \times W)$$$ time — $$$O(N \times W)$$$ space
  • Memorization:

    • f[i][s] = magic(int i, int s) stand for using from the $$$ith$$$ items, with the total weight of $$$s$$$ that maximum value is $$$f[i][s]$$$
    • All $$$f[i][s]$$$ init as $$$-1$$$
  • Base cases

    • If ($$$s > w$$$) then $$$v = -oo$$$ since we use more than what the bag can hold
    • If ($$$i \geq n$$$) then $$$v = 0$$$ since there is no available item, so no weight added into the bag
  • Transistion

    • Using current item, it will be $$$A = magic(i + 1, s + c_i) + v_i)$$$ — move to next item, weight is added with $$$c_i$$$, value is increased by $$$v_i$$$
    • Not using current item, it will be $$$B = magic(i + 1, s + 0) + 0)$$$ — move to next item, weight is remained, value is not increased
    • We want the maximum value so $$$magic(int\ i, int\ s) = max(A, B)$$$
  • The final result: $$$result = magic(1, 0)$$$ — starting from first item with $$$0$$$ weighted bag

Code


B) Iterative Dynamic Programming — $$$O(N \times W)$$$ time — $$$O(N \times W)$$$ space
  • Memorization:

    • f[i][s] stand for using from the $$$ith$$$ items, with the total weight exact $$$s$$$ that maximum value is $$$f[i][s]$$$
    • All $$$f[i][s]$$$ init as $$$0$$$ not $$$-1$$$
  • Base cases:

    • $$$\forall x \geq 0, f[0][x] = 0$$$ — using no item, hence return no value
    • $$$\forall x \geq 0, f[x][0] = 0$$$ — having no weight, hence no using item
    • $$$\forall x > 0, y < 0, f[x][y] = -oo$$$ — define it as negative infinity for easier calculation
  • Transistion:

    • Using current item, $$$A = \underset{0 \leq t + c_i \leq s}{\underset{j \leq i}{max}}(f[j][t]) + v[i] = \underset{0 \leq t = s - c_i}{\underset{j \leq i}{max}}(f[j][t]) + v[i] = \underset{0 \leq t = s - c_i}{\underset{j = i - 1}{f[j][t]}} + v[i]$$$ maximum value among all previous bags added to current item
    • Not using current item, it will be $$$B = \underset{0 \leq t + 0 \leq s}{\underset{j \leq i}{max}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j \leq i}{max}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j = i - 1}{f[j][t]}} + 0$$$ — move to next item, weight is remained, value is not increased
    • We want the maximum value so $$$f[i][s] = max(A, B) = max(f[i - 1][s], f[i - 1][s - c_i] + v_i)$$$
  • The final result: $$$result = \underset{0 \leq s \leq w}{max}(f[n][s])$$$ — starting from first item with $$$0$$$ weighted bag

Bad transistion code - O(N^2 * W^2) time
Normal DP
Prefixmax DP


C) Recursive Dynamic Programming (Space optimization) — $$$O(N \times W)$$$ time — $$$O(N + W)$$$ space

A) O(2W) DP space

  • Observe: $$$\forall i > 0, f[i][x]$$$ depends on $$$f[i - 1]$$$ and $$$f[i]$$$ only, hence we just need 2 dp array space

  • Define: When we calculate at pth element, we have $$$\underset{x \equiv p (mod 2)}{f[x]}$$$ is current dp array, $$$\underset{y \equiv p + 1 (mod 2)}{f[y]}$$$ is previous dp array

  • Transistion: $$$f[i][s] = max(f[i - 1][s], f[i - 1][s - c_i] + v_i)$$$ equivalent to $$$f[x][s] = max(f[y][s], f[y][s - c_i] + v_i)$$$

Code


B) O(W) 1D — DP space

  • From the above algorithm, we can change the inner loop
Inner Part
  • Kinda tricky, but we only need one array, for each query $$$f[s]$$$ stand for maximum value with bag of weight $$$s$$$ upto that query.
Inner Part
  • Notice that it is required for the second-inner-loop to iterate from $$$w$$$ downto $$$c_i$$$. Here is the reason
From c[i] upto w
From w downto c[i]
  • Finally, here is 1D Dynamic Programming Solution
Code




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

V. Solution for small sum of value — V[i]

What is the minimum bag weight possible when it is exact $$$S$$$ sum value ?



A) Recursive Dynamic Programming — $$$O(N \times SUM)$$$ time — $$$O(N \times SUM)$$$ space
  • Memorization:

    • f[i][s] = magic(int i, int s) stand for using from the $$$ith$$$ items, with the total value of $$$s$$$ that minimum weight is exact $$$f[i][s]$$$
    • All $$$f[i][s]$$$ init as $$$-1$$$
  • Base cases

    • If ($$$s < 0$$$) then $$$v = +oo$$$ means we use more value than expected
    • If ($$$i > n$$$ and $$$s \neq 0$$$) then $$$v = +oo$$$ means there is currently no bag of exact $$$s$$$ value
    • If ($$$i > n$$$ and $$$s = 0$$$) then $$$v = 0$$$ means there is actually a bag of exact $$$s$$$ value
  • Transistion

    • Using current item, it will be $$$A = magic(i + 1, s - v_i) + c_i)$$$ — move to next item, sum value is reduce by $$$v_i$$$, weight is added with $$$c_i$$$
    • Not using current item, it will be $$$B = magic(i + 1, s - 0) + 0)$$$ — move to next item, sum value is remained, weight is not increased
    • We want the minimum weight so $$$magic(int\ i, int\ s) = min(A, B)$$$
  • The final result: $$$result = \underset{0 \leq s \leq \Sigma(v_i)}{max}(s | magic(1, s) \leq w)$$$ — maximum value whose weight is not greater than $$$W$$$

Code


B) Iterative Dynamic Programming — $$$O(N \times SUM)$$$ time — $$$O(N \times SUM)$$$ space
  • Memorization:

    • f[i][s] stand for using from the $$$ith$$$ items, with the total value of exact $$$s$$$ that maximum value is $$$f[i][s]$$$
    • All $$$f[i][s]$$$ init as $$$+oo$$$ not $$$-1$$$
  • Base cases:

    • $$$\forall x \geq 0, f[0][x] = 0$$$ — using no item, hence return no weight
    • $$$\forall x \geq 0, f[x][0] = 0$$$ — having no value, hence no using item
    • $$$\forall x > 0, y < 0, f[x][y] = +oo$$$ — define it as negative infinity for easier calculation
  • Transistion:

    • Using current item, $$$A = \underset{0 \leq t + v_i \leq s}{\underset{j \leq i}{min}}(f[j][t]) + c[i] = \underset{0 \leq t = s - v_i}{\underset{j \leq i}{min}}(f[j][t]) + c[i] = \underset{0 \leq t = s - c_i}{\underset{j = i - 1}{f[j][t]}} + v[i]$$$ minimum weight among all previous bags added to current item
    • Not using current item, it will be $$$B = \underset{0 \leq t + 0 \leq s}{\underset{j \leq i}{min}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j \leq i}{min}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j = i - 1}{f[j][t]}} + 0$$$ — move to next item, value is remained, weight is not increased
    • We want the minimum weight so $$$f[i][s] = min(A, B) = min(f[i - 1][s], f[i - 1][s - v_i] + c_i)$$$
  • The final result: $$$result = \underset{0 \leq s \leq \Sigma(v_i)}{max}(s | f[n][s] \leq w)$$$ — maximum value whose weight is not greater than $$$W$$$

Code


C) Iterative Dynamic Programming (Space Optimization) — $$$O(N \times SUM)$$$ time — $$$O(N + SUM)$$$ space

A) O(2SUM) DP space

  • Observe: $$$\forall i > 0, f[i][x]$$$ depends on $$$f[i - 1]$$$ and $$$f[i]$$$ only, hence we just need 2 dp array space

  • Define: When we calculate at pth element, we have $$$\underset{x \equiv p (mod 2)}{f[x]}$$$ is current dp array, $$$\underset{y \equiv p + 1 (mod 2)}{f[y]}$$$ is previous dp array

  • Transistion: $$$f[i][s] = min(f[i - 1][s], f[i - 1][s - v_i] + c_i)$$$ equivalent to $$$f[x][s] = min(f[y][s], f[y][s - v_i] + c_i)$$$

Code


B) O(SUM) 1D — DP space

  • From the above algorithm, we can change the inner loop
Inner Part
  • Kinda tricky, but we only need one array, for each query $$$f[s]$$$ stand for maximum value with bag of weight $$$s$$$ upto that query.
Inner Part
  • Notice that it is required for the second-inner-loop to iterate from $$$sum$$$ downto $$$v_i$$$. Here is the reason
From v[i] upto sum
From sum downto v[i]
  • Finally, here is 1D Dynamic Programming Solution
Code




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

VI. Tracing for selected elements

Which next state will lead to the best result ?



A) Solution for small number of element — N

  • A) Permutation Approach: We will update selected elements when we see a better solution
Permutation - O(n!) time - O(n) space

  • B) Bitmasking Approach: We will update bitmask when we see a better solution
O(2^n)) time - O(n) space

  • C) Meet-in-the-middle Approach: We will update bitmask when we see a better solution AND ON DP-CALCULATION.
Bitmasking - O(2^(n/2)) time - O(2^(n/2)) space


B) Solution for small sum of weight — C[i]

  • A) Recursive Dynamic Programming: Starting from $$$(i = 0, s = 0)$$$, we already have $$$magic(i,s)$$$ return the best result, $$$magic(i + 1,s + 0) + 0)$$$ or/and $$$magic(i + 1, s + c[i]) + v[i]$$$ will be the best result
Trace cases
Recursive DP - O(NW) time - O(NW) space

  • B) Iterative Dynamic Programming:
Prefixmax Iterative DP - O(NW) time - O(NW) space

  • C) Iterative Dynamic Programming (Space Optimization):
Explanation
Code


C) Solution for small sum of value — V[i]

  • A) Recursive Dynamic Programming: Starting from $$$(i = 0, s = res)$$$, we already have $$$magic(i,s)$$$ return the best result, $$$magic(i + 1,s + 0) + 0)$$$ or/and $$$magic(i + 1, s - v[i]) + c[i]$$$ will be the best result
Trace cases
Recursive DP - O(NSUM) time - O(NSUM) space

  • B) Iterative Dynamic Programming:
Iterative DP - O(NSUM) time - O(NSUM) space

  • C) Iterative Dynamic Programming (Space Optimization): On progress...




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

VII. Online Algorithm

How to solve the problem when you need to output the result whenever you receive new item ?



A) Solution for small number of element — N

  • On progress...


B) Solution for small sum of weight — C[i]

  • A) Recursive Dynamic Programming:
What have changed from the orginal ?
O(NW) time - O(NW) space

  • B) Iterative Dynamic Programming:
What have changed from the orginal ?
O(NW) time - O(NW) space

  • C) Iterative Dynamic Programming (Space Optimization):
What have changed from the orginal ?
O(NW) time - O(W) space


C) Solution for small sum of value — V[i]

  • A) Recursive Dynamic Programming:
What have changed from the orginal ?
O(NSUM) time - O(NSUM) space

  • B) Iterative Dynamic Programming:
What have changed from the orginal ?
O(NSUM) time - O(NSUM) space

  • C) Iterative Dynamic Programming (Space Optimization):
What have changed from the orginal ?
O(NSUM) time - O(NSUM) space




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

VIII. Optimizations and Heuristic

How to improve the algorithm faster, shorter, simpler, safetier or saving space



A) Filtering the array

  • 1) Split items into 2 types, whose weight less than $$$W$$$ and the rest
Hint

  • 2) Compressed the array
Hint




















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

IX. Debugging

Support you when you are in a trouble that you cant find your bug



A) Wrong answer

1) Becareful when weight sum and value sum is big, it would cause overflow

Debug

2) Becareful that in Meet-in-the-middle approach:

  • You have to update the bitmask that have maxvalue.

  • You have to update the $$$maxval$$$ and $$$maxmask$$$ before assign $$$x.maxval$$$, $$$x.maxmask$$$

  • You have to use also in collecting the result

Wrong
Wrong
Wrong
Debug
Debug

  • 3) Forget base cases: In type $$$IV$$$ the DP is already init as 0, so you dont need the loop to zero, while the $$$V$$$ is not like that when you init it as $$$+oo$$$
Wrong


B) Time Limit Exceed

1) Global variable $$$\neq$$$ Local variable

  • In Meet-in-the-middle approach, the solve() function didnt use global variable (n), it use $$$n = |c| = |s|$$$.
Debug

2) Forget to use memorization

Wrong
Wrong

3) You might get WA if you have wrong initalization or leave the value generated randomly

Wrong

4) If you wanna binary search for the result, remember that you cant do Prefixmin DP $$$O(N \times SUM)$$$ as what it like in Prefixmax DP $$$O(N \times W)$$$

Wrong


C) Memory limit exceed

1) Though Meet-in-the-middle approach is faster than Bitmasking Approach, it requires large amount of space — $$$O(2^{^{\frac{n}{2}}}$$$, which may give you MLE !


2) In some cases you will need space optimization if the limit is too tight !


3) Becareful in tracing results

Wrong
Fixed


D) Runtime Error

1) Out of bound

Wrong
Wrong

2) Array too big in main function: Declare it globally with the init size bigger than problem constraint a bit





















――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

X. Knapsack Variation and Practice Problems

In case you need a place to practice or submitting



Hint

Note

Hint




























――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

Teleporter: [Previous] | | | [Next]

XI. Blog status

The current progress and contributor of this blogs



  • Current progress;

    - **1)** Online Algorithms
    
     - **2)** Remain space optimization while tracing for elements
  • On progress:

    - **0)** Table of content & Complexity comparision table
    
    - **1)** Online Algorithm
    
    - **2)** Optimizations and Heuristic
    
    - **3a)** Unbounded knapsack
    
    - **3b)** Bounded knapsack
    
    - **3c)** Item limitation knapsack
    
    - **4a)** Knapsack query maximum value with item in range $$$[L, R]$$$
    
    - **4b)** Knapsack query maximum value with weight in range $$$[L, R]$$$
    
    - **4c)** Knapsack query minimum weight with value in range $$$[L, R]$$$
    
    - **5a)** Multiple knapsack bags
    
    - **5b)** Multidimentional item
  • Special thank to contributors: SPyofgame, TheScrasse, Lusterdawn, jiangly

Read more »

 
 
 
 
  • Vote: I like it
  • +89
  • Vote: I do not like it

By SPyofgame, history, 4 weeks ago, In English

The full statement

Main statement

A pair of charactor $$$(L, R)$$$ is called good or matched to each other if it satisfy one of below

  • $$$L =$$$ '(' and $$$R =$$$ ')'
  • $$$L =$$$ '[' and $$$R =$$$ ']'
  • $$$L =$$$ '{' and $$$R =$$$ '}'

Notice that if $$$(L, R)$$$ is good then $$$(R, L)$$$ is not good

String can have many variation of categories, one of that is good string. Let a string $$$S$$$ of size $$$N$$$ is called good if

  • $$$S$$$ is empty (its length $$$N = 0$$$)
  • $$$S = S_1 + S_2 + \dots + S_n$$$. Where $$$S_i$$$ is a good string and + symbol mean that string concaternation
  • $$$S = L + S_x + R$$$ where $$$S_x$$$ is a good string and $$$(L, R)$$$ is a good pair of charactor

Given a string $$$S$$$ of size $$$N$$$. We can add some charactor '(', ')', '[', ']', '{', '}' into anywhere in string $$$S$$$ but you cant replace or remove them.

The question is that: What is the minimum number of charactor need to add into string to make it good ?

Limitation: $$$N = |S| \leq 500$$$



The dynamic programming solution $$$O(n^3)$$$

Lets $$$F(l, r)$$$ is the answer for substring $$$S[l..r]$$$.

  • If $$$l > r$$$ then the string is empty, hence the answer is $$$F(l, r) = 0$$$
  • If $$$l = r$$$ then we should add one charactor to match $$$S_l$$$ to make this substring good, hence the answer is $$$F(l, r) = 1$$$
  • We can split into 2 other substring $$$S[l..r] = S[l..k] + S[k+1..r]$$$, for each $$$k$$$ we have $$$F(l, r) = F(l, k) + F(k+1, r)$$$ hence $$$F(l, r) = min(F(l, k) + F(k+1, r))$$$
  • Notice that when $$$S_l$$$ match $$$S_r$$$, $$$F(l, r) = min(F(l + 1, r - 1), min(F(l, k) + F(k+1, r)))$$$

Complexity:

  • $$$F(l, r)$$$ have $$$O(n^2)$$$ states
  • In each substring $$$S[l..r]$$$, we maybe to have a for-loop $$$O(n)$$$
  • Hence the upper bound of the complexity is $$$O(n^3)$$$
Recursive Code
Iterative Code
Full Code


The other dynamic programming solution $$$O(n^3)$$$

Base cases:

  • If $$$l > r$$$ then the string is empty, hence $$$F(l, r) = 0$$$
  • If $$$l = r$$$ then we should add one charactor to match $$$S_l$$$ to make this substring good, hence $$$F(l, r) = 1$$$

Branch and bound cases:

  • If $$$S_l$$$ is close barrack, then add a open barrack before it, hence $$$F(l, r) = F(l + 1, r) + 1$$$
  • If $$$S_r$$$ is open barrack, then add a close barrack after it, hence $$$F(l, r) = F(l, r - 1) + 1$$$
  • If $$$(S_l, S_{l+1})$$$ is good, then just paired it up, hence $$$F(l, r) = F(l + 2, r) + 0$$$
  • If $$$(S_{r-1}, S_r)$$$ is good, then just paired it up, hence $$$F(l, r) = F(l, r - 2) + 0$$$

Main cases:

For each $$$k = l \rightarrow r - 1$$$

  • If $$$S_k$$$ match $$$S_r$$$, minimize $$$F(l, r)$$$ with $$$F(l, k - 1) + 0 + F(k + 1, r - 1)$$$
  • Else add a open charactor at k to match $$$S_r$$$, minimize $$$F(l, r)$$$ with $$$F(l, k) + 1 + F(k + 1, r - 1)$$$

Complexity:

  • $$$F(l, r)$$$ have $$$O(n^2)$$$ states
  • In each substring $$$S[l..r]$$$, we maybe to have a for-loop $$$O(n)$$$ or $$$O(1)$$$ for transistion
  • Hence the upper bound complexity is $$$O(n^3)$$$
  • Hence the lower bound complexity is $$$O(n^2)$$$
Recursive Code
Full code
Optimize version


My question

  • If the string $$$S$$$ is only consist of '(' and ')' then there is a Linear ($$$O(n)$$$) solution
The solution
  • Can my algorithm ($$$dp[l][r] = min(dp[l][k] + dp[k + 1][r])$$$) improved into $$$O(n^2\ polylog)$$$ or lower in somehow ?

  • Failed to use Knuth algorithm $$$(dp[l][r] = min(dp[l][k] + dp[k][r] + cost[l][r])$$$ since fully-motone condition is not satisfied

Read more »

 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English

The problem

Given $$$n$$$ points $$$(x_1, y_1),\ (x_2, y_2),\dots, (x_n, y_n)$$$

Find the minimum distance between 2 pair of points.

The problem: SPOJ



The constraint

  • $$$2 \leq n \leq 50000$$$

  • $$$x_i, y_i \leq 10^6$$$



My question

I was solving a problem that need to find the minimum distance between two points. I tried to bruteforce then cde an divide and conquer algorithm. But then I modified the bruteforce by adding some branch-and-bound to ignore not-optimal cases. For somehow my code get AC and seems to run fast while I thought it will be slow with the complexity of $$$O(n^2)$$$ with small constant.

I dont really sure about the complexity, can some one help me to calculate it ?

My main part
My full code

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By SPyofgame, history, 3 months ago, In English

The equation

A Linear Diophantine Equation is an equation of the general form:

$$$\underset{i = 1}{\overset{n}{\Sigma}} (a_i \cdot x_i) = N$$$

Where $$$a_i$$$ and $$$N$$$ are given integers and $$$x_i$$$ are unknown integers.



The problem

Given Linear Diophantine Equation of only 2 variables:

$$$ax + by = c$$$

With given integers $$$a, b, c$$$ and unknown integers $$$x, y$$$

Some interesting property
  • The equation only have solution when $$$c$$$ is a mutiple of $$$g$$$ where $$$g$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$

  • When there is a solution $$$(x, y)$$$ satisfy $$$ax + by = c$$$. We also have $$$(x + kv, y - ku)$$$ a solution of the equation (for arbitrary integer $$$k$$$ and quotients $$$u = \frac{a}{g}$$$ , $$$v = \frac{b}{g}$$$)

We have to count the number of $$$(x, y)$$$ non-negative integers solutions for the equation (assume that these value are under $$$10^9$$$ so that we dont deal with overflow cases$

Can I have a simplier implementation then this ? (My algorithm based on cp-algorithm)

Recursive extended greatest common divisor
/// Return gcd(a,b)
/// Find (&x, &y) satisfy ax + by = gcd(a, b)
template<typename T>
T extgcd(T a, T b, T &x, T &y)
{
    if (a == 0) return x = 0, y = 1, b;
    T p = b / a;
    T g = extgcd(b - p * a, a, y, x);
    x -= p * y;
    return g;
}
Recursive extended greatest common divisor
/// Return gcd(a,b)
/// Find (&x, &y) satisfy ax + by = gcd(a, b)
template<typename T>
tuple<T, T, T> extgcd(T a, T b)
{
    if (a == 0) return make_tuple(b, 0, 1);
    T g, x, y; tie(g, x, y) = extgcd(b % a, a);
    return make_tuple(g, y - b / a * x, x);
}
Find one solution ax + by = c
/// Return true if there exist such (x, y) satisfy ax + by = c
/// Find (&g) = gcd(a, b)
/// Find (&x, &y) satisfy ax + by = c
template<typename T>
bool find_any_solution(T a, T b, T c, T &x, T &y, T &g)
{
    if (a == 0 && b == 0) /// 0x + 0y = c
    {
        if (c != 0) return false;
        x = y = g = 0;
        return true;
    }

    if (a == 0) /// 0x + by = c
    {
        if (c % b != 0) return false;
        x = 0, y = c / b, g = abs(b);
        return true;
    }

    if (b == 0) /// ax + 0y = c
    {
        if (c % a != 0) return false;
        x = c / a, y = 0, g = abs(a);
        return true;
    }

    /// ax + by = c
    g = extgcd(abs(a), abs(b), x, y);
    if (c % g != 0) return false;

    x *= (a < 0 ? -1 : +1) * c / g;
    y *= (b < 0 ? -1 : +1) * c / g;
    return true;
}
Shift solution
/// Find the next/prev (cnt)-th solution of ax + by = c
template<typename T>
void shift_solution(T & x, T & y, T a, T b, T cnt)
{
    x += cnt * b;
    y -= cnt * a;
}
Count number solutions of ax + by = c with given range x & range y
template<typename T = long long>
T find_all_solutions(T a, T b, T c, T min_x, T max_x, T min_y, T max_y) {
    if (min_x > max_x) return 0; /// Invalid range
    if (min_y > max_y) return 0; /// Invalid range

    if (a == 0 && b == 0) /// 0x + 0y = c
    {
        if (c != 0) return 0; /// No solution
        return 1LL * (max_x - min_x + 1) * (max_y - min_y + 1); /// Ways to select (x) and (y) in range
    }

    if (a == 0) /// 0x + by = c <=> y = c / b
    {
        if (c % b != 0) return 0; /// No solution
        if (1LL * min_y * b > c) return 0; /// Out of range: min > y
        if (1LL * max_y * b < c) return 0; /// Out of range: max < y
        return max_x - min_x + 1; /// Ways to select (x) in range    
    }

    if (b == 0) /// ax + 0y = c <=> x = c / a
    {
        if (c % a != 0) return 0; /// No solution
        if (1LL * min_x * a > c) return 0; /// Out of range: min > x
        if (1LL * max_x * a < c) return 0; /// Out of range: max < x
        return max_y - min_y + 1; /// Ways to select (y) in range    
    }

    T x, y, g;
    if (!find_any_solution(a, b, c, x, y, g)) return 0;
    a /= g;     
    b /= g;

    T sign_a = a > 0 ? +1 : -1;
    T sign_b = b > 0 ? +1 : -1;

    shift_solution(x, y, a, b, (min_x - x) / b);
    if (x < min_x) shift_solution(x, y, a, b, sign_b);
    if (x > max_x) return 0;
    T lx1 = x;

    shift_solution(x, y, a, b, (max_x - x) / b);
    if (x > max_x) shift_solution(x, y, a, b, -sign_b);
    T rx1 = x;

    shift_solution(x, y, a, b, -(min_y - y) / a);
    if (y < min_y) shift_solution(x, y, a, b, -sign_a);
    if (y > max_y) return 0;
    T lx2 = x;

    shift_solution(x, y, a, b, -(max_y - y) / a);
    if (y > max_y) shift_solution(x, y, a, b, sign_a);
    T rx2 = x;

    if (lx2 > rx2) swap(lx2, rx2);
    T lx = max(lx1, lx2);
    T rx = min(rx1, rx2);

    if (lx > rx) return 0;
    return (rx - lx) / abs(b) + 1;
}
Count all nonegative solutions (x, y) satisfy ax + by = c
typedef long long ll;
long long count_nonegative_solution(int a, int b, int c)
{
    return find_all_solutions(ll(a), ll(b), ll(c), 0LL, ll(c / a + 1), 0LL, ll(c / b + 1));
}

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English

Original Problem


You are given a binary table of size $$$n×m$$$. This table consists of symbols $$$0$$$ and $$$1$$$

You can make such operation: select $$$3$$$ different cells that belong to one $$$2×2$$$ square and change the symbols in these cells (change $$$0$$$ to $$$1$$$ and $$$1$$$ to $$$0$$$)

Your task is to make all symbols in the table equal to $$$0$$$. You dont have to minimize the number of operations. (It can be proved, that it is always possible)


And the constraints are

  • $$$2 \leq N, M \leq 100$$$
  • Easy Version: Limited in $$$3 \cdot N \cdot M$$$ operations
  • Hard Version: Limited in $$$1 \cdot N \cdot M$$$ operations
Code solution without minimizing (with comments)


Extended version

But what if I have to minimize number of operations ?

  • Is there an algorithm other than brute-force to find minimum number of operations in these problem ?

  • I am wondering if I can use Gauss-Elimination (mod 2) or Greedy-DP to solve in somehow

  • I wrote an analizer for small $$$N \cdot M$$$ tables so that you can check too. (Modify by a bit, we can answer query of all $$$N \cdot M$$$ tables, but the complexity is $$$O(2^{n \cdot m})$$$)

Analizer
Test with 3x3 tables
With (n, m) = (2, 2) || show_case = true; show_trace = true;
  • And if the ones are connected, here is the analizer (I will optimize the algo later)
Small checker
Observation
Test with 9x9 tables

Read more »

 
 
 
 
  • Vote: I like it
  • +56
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English

Original Problem

M-candies-problem. In this version, we need to calculate the number of ways to share exact $$$K$$$ candies for all $$$N$$$ children that the $$$ith$$$-child doesnt have more than $$$a_i$$$ candies.

And the constraints are

  • $$$1 \leq N \leq 100$$$
  • $$$0 \leq K \leq 10^5$$$
  • $$$0 \leq a_i \leq K$$$
O(n * k^2) solution - Standard DP
O(n * k) solution - Prefixsum DP
O(n * k) solution - Online algo and space optimization


Extended Version

But what if the constraints were higher, I mean for such $$$M, a_i \leq 10^{18}$$$ limitation ?

O(1) solution for N = 1
O(1) solution for N = 2
O(1) solution for N = 3
O(1) solution for N = 4

Those fully-combinatorics codes above suck and hard to gets a simplified formula. Though I think this problem can be solved for general $$$a_i$$$ and $$$k$$$ in $$$O(n)$$$ or $$$O(n\ polylog\ n)$$$ with combinatorics or/and inclusion-exclusion, but I failed to find such formula.

Can someone give me a hint ?

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English

Does anyone know any simple website or tool or vscode-extension that replace all macros directly into the source code ? I tried to search on google/vscode-extension something like antimacro ..., remove macro ..., replace macro ... but find no result. Thanks for helping ^^

Read more »

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English

Can someone help me. I didnt download anything or any extensions these days but suddenly my both Google and Mozilla Firefox browsers give me codeforces without right navigation tabs :(

I really need the navigations for reading recent news on codeforces and some are helpful <3 Thanks

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English

The problem

Lets $$$f(x) = $$$ product of digits of $$$x$$$. Example: $$$f(123) = 1 * 2 * 3 = 6$$$, $$$f(990) = 9 * 9 * 0 = 0$$$, $$$f(1) = 1$$$

The statement is, given such limitation $$$N$$$, count the number of positive $$$x$$$ that $$$1 \leq x * f(x) \leq N$$$

Example: For $$$N = 20$$$, there are 5 valid numbers $$$1, 2, 3, 4, 11$$$



The limitation

  • Subtask 1: $$$N \leq 10^6$$$
  • Subtask 2: $$$N \leq 10^{10}$$$
  • Subtask 3: $$$N \leq 10^{14}$$$
  • Subtask 4: $$$N \leq 10^{18}$$$


My approach for subtask 1

  • If $$$(x > N)$$$ or $$$(f(x) > N)$$$ then $$$(x * f(x) > N)$$$. So we will only care about $$$x \leq N$$$ that $$$x * f(x) \leq N$$$
Calculating x * f(x) - O(log10(x))
Counting - O(n log10(n))


My approach for subtask 2

  • If $$$x$$$ contains $$$0$$$ then $$$f(x) = 0 \Rightarrow x \times f(x) < 1$$$. We only care about such $$$x$$$ without $$$0$$$ digit
Building function - O(result + log10(n))


Here is the solution:

Let takes some $$$x$$$ satisfy $$$1 \leq x * f(x) \leq N$$$

We can easily prove that $$$f(x) \leq x$$$, and because $$$x * f(x) \leq N$$$, we have $$$f(x) \leq \sqrt{N}$$$ (notice that $$$x$$$ might bigger than $$$\sqrt{N}$$$)

Since $$$f(x)$$$ is product of digits of $$$x$$$, which can be obtain by such digits {$$$1, 2, \dots, 9$$$}. So $$$f(x) = 2^a \times 3^b \times 5^c \times 7^d$$$

So we can bruteforces all possible tuple of such $$$(a, b, c, d)$$$ satisfy ($$$P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{N}$$$). There are small amount of such tuples (493 tuples for $$$N = 10^9$$$ and 5914 tuples for $$$N = 10^{18}$$$)

Find all possible tuples - O(quartic_root(N))

For each tuples, we need to counting the numbers of such $$$x$$$ that $$$1 \leq x \times f(x) \leq N$$$ and $$$f(x) = P$$$.

  • We have the value $$$P$$$, so $$$\lceil \frac{1}{P} \rceil \leq x \leq \lfloor \frac{N}{P} \rfloor$$$.
  • We have the value $$$f(x) = P$$$, so $$$x$$$ can be made by digits having the product exactly $$$P$$$, so we can do some DP-digit

So now we have to solve this DP-digit problem: Calculate numbers of such $$$x$$$ ($$$L \leq x \leq R$$$) whose $$$f(x) = P$$$



Solving Subproblem

We try to build each digits by digits for $$$X$$$. Because $$$X \leq N$$$, so we have to build about $$$18$$$ digits.

Lets make a recursive function $$$magic(X, N, p2, p3, p5, p7)$$$

Lets make some definition
Notice that
Ugly precalculation code - O(1)
magic function - O(18*p2*p3*p5*p7)


About the proving stuff

1) $$$\forall x \in \mathbb{N}, f(x) \leq x$$$

  • Proof: $$$x = \overline{\dots dcba} = \dots + d \times 10^3 + c \times 10^2 + b \times 10^1 + a \times 10^0 \geq \dots \times d \times c \times b \times a = f(x)$$$

2) If $$$x$$$ satisfy then $$$f(x) \leq \sqrt{N}$$$ must be satisfied

  • Proof: $$$x \times f(x) \leq N \Rightarrow f(x) \times f(x) \leq N \Rightarrow f(x) \leq \sqrt{N}$$$

3) $$$\exists\ a, b, c, d \in \mathbb{N} \rightarrow f(x) = 2^a \times 3^b \times 5^c \times 7^d$$$

  • Since $$$x = \overline{\dots dcba} \Rightarrow (0 \leq \dots, d, c, b, a \leq 9)$$$ and $$$f(x) = \dots \times d \times c \times b \times a$$$

  • And we also have $$$\forall$$$ digit $$$v$$$ ($$$v \in \mathbb{N}, 0 \leq v \leq 9$$$) $$$\rightarrow \exists\ a, b, c, d \in \mathbb{N} \rightarrow v = 2^a \times 3^b \times 5^c \times 7^d$$$

  • And because $$$f(x)$$$ is the product of digits of $$$x$$$, hence the statement is correct

4) If we know $$$f(x)$$$ we can find such $$$x$$$ satisfy $$$x \in [L, R]$$$

  • Proof: Since $$$f(x)$$$ is created from factors of digits of $$$x$$$, so $$$x$$$ can also be generated using the factors

5) Number of tuples $$$(a, b, c, d)$$$ satisfy $$$P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{N}$$$ is very small

  • Lets $$$O(k(x)) = O(log_2(x) \times log_3(x) \times log_5(x) \times log_7(x))$$$

  • Since each value $$$x$$$ have the upper bound of $$$log_x(\sqrt{N})$$$. So the complexity is about $$$O(log_2(\sqrt{N}) \times log_3(\sqrt{N}) \times log_5(\sqrt{N}) \times log_7(\sqrt{N})) = O(k(\sqrt{N})) \leq O(log_2(\sqrt{N})^4)$$$

  • But actually for $$$R \leq 10^{18}$$$, the complexity is just about $$$O(k(\sqrt[4]{N}))$$$

Weak proof - N = 10^k
Weak proof - N = 2^k
Code


About the complexity:

  • $$$O(h(x)) = O(log_{10}(N))$$$ is number of digits we have to build
  • $$$O(k(x)) = O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N)) = O(log(N)^4)$$$ is product of all prime digits $$$p$$$ with its maximum power $$$k$$$ satisfy $$$p^k \leq N$$$
  • $$$O(g(x)) = O(k(\sqrt{N}))$$$ is number of such valid tuples, but for $$$1 \leq N \leq 10^{18}$$$ it is about $$$\approx O(k(\sqrt[4]{N})) \leq O(log_2^4{\sqrt[4]{N}})$$$
  • The space complexity is $$$O(SPACE) = O(h(x) \times k(x)) = O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N) \times log_{10}(N)) = O(log(N)^5)$$$
  • The time complexity is $$$O(TIME) = O(SPACE) + O(g(x) \times k(x)) \approx O(log(N)^4 \times log_2^4{\sqrt[4]{N}})$$$


Other

  • About the real complexity for $$$O(k(x))$$$, do you find a better/closer upper bound of counting such tuples of $$$(a, b, c, d \in \mathbb{N})$$$ that $$$P = 2^a \times 3^b \times 5^c \times 7^d \leq N$$$ ? Since my $$$O(log_2(N))$$$ complexity seem very far than the real counting and $$$O(log_2(\sqrt{N}))$$$ is closer but just correct for $$$N \leq 10^{18}$$$

  • Thanks for reading and sorry for updating this blog publicly so many times (most is for the proving path and correcting the complexity)

Read more »

 
 
 
 
  • Vote: I like it
  • +63
  • Vote: I do not like it

By SPyofgame, history, 4 months ago, In English

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 ?

Read more »

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

By SPyofgame, history, 6 months ago, In English

Original Problem

In this problem. The statement give you a deque of $$$n$$$ number. There are two players take turn alternately. In one turn, they can select either leftmost or rightmost element and remove it, and earn $$$x$$$ points where $$$x$$$ is the removed number. They play until the deque is empty. Lets $$$X, Y$$$ are the scores of the first player and the second. Find the maximum $$$X - Y$$$ when they play optimally

We can use dynamic-programming to solve it in $$$O(n^2)$$$ or we can improve upto $$$O(n\ polylog(n))$$$ using data-structure like Treap and fully-optimized by deque in linear $$$O(n)$$$

Recursive DP - O(n^2)
DP iterative - O(n^2)
Deque - O(n)

Variant Problem

Then, I come to a problem, here is the statement.

There is a cycle of $$$n (n \leq 10^4)$$$ binary number $$${a_1, a_2, \dots, a_n}$$$ and ($$$a_i \in {0, 1}$$$) First player take a random number, lets say $$$a_p$$$ then remove it and gain $$$a_p$$$ points The second player take a number which is consecutive with last number removed ($$$a_p$$$) — select either $$$a_{p - 1}$$$ or $$$a_{p + 1}$$$ (notice that $$$a_1$$$ and $$$a_n$$$ is consecutive) They start to play alternately until there are no number left and they plays optimally

The question is in each game where as the first player select the number $$$a_p$$$, $$$p \in [1, n]$$$. How many games did the first player have more score than the second player

Example 1
Example 2
Example 3

I try to use dp to solve it in $$$O(n^2)$$$ but I dont know how to optimize by using deque and only come up to an $$$O(n^2)$$$ solution. Can someone suggest me a better algorithm ?

Dynamic programming - O(n^2)
Deque way - O(n^2)

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By SPyofgame, history, 6 months ago, In English

About the problem

The problem is to calculate the number of such subsequence $$${a_1, a_2, \dots a_n}$$$ that ($$$a_1 + a_2 + \dots + a_k = n$$$) where ($$$k \geq 2$$$) and ($$$a_i \in {1, 2, \dots, n}$$$)

It is the sequence OEIS A111133



My approach for small n

Lets $$$magic(left, last)$$$ is the number of valid subsequences whose sum equal $$$left$$$ which next selected element is such $$$next$$$ in range $$$(last, left]$$$ ($$$next$$$ is strictly greater then last selected number $$$last$$$ and not greater than current sum $$$left$$$). The recursive stop when $$$left = 0$$$ then we found one valid subsequence

Recursive dp - O(n^3) - small n


My approach for bigger n

Lets $$$magic(sum, cur)$$$ is the number of valid subsequences whose selected sum is $$$sum$$$ and current selecting element is $$$cur$$$

  • $$$cur$$$ is init as $$$1$$$ (smallest element) and recursive stop when it greater than $$$n$$$ (largest element)

  • $$$sum$$$ is in range $$$[0, n]$$$ when it equal $$$n$$$ then we found 1 valid subsequence so we return $$$1$$$, else if it greater than $$$n$$$ we stop the recursive

The complexity is still $$$O(n^3)$$$ which $$$O(n^2)$$$ calculation and $$$O(n)$$$ for bignum implementation

Recursive dp - O(n^3) - bignum result
Iterative dp - O(n^3) - bignum result


My question

  • Can I solve the problem in $$$O(n^2)$$$ or in $$$O(n^2 \times polylog(n))$$$

  • Can I find the n_th element faster than $$$O(n^3)$$$

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By SPyofgame, history, 7 months ago, In English

Simplest way:

Approach
Brute-force <TLE> - O(n! * n ^ 2) time - O(n) space

Improving the algorithm

Approach
BIT, Binary-search, Dynamic-programming <TLE> - O((n! * n + n) log n) time - O(n) space

Using formula to improve furthur more

Approach
Recursive Dynamic Programming Approach <AC> - O(n * k) time - O(n * k) space
Iterative Dynamic Programming Approach <AC> - O(n * k) time - O(k) space

I solved this problem but I wonder if there is a better way (faster than $$$O(n \times k)$$$)

So my question is "Is there a faster approach for this problem ?"

Read more »

 
 
 
 
  • Vote: I like it
  • +21
  • Vote: I do not like it

By SPyofgame, history, 8 months ago, In English

There is a simple problem like that on Codeforces

With ($$$1 \leq x, y \leq n$$$) then the result will just simply $$$pair(1; n - 1)$$$

When $$$(b\ \text{mod}\ a = 0)$$$ we have $$$(gcd(a, b) = a\ ;\ lcm(a, b) = b)$$$, therefor $$$gcd(a, b) + lcm(a, b) = a + b = n$$$

So if we choose $$$(a, b) = pair(1; n - 1)$$$ then $$$1 + (n - 1) = n$$$ true

But can I find the result in Linear or faster when both $$$x$$$ and $$$y$$$ have to be in range $$$[l, r]$$$ ? Maybe we give $$$pair(-1; -1)$$$ when there is no result

I found answers in some special cases but not general

Input:

Positive integer $$$n, l, r$$$

Output:

Find such $$$pair(x, y)$$$ in $$$range [l, r]$$$ that $$$(gcd(x, y) + lcm(x, y) = n)$$$


Example 1
Example 2

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By SPyofgame, history, 8 months ago, In English

I read in this paper and know that Binary GCD Implementation is proven to be about 2 times faster than Normal GCD Implementation.

Binary Iterative GCD Implementation (wikipedia)
Normal Iterative GCD Implementation

I just wonder if there is an Efficient Binary Extended GCD Implementation and how fast can it be ?

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By SPyofgame, history, 8 months ago, In English

Thanks to Suffix Array Tutorial from Codeforces I could learn easily how to build Suffix Array and solve some problems

I learn about $$$O(n \log^2(n))$$$ solution and optimize it into $$$O(n \log(n)$$$, it is fast and good. In some contests, I saw some div-1 rankers discuss about $$$O(n)$$$ solution. Now I am wondering if there is an simple implementation but efficient Suffix Array in Linear Time and Space ?

From their conversation about Linear Solution, I read from this paper and this too but I am not be able to implement it. I know those implementations are hard and higher above my levels but I just curiously to know about the implementation

Thanks for reading, sorry if this blog waste your time.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By SPyofgame, history, 8 months ago, In English
In problem $$$\overbrace{(((a ^ n) ^ {{}^n}) ^ {{}^{{}^{...}}})}^{b\ times\ n} \mod m$$$
  • My approach is calculating each part $$$((a ^ n) \mod m)$$$ then $$$(((a ^ n) ^ n) \mod m) = ((t ^ n) \mod m)$$$ ... all together in $$$O(\log n)$$$ each part and $$$O(b \times \log n)$$$ total time complexity

  • Can I improve it somehow faster where $$$b$$$ is large ($$$b \leq 10^{16}$$$) and ($$$m$$$ can be composite number)

In problem $$$\overbrace{a ^ {(n ^ {(n ^ {(...)})})}}^{b\ times\ n} \mod m$$$
  • I only know the way to use bignum to calculate $$$n ^ n$$$ then $$$n ^ {n ^ n}$$$ all together then I just have to calculate the modulo of $$$a ^ {...} \mod m$$$ but the total complexity will be very huge (since the number of digits of bignum will raise very fast)

  • Can I apply these formula from phi-function:

$$$a ^ {\phi(m)} \equiv 1 \pmod m$$$
$$$a ^ n \equiv a ^ {n \mod \phi(m)} \pmod m$$$
$$$a ^ n \equiv a ^ {\phi(m) + (n \mod \phi(m))} \pmod m$$$
  • Can I improve it somehow faster where $$$n$$$ is large ($$$n \leq 10^{16}$$$) and ($$$m$$$ can be composite number)

Read more »

 
 
 
 
  • Vote: I like it
  • +76
  • Vote: I do not like it

By SPyofgame, history, 8 months ago, In English

There is an empty rectangle of size

$$$n \times m$$$

where

$$$1 \leq n, m \leq 10^6$$$

We cover the rectangles k times from (u1, v1) to (u2, v2), where

$$$1 \leq k \leq 400$$$
$$$1 \leq u1 \leq u2 \leq n$$$
$$$1 \leq v1 \leq v2 \leq m$$$

The question is: How many squares of that rectangle have been covered ?

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By SPyofgame, history, 9 months ago, In English

Here are some implementations for getting primes.

  • Some are well-known & effectively algorithms you might need
  • There are several blogs for these implementations, I only collect and edit it to same style code
  • You can show your way below and I will add to the post ^^

    Sorry, I am not sure if there are some corner cases or I calculated wrong complexity. If there are, please correct m


Here are the algorithms. Enjoy ^^

Division approach: Check if there are only 2 divisors
Masking approach: Mask every multiple of primes
Another approach


My Planning on this post

  • Add compilations
  • Add relative blogs
  • Add some more implementations
  • Add tutorial & reasoning for each implementation

Read more »

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

By SPyofgame, history, 9 months ago, In English

I found these implementations ^^

Sorry, I am not sure if there are some corner cases or I calculated wrong complexity. If there are, please correct me.

I am wondering if there are some other implementations ^^ (you can comment below and I will add to the post)

Implementation 0: Trivial
Implementation 1: Optimized Trivial
Implementation 2: Naive Factorization
Implementation 3: Factorization
Implementation 4: Miller-rabin
Implementation 5: Sieve + Factorization
Implementation 6: Sieve + Miller-rabin + Pollard-rho
Implementation 7: Divisor Sum Sieve


Compilation:

Implementation Main Algorithm Time Complexity Space Complexity Coding Space Coding Complex
0. Trivial Implementation O(n) O(1) Short Simple
1. Trivial Implementation O(√n) O(1) Short Simple
2. Factorization + Math Math O(n ^ 2) ? O(1) Normal Normal
3. Factorization + Math Factorization O(n√n) O(1) Normal Normal
4. Factorization + Math Miller-rabin O(n * log^5(n)) O(1) Long Normal
5. Factorization + Math Sieve O(n) + O(log n) O(n) Normal Normal
6. Factorization + Math Pollard-rho O(√n) + O(√(√(n)) polylog n) query O(√n) + O(log n / log(log n)) query Very Long Complex


Planning:

  • Add relative blogs

  • Add some more implementations

  • Add tutorial & reasoning for each implementation

Read more »

 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it

By SPyofgame, history, 9 months ago, In English

I am wondering if I could always replace all long long type into int64_t type without breaking the program ? Will it somehow affects the program or remains the same ?

And how about the relationship between int and int32_t types

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By SPyofgame, history, 10 months ago, In English

Recently while I am solving a problem, I realised that increase iterator after erasing the last element of the map (the map is empty) then it would run infinitively

So I stop the loop by adding a small line to check whether it is empty or not

/// map-looping using either iterator or reverse iterator
{
    /// some code upper that erase the element but possible to make the map empty
    if (map.empty()) break;
}

Is there an alternative way (some other implementations) to prevent from iterator increament when the map is empty (and reverse_iterator too if possible)

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By SPyofgame, history, 11 months ago, In English

Given an array of N elements where |Ai| ≤ 1e9

How can I find the longest subsequences whose sum is positive efficiently

Read more »

 
 
 
 
  • Vote: I like it
  • -14
  • Vote: I do not like it

By SPyofgame, history, 11 months ago, In English
Original templates

If I want to make those templates simpler by using --bit instead of (bit — 1). Will this cause undefined behaviour ?

Changed templates

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By SPyofgame, history, 11 months ago, In English

Issue: I feel laggy to comment and the contest which I took part in isnt been highlighted anymore.

Hope: Codeforces after the maintaining would work faster and more stable (and even during the contest if possible) <3.

Read more »

 
 
 
 
  • Vote: I like it
  • -29
  • Vote: I do not like it