awoo's blog

By awoo, history, 8 months ago, translation,

1901A - Line Trip

Idea: BledDest

Tutorial
Solution (Neon)

1901B - Chip and Ribbon

Idea: Roms

Tutorial
Solution (Roms)

1901C - Add, Divide and Floor

Idea: BledDest

Tutorial
Solution (awoo)

1901D - Yet Another Monster Fight

Idea: BledDest

Tutorial
Solution (vovuh)

1901E - Compressed Tree

Idea: BledDest

Tutorial
Solution (Neon)

1901F - Landscaping

Tutorial
• +47

 » 8 months ago, # |   0 In problem D, I am struggling to understand the statement. According to my perception, the answer to the first test case should be 7. I will choose i = 4. The chain of the indices to strike will be like 4->3->5->6->2->1. Please someone correct me.
•  » » 8 months ago, # ^ |   0 The spell's power must cover the worst-case scenario, given the chosen location.
•  » » » 8 months ago, # ^ |   0 Ohh! That last line. Thanks a lot.
•  » » » 7 months ago, # ^ |   0 Worst case I don't get it. First Index will chosen same for best case and worst case ?
•  » » » 6 months ago, # ^ |   0 then if we consider i=1 as a case that x must be atleast 9 right?
•  » » » » 5 months ago, # ^ |   0 you can actually choose the value of i, so despite x have to be 9 when i=1, you can choose other i instead of 1
 » 8 months ago, # |   0 Reached Specialist, in this round.
•  » » 8 months ago, # ^ |   0 Congrats!
•  » » » 8 months ago, # ^ |   0 Thanks
 » 8 months ago, # |   +3 problem E is a art.It takes a lot of effort to achieve perfection in whatever any direction.
 » 8 months ago, # | ← Rev. 2 →   0 for C, if we have min = 2 & max = 11. since min is even then x=0 & min = 1, max = 5 now if I go according to the editorial. it would take a total of 4 steps (1,3 -> 1,2 -> 1,1). but when min = 1 & max =5, I can take x =0 and reduce in 1 step less (1,2 -> 1,1) total of 3.am I missing something here?
•  » » 8 months ago, # ^ |   0 Of course. When min=1 and you don't add 1 then 1/2 = 0It's easier to think about it another way: if max is odd then by adding anything will not gain any steps reduction.
•  » » » 8 months ago, # ^ |   0 yeah this makes more sense.
 » 8 months ago, # | ← Rev. 2 →   0 Problem D: If it's necessary to check all indices as a first target point (according to tutorial), then why problem statement says that "Vasya chooses the first target optimally"?
•  » » 8 months ago, # ^ |   +4 Vasya chooses the first target optimally How would you figure out the optimal first target without checking all indices as first target point?
•  » » » 8 months ago, # ^ | ← Rev. 6 →   0 Oh yeah.. I got it. We need to take the minimum of these max values for an optimal first target (if I'm not wrong).Thanks...
•  » » » 5 months ago, # ^ |   0 Can't he choose the max element as the 1st target?
•  » » » » 5 months ago, # ^ |   0 That's not always optimal. 4 4 5 2 1 If we start at monster $2$ with health $5$, the attack might take the path $2\rightarrow 3\rightarrow 4\rightarrow 1$ and we need to start with $x = 7$. If instead we start at monster $1$ with health $4$, we can start with $x = 6$.
•  » » » » » 5 months ago, # ^ |   0 Thanks man
 » 8 months ago, # |   0 [Problem C] Can someone help me understand why choosing $x$ as the average between $max$ and $min$ (or $a$ and $b$) doesn't work?I guess it has somethings to do with parities and rounding down, but I honestly cannot figure it out myself.
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 x = (a + b)/2 a -> (a + (a+b)/2) / 2 b -> ( b + (a + b)/2) / 2 if b == a + 1: a -> (a + (a+a+1)/2)/2 -> (a+a)/2 ->a b -> (a+1 + (a+a+1)/2)/2->(a+a+1)/2->a diff reduce! if b == a+2: a -> (a + (a+a+2)/2)/2 -> (a+a+1)/2 ->a b -> (a+2 + (a+a+2)/2)/2->(a+2+a+1)/2->a+1 diff reduce too if b == a+3: a -> (a + (a+a+3)/2)/2 -> (a+a+1)/2 ->a b -> (a+3 + (a+a+3)/2)/2 -> (a+3+a+1)/2 ->a+2 diff reduce too ... 
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 8 0 0 1 0 6 4 3 0 a = 0 b = 6 1) avg = 3 x = 0 a -> (a + 3)/2 -> 1 a-> a/2 ->0 b -> (b + 3)/2 -> 4 b->b/2->3 abs = 3 3 2) avg = 2 x = 0 a -> (a+2)/2 ->1 a -> 0 b ->(b+2)/2 -> 3 b ->1 abs = 2 1 3) avg = 2 x = 0 a -> (2+2)/2 ->1 a -> 0 b -> (3+2)/2 -> 2 b -> 0 abs = 1 0 4) avg = 1 a -> (1+1)/2 ->1 b -> (2+1)/2 ->1 abs = 0 0 
•  » » 8 months ago, # ^ |   0 In addressing the question of why choosing $x$ as the average between the maximum ($b$) and minimum ($a$) values doesn't always yield the optimal result in problem C, it is essential to understand how the parity effects the calculations.We categorize the scenarios based on the parity of $a$, $b$, and $x$. By brute force, we identify eight possible parity combinations, but let's consider two illustrative examples: When $a=2i$, $b=2j+1$ and $x=2k+1$, the difference is $\left\lfloor (b + x)/2\right\rfloor - \left\lfloor(a+x)/2\right\rfloor = j - i + 1$. When $a=2i+1$, $b=2j$ and $x=2k+1$, the difference is $\left\lfloor (b + x)/2\right\rfloor - \left\lfloor(a+x)/2\right\rfloor = j - i - 1$. In the remaining six cases, the difference is $\left\lfloor (b + x)/2\right\rfloor - \left\lfloor(a+x)/2\right\rfloor = j - i$.The optimal strategy emerges from these calculations. Matching the parity of $x$ with $a$ tends to minimize the difference. This is because the difference doesn't depend on $k$ and different parity can lead to a larger difference when $a$ is even.Now, regarding your specific question, if $a=4i+1$ and $b=4j$, then choosing $x$ as the average, $x = \left\lfloor (a+b)/2\right\rfloor = 2(i + j) = 2k$, does not align with the optimal strategy. In this case, $x$ is even while $a$ is odd, and as we've established, matching their parities is crucial for optimality.
•  » » » 4 months ago, # ^ |   0 Can we also say as long as parity of a and x matches it doesn't matter whatever x is since difference is independent of k ?
•  » » » 3 months ago, # ^ |   0 Please take a look at my submission, I used the midpoint of the min and the max rounded up.Submission Number: 259266474
•  » » 8 months ago, # ^ |   0 Take a look at Ticket 17162 from CF Stress for a counter example.If you apply this strategy, the choice of $x$ at each step would be: $\frac{3+0}{2} = 1$, Resultant array: $[2, 0]$ $\frac{2+0}{2} = 1$, Resultant array: $[1, 0]$ $\frac{1+0}{2} = 0$, Resultant array: $[0, 0]$ However, it's possible to achieve this in 2 steps instead: Choose $x = 0$, Resultant array: $[1, 0]$ Choose $x = 0$, Resultant array: $[0, 0]$.
 » 8 months ago, # | ← Rev. 2 →   0 Question no. C, what does the line " You can consider all cases of parities of a and b to discover that it's always possible to divide the difference by 2, rounding down, and it's never possible to make it less than that. ".I am struggling to understand the solution. Please help me understanding the solution.
 » 8 months ago, # |   0 Why there's a tag of binary seach in problem D: although it seems at first glance that we can go for a approach like BS. But then realised there's nothing to do with BS.
