### vaaven's blog

By vaaven, 17 months ago, translation,

## 1802A - Likes

Idea: Aleks5d, Preparation: vaaven

Solution
Code

## 1802B - Settlement of Guinea Pigs

Idea and preparation: Aleks5d

Solution
Code

## 1801A - The Very Beautiful Blanket

Idea and preparation: 4qqqq

Solution
Code

Idea: Tikhon228, Preparation: DishonoredRighteous

Solution
Code

## 1801C - Music Festival

Idea: vaaven, Preparation: ViktorSM

Solution
Code

## 1801D - The way home

Idea: Tikhon228, Preparation: Ormlis

Solution
Code

## 1801E - Gasoline prices

Idea and preparation: Kirill22

Solution
Code

## 1801F - Another n-dimensional chocolate bar

Idea and preparation: Tikhon228

Solution
Code

## 1801G - A task for substrings

Idea and preparation: grphil

Solution
Code
• +125

| Write comment?
 » 17 months ago, # |   +25 Testcases aside, I thought this was generally a really cool round (or at least all the problems I tried).
•  » » 17 months ago, # ^ |   +1 same
 » 17 months ago, # |   +14 What does SNM mean in tutorial of d1E?
•  » » 17 months ago, # ^ |   +18 It's DSU, fixed now
 » 17 months ago, # |   +8 It can be shown that it is optimal to minimize the number of shows first, and then maximize the amount of money.Can anyone share a proof of this statement? it seems intuitive but i failed to prove it:c
•  » » 17 months ago, # ^ |   0 If there are fewer shows, they can do another show to get more money
•  » » 17 months ago, # ^ | ← Rev. 7 →   +13 It can be seen that for all paths with end vertex $v$ and best vertex $t$, the number of shows is $0$ and/or the amount of money $< w_t$. So comparing any two possible paths with the same $v, t$, you can always do more shows on the path with fewer shows to get at least $w_t$ rubles, which would be more money than the other path.
 » 17 months ago, # |   +40
•  » » 17 months ago, # ^ |   +9 Never thought 69 would hurt so much
 » 17 months ago, # |   +1 This round is a little difficult, but the tasks are really interesting. I love div 2C.
 » 17 months ago, # |   +26 div1E smart solution is great!
 » 17 months ago, # |   0 Can I solve solve Div1 B with ternary search? If so, why my solution 197805657 did'nt work for this? Can someone help me?
 » 17 months ago, # |   0 alternate construction for beautiful blanket: for each row, simply use consecutive integers. denote the smallest power of 2 greater than m as 2^j. then let the first element in each row i be i*2^j, and the rest of the elements be simply the consecutive integers after i*2^j. this construction satisfies the conditions in the problem. examples: n=4, m=4 0 1 2 3 8 9 10 11 16 17 18 19 24 25 26 27 n=5, m=7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 
•  » » 17 months ago, # ^ |   0 Thanks ! Your solution is easier to prove its accuracy.
 » 17 months ago, # |   0 can any one say whats wrong with this solution for div2.c 0 1 4 5 8 2 3 6 7 10 12 13 16 17 20 14 15 18 19 22 24 25 28 29 32 
•  » » 14 months ago, # ^ |   0 Check the xor value of 3,6,13,16 (not zero)
 » 17 months ago, # |   -8 为什么没有中文版？Why is there no Chinese version?
•  » » 17 months ago, # ^ |   0 I think it is necessary,too.
 » 16 months ago, # |   0 I'm sure this is inadvertant, but in problem 1801A, after submitting any wrong solution, the pattern is literally visible in jury's answer xD.
 » 16 months ago, # |   0 Can somebody explain solution to Div 1. C? I can't understand what the editorial says.
