### vaaven's blog

By vaaven, 9 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 Comments (40)
 » Testcases aside, I thought this was generally a really cool round (or at least all the problems I tried).
•  » » same
 » What does SNM mean in tutorial of d1E?
•  » » It's DSU, fixed now
 » 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
•  » » If there are fewer shows, they can do another show to get more money
•  » » 9 months ago, # ^ | ← Rev. 7 →   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.
 » •  » » Never thought 69 would hurt so much
 » This round is a little difficult, but the tasks are really interesting. I love div 2C.
 » div1E smart solution is great!
 » Can I solve solve Div1 B with ternary search? If so, why my solution 197805657 did'nt work for this? Can someone help me?
•  » » Hi I tried the problem with binary search got stuck WA on test 2. Have you found why this approach doesn't work? Or provide case when it fails?
 » 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 
•  » » Thanks ! Your solution is easier to prove its accuracy.
•  » » How did you come up with this solution?
 » Why I changed N to 256,I got AC?WA CodeAC Code
 » 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 
•  » » Check the xor value of 3,6,13,16 (not zero)
 » 为什么没有中文版？Why is there no Chinese version?
•  » » I think it is necessary,too.
•  » » 可能是他们不会写中文
•  » » » 有道理
 » Can someone please explain the logic behind this part of the code in question A. Im not getting how we are printing the min string.  for (int i = 1; i <= n; ++i) { if (i <= dislikes * 2) cout << i % 2 << ' '; else cout << (i - dislikes * 2) << ' '; } cout << '\n'; 
 » 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.
 » Can somebody explain solution to Div 1. C? I can't understand what the editorial says.
•  » » Same here, cannot understand the editorial
•  » » 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
•  » » » Thank you bro, great explanation!
•  » » » 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
 » 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?
 » The solution for 1801A can be simpler: just let M(i,j)=i*256+j.
 » 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 :)
•  » » Again, it has been 2 days and the editorial has still not been posted for B. Please do so!
•  » » 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))
 » 6 months ago, # | ← Rev. 2 →   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" : " "); 
 » Ya
 » 3 months ago, # | ← Rev. 2 →   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
 » 2 months ago, # | ← Rev. 2 →   4D dijkstra ? next 7D then what ? Nice Testcases
 » 7 weeks ago, # | ← Rev. 4 →   Can someone please explain Problem C- Music Festival solution? I did not understand the tutorial at all. vaaven