I struggle to understand the statement of this problem. Could you help me re-declare this statement, thanks a lot.

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3567 |

3 | tourist | 3520 |

4 | maroonrk | 3421 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3309 |

8 | Benq | 3283 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 193 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | Radewoosh | 168 |

6 | tourist | 166 |

7 | Um_nik | 165 |

8 | ko_osaga | 163 |

9 | McDic | 162 |

10 | Ashishgup | 161 |

I'm solving this Vietnamese problem which ask to calculate sum of first $$$n$$$ Tribonacci Number.

Tribonacci Number:

Let $$$S_n$$$ is the sum of first $$$n$$$ Tribonacci.

.

How to calculate $$$S_n$$$ with time complexity less than linear.

I have searched for it and found out we can use matrix multiplication to solve it with $$$O(log\ n)$$$. But with Fibonacci, we can based on relation between $$$F_n$$$ and $$$S_n$$$, $$$S_n = F_{n+2} - 1$$$. This article.

Could you help me figure out the relation between $$$T_n$$$ and $$$S_n$$$ in Tribonacci Number.

Thanks for your reading.

I see many people write your own pow function with module like this:

```
int pow(int a, int b, int m){
int ans = 1;
while(b){
if (b&1) ans = (ans*a) % m;
b /= 2;
a = (a*a) % m;
}
return ans;
}
```

and my pow function:

```
int pow(int a, int b, int m){
int ans = 1;
while(b){
ans *= a;
b--;
}
return ans;
}
```

The complexity of solution 1 is $$$O(log(b))$$$ ans solution 2 (my solution) is $$$O(b)$$$. I would like to know if it's the main reason to do that because I feel the 2nd solution easier to grasp and in the small situation (ex: b < 100), the second one is also good enough? Does it have any other reason?

I have solved UVa-10499 Traffic.

The problem ask to find out all shortest path from vertex 1, if vertices are affected by negative cycle, it means the shortest path become undefined and we print `?`

. I solved it with Bellman-Ford algorithm and it passed but I feel my approach is incorrect and I found a counter-example.

My approach: In the nth-relaxation, if vertices are shorten, I assign shortest path to them equal $$$-\infty$$$.

```
for(auto e:edges){
int u, v, w; tie(u, v, w) = e;
if (d[u]+w < d[v]) {
d[v] = -INF;
}
}
```

My fully solution: https://ideone.com/TfuoGz

For example, I have this graph and edges are stored in this order, the weight of edges represent the edges.

and in the n-th relaxation, I am just able to assign $$$-\infty$$$ to vertex 3, but vertex 2 and 4 are also affected by negative cycle.

Does the system test is weak or I understand something wrong? Could you suggest me the approach to solve this kind of problems.

Thank you!

My code

Idea:

$$$dp[i][j]$$$: The longest consecutive sequence when we start at character $$$(i,j)$$$.

I use DFS to compute dp table.

After that, I iterate all characters $$$c[i][j]$$$ in the matrix, if `c[i][j]=='A'`

, I take the answer `ans = max(ans, dp[i][j])`

.

Thank you!!!

The problem VK2012 B — File List.

I solved it by using greedy, but this problem was tagged dp and the editorial instructed dp approach such that:

is [i] — can we cut the prefix of length i .

Initially, is [0] = 1, the remaining zeros.

Now iterate over i in ascending order and if is [i] = 1, try to make the transition to i + 1 .. i + 12

I still can't solve it by DP, could you give me a more detailed explanation to solve this problem using DP? Thanks in advance!

I see a lot of people handling nCk with module(1e9+7) like that?

```
vector<ll> inv(h+w+1);
vector<ll> fact(h+w+1);
vector<ll> fact_inv(h+w+1);
inv[1] = 1;
for(int i=2; i<h+w+1; i++){
inv[i] = MOD - (MOD/i) * inv[MOD%i] % MOD;
}
fact[0] = 1;
fact_inv[0] = 1;
for(int i=1; i<h+w+1; i++){
fact[i] = fact[i-1]*i % MOD;
fact_inv[i] = fact_inv[i-1]*inv[i] % MOD;
}
auto comb = [&](int n, int k){
if (n<0 || k<0) return 0LL;
if (n < k) return 0LL;
return fact[n]*fact_inv[n-k] % MOD * fact_inv[k] % MOD;
};
```