•  » » 16 months ago, # ^ |   0 This is how I solved the problem. It's a bit long but I tried to make it as comprehensive as possible -the first thing we notice is no matter which track we start from in a particular song, the ending track will always remain the same and this position is the last track in the song such that it is strictly greater than all tracks before it. Let's denote this track's value as $X[i]$.We notice that if we place a song $j$ with larger $X[j]$ before a song $i$ all tracks in song $i$ become redundant since you can't continue any of them.So it's best if we sort the songs by the value of $X[i]$ in non decreasing order. But the issue is when we reach a case like -$n$ = 3first song — 1 2 3second song — 5third song — 4 5 6here we could place the third song after the first song to get a higher value.From now on we shall consider all songs as sorted by $X[i]$. So we do dp, where $dp[i]$ stores the max coolness in the prefix of length $i$.We also notice that the values of $dp[i]$ are non decreasing since we can always just continue off of the values of $dp[i-1]$.Now, let us denote $val[i][j]$ as the max that we can extend the $jth$ track in song i, for example the following song would have values — song = 4 1 3 6 2 8$val[i]$ = 3 -1 -1 2 -1 1I denote -1 for some $val[i][j]$ because they are not the max value in the prefix and they never add to the coolness.To compute $dp[i]$, we go through all tracks of song $i$ and binary search to find the first $X[k]$ that is strictly less than $a[i][j]$ (where $a[i][j]$ denotes the value of track $j$ in song $i$) and $val[i][j] \neq -1$, then we choose the max value of $dp[k]+val[i][j]$ over all valid tracks $j$.The final answer is $dp[n]$. Here is my submission
•  » » » 16 months ago, # ^ |   0 Thank you bro, great explanation!
•  » » » 15 months ago, # ^ |   0 I did pretty much the same thing that you did. I am somehow getting the wrong answer. Here is my submission link submission. I am having a hard time debugging. Could you please help
 » 16 months ago, # |   0 What's the correctness issue with using Dijkstra's directly using the same cost function as the editorial mentions, and using the shortest path found to n-1, rather than maintaining the dp state for NxN [v][best] pairs?
•  » » 5 months ago, # ^ |   0 It might be optimal to 'stop by' a different node for higher money from performances, before continuing on to the end.
 » 14 months ago, # |   0 The solution for 1801A can be simpler: just let M(i,j)=i*256+j.
 » 14 months ago, # |   0 I appreciate the fast editorial, however it has been quite a while and the solution for B has not been posted yet. Aleks5d please post the solution! It would help newbies like me out :)
•  » » 14 months ago, # ^ |   0 Let U be a guinea pig whose gender is not yet known.If $x=1$, let $U:=U+1$.If $x=2$, let $K$ be the number of guinea pigs whose gender is known.In the state of $U$, it must always be in a cage. For $K$, $⌈K/2⌉$ cages are needed.This is because in the worst case, the gender must be determined in order male, female, male, etc., and eventually $⌈K/2⌉$ cages are needed.However, since cages are not lost once they are bought, the maximum value of the answer is updated as follows.ans = max(ans, k + ceil(t/2))
 » 14 months ago, # | ← Rev. 2 →   0 C, Actually, We can always make all part as zero with this. int Y, X; cin >> Y >> X; cout << Y * X << endl; for (int y = 0; y < Y; y++) for (int x = 0; x < X; x++) cout << y * (1ll << 32) + x << (x == X - 1 ? "\n" : " "); 
 » 11 months ago, # | ← Rev. 2 →   0 Div-1 E doesn't really require HLD, we can simply use two fenwick trees to find hash of a path in $O(\log{n})$ similarly to how we query path sum in trees.Each path $u \rightarrow v$ can be divided into two subpaths $u \rightarrow lca(u, v)$ and $lca(u, v) \rightarrow v$.We can now build two fenwick trees upon euler tour of the tree, one to find the hash of upward vertical path $u \rightarrow lca(u, v)$ and one to find the hash of downward vertical path $lca(u, v) \rightarrow v$. The first fenwick will store value $(-par_u.P^{H - depth_u})$ at $EntryTime_u$ and $(+par_u.P^{H - depth_u})$ at $ExitTime_u$. The second fenwick stores value $(+par_u.P^{depth_u})$ at $EntryTime_u$ and $(-par_u.P^{depth_u})$ at $ExitTime_u$. ($par_u$ is the parent of $u$ in dsu, $H$ is height of the tree, and $P$ is the number we chose for exponents in hash)To find hash of upward vertical path $a \rightarrow b$, simply query range $[ExitTime_a, ExitTime_b]$ in the first fenwick tree. To find hash of downward vertical path $a \rightarrow b$, simply query range $[EntryTime_a, EntryTime_b]$ in the second fenwick. (Exponents can ofc be easily adjusted in $O(1)$ with $O(n\log{MOD})$ precomputation.)Implementation: link
 » 10 months ago, # | ← Rev. 2 →   0 4D dijkstra ? next 7D then what ? Nice Testcases
 » 10 months ago, # | ← Rev. 4 →   0 Can someone please explain Problem C- Music Festival solution? I did not understand the tutorial at all. vaaven
 » 4 months ago, # |   0 how does one get the logic of div2a (beautiful blanket) during contest?
 » 3 weeks ago, # |   0 Div 1D. Can we use the topological sort instead of dijkstra?270590828 — My wa6 solution.