awoo's blog

By awoo, history, 11 months ago, translation, In English

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

Idea: adedalic

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +47
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The spell's power must cover the worst-case scenario, given the chosen location.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh! That last line. Thanks a lot.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Worst case I don't get it. First Index will chosen same for best case and worst case ?

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      then if we consider i=1 as a case that x must be atleast 9 right?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reached Specialist, in this round.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

problem E is a art.

It takes a lot of effort to achieve perfection in whatever any direction.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Of course. When min=1 and you don't add 1 then 1/2 = 0

    It's easier to think about it another way: if max is odd then by adding anything will not gain any steps reduction.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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"?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Vasya chooses the first target optimally

    How would you figure out the optimal first target without checking all indices as first target point?

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 6   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can't he choose the max element as the 1st target?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    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
    ...
    
    
  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    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
    
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please take a look at my submission, I used the midpoint of the min and the max rounded up.

      Submission Number: 259266474

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    1. $$$\frac{3+0}{2} = 1$$$, Resultant array: $$$[2, 0]$$$
    2. $$$\frac{2+0}{2} = 1$$$, Resultant array: $$$[1, 0]$$$
    3. $$$\frac{1+0}{2} = 0$$$, Resultant array: $$$[0, 0]$$$

    However, it's possible to achieve this in 2 steps instead:

    1. Choose $$$x = 0$$$, Resultant array: $$$[1, 0]$$$
    2. Choose $$$x = 0$$$, Resultant array: $$$[0, 0]$$$.
»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial !

»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

Submission: https://codeforces.net/contest/1901/submission/234308715

Is the test data weak, or is the strategy described above valid? Thanks.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We are optimally selecting the start point, then we have to consider worst case after selecting start point

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

nvm I set my dp = -1 if it's not visited but I forget that the dp might be negative

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problen D, for this case

6

1 6 1 1 6 1 , the accepted ans is 10, but shouldn't it be 9?

1 6 1 1 6 1

5 6 7 8 9 4. <--- Like this?