What I can infer is that `inv[i]`

is `1/i`

. Now, i don't understand the way they calculate `inv[i]`

? Let me a more detailed explanation about that. Thanks in advance!

Hi Codeforces Community, I have just solved this problem.

Link problems

Even though I solved it by myself, i still feel i'm missing anything, i feel uncomfortable.

The problem requires we find out k ranges (size = m) in the way that sum of all elements in every ranges is maximal. I came up with the ideal that:

$$$f(i,j)$$$ is the maximum sum of all elements in j range (size = m) when we have already gone to a[i]. So

The answer will be $$$f(n,k)$$$.

I still feel like i don't understand it absolutely. As usual, i try to form my DP problem to a graph and find the shortest (or longest) path depended on statement.

I want to ask the way you approach for a DP problem.

Thanks in advance, i am studying dynamic programming.

I read many people's solutions and I realized the technique that helps me count effectively. This technique is:

If i want to increase all elements in range $$$[l;r]$$$ in array $$$cnt[]$$$, i will set $$$cnt[l]++$$$ and $$$cnt[r+1]--$$$, after that i will calculate cumulative sum from left to right, $$$cnt[i]+= cnt[i-1], \forall i \in [1:n]$$$.

The same approach is applied for 2d counting arrray. If i want to increase every cell in rectangle with top-left $$$(x_1, y_1)$$$ and bottom-right $$$(x_2, y_2)$$$. I will set` cnt[x1][y1]++; cnt[x1][y2+1]--; cnt[x2+1][y1]--; cnt[x2+1][y2+1]++; `

and then calculate the partial sum of this 2d counting array.

I want to get more information for this technique. Could you help me the name of it or any link that is relevant. Thanks in advance.

This is the link of problem: D. White Line.

For the best i understand up to now, let's focus on row.

I will base on the range [l;r] each row of black to determine whether which cells that we click will erase this row or not. These cells are in the rectangle from $$$(l1, l2)$$$ (top left) to $$$(r1-1, r2-1)$$$ (bottom right), $$$l1, l2, r1, r2$$$ is defined in the code i extracted from @kcm1770's solution.

```
for(int i=0; i<n; ++i) {
int l=0;
while(l<n&&s[i][l]=='W')
++l;
if(l>=n) {
++b[0][0];
continue;
}
int r=n-1;
while(~r&&s[i][r]=='W')
--r;
if(r-l+1>k)
continue;
//i-k+1, i
//r-k+1, l
int l1=max(i-k+1, 0), r1=i+1;
int l2=max(r-k+1, 0), r2=l+1;
++b[l1][l2];
--b[l1][r2];
--b[r1][l2];
++b[r1][r2];
}
```

I see a lot of people do the same approach. I don't know how they come up with the way set ++ & -- like that. This is all of magic for me. Could you tell me about some similar problems using that or some concepts involve.

`*2500`

tag, i lose all of my confident =)). Lmao!!! Could you give me some advice. Thanks in advance.

The problem link: https://csacademy.com/contest/archive/task/binary-flips/statement/

The Editorial link: https://csacademy.com/contest/archive/task/binary-flips/solution/

For me, i read editorial and think:

D(N,K,P) is the number of ways flips K times to construct a matrix with P columns all 1.

and when we discover $$$i\ col (all 1) * N + j\ row (all 1) * M - 2ij$$$ equals to S, we add D(N,K,i)* D(M,K,j) but i am pretty confused that: What guarantee K operations that construct i col 1 also construct j row 1. What wrong with my understand?

I have read Editorial and Code Example but I still don't understand the solution. Could you help me to explain more details. Thanks in advanced.

Link problem: https://csacademy.com/contest/archive/task/array-elimination/

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2020 07:03:53 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|