•  » » 7 months ago, # ^ |   0 i have solved using Binary search, my solution
•  » » » 7 months ago, # ^ |   0 Didn't mean to say but you are increasing time complexity with binary search
 » 8 months ago, # |   0 Thanks for the fast editorial !
 » 8 months ago, # |   +12 I've added hints and thought process for problems: on CF Step
 » 8 months ago, # |   0 For problem D, my after-contest solution only involved checking the first location, the last location, and the location with the monster that needs the most spell power to kill.Is the test data weak, or is the strategy described above valid? Thanks.
 » 8 months ago, # |   0 In problem D, according to my understanding the worst case for 2 1 5 6 4 3 should be 2->1->5->6->4->3 and that would not be possible with 8 damage ?
•  » » 7 months ago, # ^ |   0 We are optimally selecting the start point, then we have to consider worst case after selecting start point
 » 8 months ago, # | ← Rev. 2 →   0 nvm I set my dp = -1 if it's not visited but I forget that the dp might be negative
 » 7 months ago, # |   0 i got accepted on F (237389815) by computing the overall hull in each step of the transition from old points to new points (the hardest part is to update the segment L = PQ that goes from a point P of the prefix hull to a point Q of the suffix hull). we have to keep the prefix hull, the suffix hull and L = PQ updated. for each point y of the suffix hull, consider the segments that goes from y to each point x of the prefix hull. if we fix y, we can binary search for the first x which cross product changes sign in relation to the point x-1. with this we can find the point x_best of the prefix hull such that the line that contains the segment (x_best, y) necessarily covers all points of the prefix hull. we now need only to verify if this line also covers the suffix hull, which can be done with a cross product in relation to y+1. the first point of the suffix hull that this happens is the point Q.in each step we should update the point Q based on the removals and insertions of new points of the current prefix and suffix hull. in order to keep it correct, we can do the following steps:1) update the suffix hull by removing its current leftmost point and undoing the points that have been removed by it (inserting them back). for each of these added points, we must verify wether or not its line covers the prefix hull. this can be done in O(log n) for each point with binary searching in the prefix hull + some cross products for verification, as explained. doing this we are locating the new position of point Q.2) update the prefix hull and change the suffix hull point Q status accordingly. since the added point covers all the prefix hull removed points (afterall, it defines the new prefix hull), we only verify if the point added changes the status of Q, with a binary search on the suffix hull, and update the point Q (basically, it can only make the point Q go more to the right).3) now we have an updated point Q, and can binary search again the prefix hull to find the other point P that makes segment L.
 » 7 months ago, # |   0 There is a small error in the editorial for problem D. The minimum spell power needed is $\displaystyle \min (\max_{j = 1} ^{i - 1} a_j +(n - j), a_i, \max_{j = i + 1} ^ {n} a_j + (j - 1))$ instead of the original $\displaystyle \max (\max_{j = 1} ^{i - 1} a_j +(n - j), a_i, \max_{j = i + 1} ^ {n} a_j + (j - 1))$. Guess it's just a typo.
 » 6 months ago, # |   0 In Problem C, I was thinking in terms of binary representation. Taking x as the most appropriate number to shift the prefix of same bits to the right considering left as the largest similar bit (with all before it as same) but didn't went very far with it. Any suggestion with approach?
 » 5 months ago, # | ← Rev. 2 →   0 For problen D, for this case61 6 1 1 6 1 , the accepted ans is 10, but shouldn't it be 9?1 6 1 1 6 15 6 7 8 9 4. <--- Like this?