### ljsh_king's blog

By ljsh_king, 2 months ago,

I'm solving ABC 259 pG.

Here's the article that I found.

I can understand "The project selection problem" part, but doesn't know how to modify it. To be clear, if $task_i$ is dependent on $task_j$, we simply add an edge from $i$ to $j$ with $\infty$ weight. What if we want a penalty when both $i$ and $j$ are chosen? How do we reconstruct the edges? (Actually from the code of leaderboard it seems like we add an edge from $i$ to $j$ with $penalty$ weight, but why? Adding an edge with $\infty$ weight means we can't cut the edge there, but what if the weight isn't $\infty$? What does it mean when the cut is in the middle?)

Also, are there more resources that I can read for constructing flows? I've googled it and most of them were talking about flow algorithms instead of flow constructions.

• +3

By ljsh_king, history, 3 months ago,

Link to the problem I use bottom up DP, where $dp[\text{mask of visited vertices}][\text{ending vertex}]$. I'm pretty sure my time complexity is $O(N \cdot 2^N + 2^N \cdot N^2)$ however it gives TLE. Are there any way to optimize my code, and what's the reason for TLE (probably big constant factor?)

My code

• +3

By ljsh_king, 4 months ago,

I was solving this problem.

My idea is to map bits into linear equations.

Try all possible number of bits set to 1 in the final array (0~30 in this problem).

Take sample input 1 as an example.

Let's say we want $(S = 2)$ bits set to 1, here's the linear equations:

$(1 - A) + (1 - B) + (1 - C) = 2$

$A + (1 - B) + C = 2$

Do some simplifications,

$(-1) * A + (-1) * B + (-1) * C = -1$

$1 * A + (-1) * B + 1 * C = 1$

One possible solution for $(A, B, C)$ is $(0, 0, 1)$ = $1(001)_2$.

However gaussian elimination doesn't ensure the solution having integer solution (and also =0 or =1 in this problem).

When there're infinite solutions, is there a way to check if there exist a solution $(x_0, x_1, \dots, x_{30}), x_i = 0$ or $x_i = 1$?

My submission

• +8

By ljsh_king, history, 4 months ago,

I was solving this problem. The formula for this problem can be founded here. I've stress tested my code, and found out that this is the smallest test case where my code failed (answer for n <= 225537 are all correct).

Input
Output
Expect

It is obvious that my output is wrong, since $answer(n) > answer(n-1)$. I have no idea why my code doesn't work.

Code

• +3

By ljsh_king, history, 4 months ago,

I was reading this article, and saw example 1 (number of coprime pairs in range [1, n]). I tried to solve this problem with similar formula. Here's what I wrote:

$\sum_{i=1}^n \sum_{j=1}^n [gcd(a_i, a_j) = 1]$

$= \sum_{i=1}^n \sum_{j=1}^n \sum_{d|gcd(a_i, a_j)} \mu{(d)}$

$= \sum_{i=1}^n \sum_{j=1}^n \sum_{d=1}^{\infty} [d|a_i][d|a_j]\mu{(d)}$

$= \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i]) (\sum_{j=1}^n [d|a_j])$

$= \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i])^2$

We can calculate $\mu{(d)}$ using linear sieve in $O(max(a_i))$

and $\sum_{i=1}^n [d|a_i]$ for each $d$ in $O(n * \sqrt{max(a_i)})$

But it turns out that when the input is

2
1 2


mu = {1, -1}

cnt = {2, 1}

Gives output of $1 * 2^2 + -1 * 1^2 = 3$ which is absolutely wrong.

Can anyone point out my mistake? Thanks.

• +8

By ljsh_king, history, 8 months ago,

I was solving this Problem Link and encountered a bug. I'm getting WA on test 10, but I run stress test locally on my PC and didn't found any counter test cases. Please take a look on my code.

Approach that I used to solve this problem

Here are my code.

Test Case Generator
Brute force solution
My submission

EDIT: SOLVED. Stupid mistake in binary lifting function.