### lunchbox's blog

By lunchbox, 4 months ago, This post contains the editorials for all tasks contained in the AtCoder DP Contest, since there is no official editorial. This is written by nwatx and me.

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis
Code

Analysis

Analysis
Code

Analysis
Code

Analysis
Code

## Z — Frog 3

Analysis
Code  Comments (21)
 » LUNCHBOX OFZ
•  » » LUNCHBOX OFZ
•  » » » LUNCHBOX OFZ
•  » » LUNCHBOX OFZ
 » LUNCHBOFZ
 » 4 months ago, # | ← Rev. 2 →   Someone finally wrote one!
 » Thanks a lot! It will be really helpful :)
 » Good Job,,, I was waiting for this from ages. Thanks a lot ... OFZ
 » ​I’m telling you, lunchbox is as cracked as he is jacked. Saw him the other day benching 696lbs while winning IOI. I asked him what he was doing and he said "better than you" and walked out with a explosion.
 » Thank you very much. I was solving these problems for past 2-3 days but couldn't find editorial. What a nice timing.
 » For the problem T-Permutation, I came up with the following idea: We first create n-1 edges directed from small numbered index to large numbered index. i.e. if we have $i^{th}$ sign as $<$ then we create an edge from $i$ to $i+1$. Now, the answer is the number of topological orderings for this graph. But I am stuck here. Can anybody help me how can I find the answer? Thanks in advance.
 » I can't find the Editorial for N — Slimes anywhere in this post... Am I missing something?
•  » » Thanks, I just added it!
 » This is one of the best list which covers all varients of Dp and gradient starting from absolute beginners. Very nicely written Analysis and Code! Thanks a lot:)
 » 3 months ago, # | ← Rev. 10 →   For task U(Grouping), you can reduce finding cost[mask] from $O(2^n \cdot n^2)$ to $O(2^n\cdot n)$ by doing like this. Spoilerfor (int i = 1; i < 1 << n; i ++) { int first = (int) log2(i), last = (int) log(i & -i); int p_first = 1 << first, p_last = 1 << last; if (first == last) cost[i] = 0; else cost[i] = cost[i -p_first] + cost[i - p_last] - cost[i - p_first - p_last] + a[first][last]; } And yeah, you can reduce calculation time from log2 by some precalculation, so you can do it in $O(2^n)$
 » 3 months ago, # | ← Rev. 2 →   I think in the analysis of W-Intervals the range is supposed to be [0,l-1] not [0,a-1]. lunchbox
•  » » Thanks for catching that!
 » 2 months ago, # | ← Rev. 8 →   sed
 » Time complexity for K is wrong.
 » Can someone explain problem L more clearly? Why is the transitions like that, and why in the analysis dp[i][i] = 0 but in the code dp[i][i] = a[i]?
•  » » Errichto explained it well on his stream about that contest. In case you didn't saw that https://youtu.be/FAQxdm0bTaw?t=6892The transition formula , can be rephrased in that way."Pick up the left bound , the opponent will pick up the best value on interval dp[L + 1][R]. The difference between your turn and opponents' next turn will be your answer for that interval.Pick up the right bound , the opponents will pick up the best value on interval dp[L][R — 1]. The difference betwene your turn and opponents' next turn will be your answer for that interval.Find max between these two choices."Can't explain why dp[i][i] = 0 in analysis , while in the actual implementation dp[i][i] = a[i].