Don't worry, red coders are able to set up contests with easy problems.

flashback of my rounds

Okay, some red coders.

The difficulty levels of the problems range from Div2 A to Div2 E. However, it may be challenging even for Div1 coders to solve all the problems in five hours.

If this can be done then it will be really helpful.

As mentioned in the sugim's tweet on twitter it is due to the codeforces round clashing with the atcoders' round.

"1/5 (土) 20:00 — 25:00 に開催予定の DP まとめコンテスト (https://atcoder.jp/contests/dp ) ですが、1/5 (土) 25:30 — に Codeforces のコンテストが生えたので、1/6 (日) 20:00 — 25:00 への移動を検討しています。ぜひアンケートにご協力ください。"

Read the blog.

No the questions won't be sorted by difficulty

Difficulty according to solve count during contest: A B C D H F E I G K L M N P S O Q R J U Z Y X T V W

dp[i][j] — The number of ways to make a permutation of length i + 1 that respects the first i signs and the last element is j (j ≤ i + 1).

If s[i] is  >  then

Otherwise

To do this in O(n²) use prefix sums

dp[i][j] denotes the number of permutations of 0, 1, ..., i - 1 such that the last element is j and all the first i - 1 inequalities are fulfilled. You can easily update this dp in O(1) with prefix sums, giving O(n²) complexity.

I solved it with inclusion-exclusion principle, dividing the sequence into monotonously increasing parts. After writing down each terms, calculate dp[i] := sum of terms ending at i. That can be done in O(n^2) time. (I couldn't come up with simpler dp...)

In the given problem the values were  ≤ 1e3, so .

You need to make a dp[N][V] — what is the minimum weight you need to use to get the value V in the first N items. Then just iterate over the dp table to find the maximum value that requires less than W space.

Btw, there is also dp[val] solution (val<=1e5, maximum possible value) where for each i<=n check if there is j>val[i] such that adding wgh[i] to dp[j-val[i]] will minimize dp[j]. (1<=j<=val). But in order to not overlap with updates (if you go from 1 to val), either iterate from val to 1, or store all changes in vector and update it after iteration.

I even don't understand it, do you?

If you have k empty piles out of n, the expected value of the number of steps to go to different state increases by . The rest is just dp[cnt₁][cnt₂][cnt₃] with 3 transitions.

Please share what's special in that test case,in case you come to know about it.I am also stuck only for that. Thanks in advance.

You should have tried to submit it without optimization. I got AC with it in 500ms.

Hint: if you know mask of already paired women, you know the number of already paired men (it's just number of 1 bits in mask).

I think Expected Solution is O(n*2^n)

You did coins but not the problems before it? Or are you still uploading problems.

I solved Coins in the same way as you did but got WA. My solution What mistake did I make?

I like your idea, so i have uploaded the codes for the problems i solved. I will be adding more problems as i solve them and maybe even the explanations to some problems if i'm not too lazy.

Haven't even read Frog 3, the problem is actually easy with LiChao or something similar.

If you have a template, (I used https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h), it's one of the easier problems.

V and Y are simpler concepts IMO but reequire more not-template code.

I really like tests for Z! (I can't come up with a MAGIC solution which passes even half of them :D) sugim48, can you please show me some generators for it?

UPD: Why did I comment that instead of writing a PM? :D

Is there an easy way to do the rerooting in V? I had to make a segment tree for every node to store the already calculated values for its neighbours to make my solution not TLE. I understand why it TLEs without the segtree but cant figure out something simpler to fix it.

It can be solved in O(3ⁿ) time. In fact, and there are only 3ⁿ pairs (mask, submask).

dp[l][r] — minimum cost to merge from l to r Notice that in the last operation we will merge two consecutive blocks, and their total sum will be the sum of all slimes. So dp[l][r] = min(dp[l][k] + dp[k][r]) + a[l] + a[l + 1] + ... + a[r]. Which is O(n³)

Grundy

dp[i] = can we win from i stones?

dp[i] = any(not dp[i - x] for x in a)

B=A^k add all B[i][j]

Simple Matrix exponentiation. Find code here

The TLE is caused by visiting a state over and over.

Remember a node can have many parents.

I suggest you count the answer for each node on a topdown manner , and when visiting it again just return its value.

We have dp[i] = min(dp[j] + (h[i] — h[j])^2) + C , (h[i] — h[j])^2 = h[i]^2 + h[j]^2 — 2*h[i]*h[j], dp[i] = min(-2*h[i]*h[j] + h[j]^2 + dp[j]) + h[i]^2 + C, the line is (-2*h[j] , h[j]^2 + dp[j]).

https://codeforces.net/blog/entry/51880?#comment-358982

It seems that the intended solution does use the fact that the ranges only have positive weights.

Imagine my surprise there.

For small k you can find the number of walks of length k from a fixed end by making dp states as pair node index and length, for large k you might require cayley hamilton theorem. Check out this problem: https://discuss.codechef.com/questions/137912/treewalk-editorial

You can simply apply Berlekamp-Massey algorithm Linear Recurrence and Berlekamp-Massey Algorithm

Problem X: Sort all blocks according to w + s decreasing. Now DP(i, j) is the maximum value of stack containing blocks for the first i blocks and current stack can contain more j unit weight.

Transition is very similar to Knapsack problem:

• If we don't choose block i, then dp(i, j) -> dp(i + 1, j)

• If we choose block i, then it must satisfy j >= weight[i], dp(i, j) + value[i] -> dp(i + 1, min(j — weight[i], solid[i]))

Problem W:
l[v] — left of v-th query
r[v] — right
a[v] — score for v-th query
dp[i] — answer for prefix with length i if s[i] == '1'
in naive solution dp[i] = max(dp[j] + summ(a[v])) for all j < i , for all v if l[v] <= i <= r[v] && !(l[v] <= j <= r[v]))
it works in O(n^2)
to improve it you need to use segment tree witch can give you max on prefix, for dp[i] = get(0, i — 1)
so you need to keep tree valid at each iteration
if you encountered left edge of some query make += a[v] on segment (0, l[v] — 1)
if you encountered right edge of some query make -= a[v] on segment (0, l[v] — 1)
when dp[i] is calculated += dp[i] on segment (i, i)

UPD: "r[v] — 1" to "l[v] — 1"

Totally agree, that would be awesome :D

Editorial of this problem should be helpful: https://codeforces.net/gym/100589/problem/F

Calculating isn't hard, You just store the factorials from 1 to 10⁵, then you can directly get required values.

Let's calculate two values for every node after rooting the tree:

• down[node] = number of ways to paint the descendants of node when node is black

• up[node] = number of ways to paint vertices not in the subtree of node when node is black

The answer for any node is the product of these values, down[node] × up[node]

down[node] is easier to calculate, it is (we let the subtree rooted at son all white or we have down[son] ways). The base case is when the node is a leaf, we have 1 way to color it black.

up[node] is almost the same, (the 1 summing in the beginning comes from letting the parent white).

The trick part with up is that the modulus will not always be co-prime with the values we got (so we won't be able to calculate the inverse modular by, let's say, maintaining the product of all sons and dividing by the current son down value to get the up[node] fast). The solution is to keep a prefix and suffix product of the down values for the sons of a node, this way we don't have to divide or use modular inverses.

To solve it in O(n²) we have the following recurrence,

.

Now, h_i² + c is constant for fixed i, and we have to minimise the second term.

Now observe that the second term is of form y = mx + c, with (m, c) = ( - 2h_j, h_j² + dp[j]) which we are evaluating at x = h_i, which means we can use Convex Hull Trick to compute answer in O(nlogn).