lunchbox's blog

By lunchbox, 5 weeks ago, In English

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.

A — Frog 1

Analysis
Code

B — Frog 2

Analysis
Code

C — Vacation

Analysis
Code

D — Knapsack 1

Analysis
Code

E — Knapsack 2

Analysis
Code

F — LCS

Analysis
Code

G — Longest Path

Analysis
Code

H — Grid 1

Analysis
Code

I — Coins

Analysis
Code

J — Sushi

Analysis
Code

K — Stones

Analysis
Code

L — Deque

Analysis
Code

M — Candies

Analysis
Code

N — Slimes

Analysis
Code

O — Matching

Analysis
Code

P — Independent Set

Analysis
Code

Q — Flowers

Analysis
Code

R — Walk

Analysis
Code

S — Digit Sum

Analysis
Code

T — Permutation

Analysis
Code

U — Grouping

Analysis
Code

V — Subtrees

Analysis

W — Intervals

Analysis
Code

X — Towers

Analysis
Code

Y — Grids 2

Analysis
Code

Z — Frog 3

Analysis
Code
 
 
 
 
  • Vote: I like it
  • +242
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

LUNCHBOX OFZ

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

LUNCHBOFZ

»
5 weeks ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Someone finally wrote one!

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Thanks a lot! It will be really helpful :)

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Good Job,,, I was waiting for this from ages. Thanks a lot ... OFZ

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

​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.

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you very much. I was solving these problems for past 2-3 days but couldn't find editorial. What a nice timing.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I can't find the Editorial for N — Slimes anywhere in this post... Am I missing something?

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like 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:)

»
2 weeks ago, # |
Rev. 10   Vote: I like it +10 Vote: I do not like it

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.

Spoiler
»
2 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I think in the analysis of W-Intervals the range is supposed to be [0,l-1] not [0,a-1]. lunchbox