BledDest's blog

Educational Codeforces Round 193 — Editorial
By BledDest, history, 4 weeks ago, translation, In English

2253A - The Best Card

Idea: BledDest

Tutorial
Solution (BledDest)

2253B - Hypercarp and the Control Panel

Idea: FelixArg

Tutorial
Solution (FelixArg)

2253C - Sum of Distinct Values in a Matrix

Idea: BledDest

Tutorial
Solution (BledDest)

2253D - Hypercarp and Interdimensional Jumps

Idea: FelixArg

Tutorial
Solution (FelixArg)

2253E - Diameter Intersections

Idea: BledDest

Tutorial
Solution (BledDest)

2253F - 4-beauty

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +55
  • Vote: I do not like it

»
4 weeks ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

But D just needed a simple greedy 386119523

The code
→ Reply
  • »
    »
    4 weeks ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Mind explaining why greedy works?

    → Reply
    • »
      »
      »
      4 weeks ago, hide # ^ |
       
      Vote: I like it +11 Vote: I do not like it

      ( we move from (x,y) to (0,0) )

      First of all, we know the maximum operations we can perform(k). the 'i'-th change in 'a' or 'b' will finally reduce 'x' or 'y' by k+1-i

      if one of the numbers is much bigger and can't reach the other number by using all the operation, so it's OK!

      Otherwise we consider that x>y then, we have a moment that 'x' reachs 'y' and probably become smaller than 'y'. in this case, the maximum difference between 'x' and 'y' is 'k' so it compensates with k-1 (and k-1 with k-2...) and finally the maximum difference becomes 1

      And the minimum difference between x and y is what we need!

      → Reply
»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Yeaah, finally )))

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Alternative solution of D:

Let $$$k$$$ be the largest integer with $$$\frac{k \cdot (k + 1)}{2} \le x + y$$$. Consider two bag with capacity $$$x, y$$$ respectively. For $$$w = k, k - 1, \ldots, 1$$$ in this order, put the item with weight $$$w$$$ into the bag with larger capacity remain. Let $$$x', y'$$$ denote the final capacity remain for two bags. We claim this process minimize $$$\max(x', y')$$$.

Proof.

W.L.O.G. assume $$$x \ge y$$$, call the bag with $$$x$$$ initial capacity the first bag, and the other be the second bag.

case 1 ($$$x \ge y + \frac{k\cdot (k + 1)}{2}$$$): trivial

case 2: items would be add into the first bag until its capacity is no more than the second bag, let $$$m$$$ be the item added to make this happen. then at this point, the difference of capacity between two bag would be no more than $$$m$$$, and in the subsequent item addition, the difference would be no more than the item added last, thus $$$|x' - y'| \le 1$$$ holds at the end, which achieve the lower bound of $$$\max(x', y')$$$.

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In Problem E (2253E), how would i know number of distinct LCAs would be O($$$\sqrt{n}$$$)? I was stuck with thinking it was O($$$n^2$$$) solution and won't pass.

→ Reply
  • »
    »
    4 weeks ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    We have $$$n-1$$$ edges, and each edge either part of diameter or not, and each node of diameter can form just a single distinct number, and sum of nodes limited on $$$n$$$, so you wont have more than $$$sqrt(n)$$$ distinct numbers. We can prove that by summing the first k small values such that sum won't exceed $$$n$$$.

    → Reply
  • »
    »
    4 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Firstly discard all nodes who's subtree does NOT have a descendant of maximal depth, as these can never be valid LCA's. For the remaining nodes, define $$$cnt[d]$$$ as the number of nodes at depth $$$d$$$.

    Since each path is guaranteed to continue down until the maximal depth, we know that $$$cnt[d + 1] \geq cnt[d]$$$. Furthermore, when depth $$$d$$$ contains a valid LCA (i.e. some node has two or more children with max depth descendants), then $$$cnt[d + 1] \geq cnt[d] + 1$$$.

    If there are $$$r$$$ distinct achievable depths, then the width increases at least $$$r$$$ times. After the i-th increase, the width is at least $$$i+1$$$. Therefore, among the levels containing these increases and the level immediately after each one, there are at least $$$1 + 2 + \ldots + (r + 1)$$$ nodes. Since the number of nodes per valid LCA depth grows quadratically, the number of valid LCA depths per node grows at a rate of $$$O(\sqrt{n})$$$.

    → Reply
»
4 weeks ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

I believe there's a typo in F. I think it should be x mod 2 != 0 and x mod 3 != 0 whereas it says the opposite now.

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I think F > C > E > D > B > A.

E is a very simple property about trees whose diameter length is odd, you just need to replace the middle edge of the diameter with a new vertex, and the problem becomes trivial (it turns into a tree with even diameter, where the center of the diameter has only two subtrees).

D is a straightforward "brute-force and find the pattern" problem; you can easily spot the relation between the number of operations and the landing position, and then it's just a simple contribution‑splitting construction.

As for C, my two-pointer got WA on test 2, which really annoyed me and cost me a lot of time.

For F, I never expected it could be solved with that kind of bitmask DP, so I won't comment much, but once you think of it, it's indeed not hard.

→ Reply
»
4 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I was able to write this much shorter solution for D. The idea is the same as the editorial's, but I didn't have to do any math to find the optimal ending point (from $$$(x,y)$$$, I just brute forced the walk back).

By the way, was anyone particularly troubled by C? For me, it took nearly an hour to find the correct greedy.

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Alternative $$$O(n)$$$ solution for B.

First, ignore the swap.

Since we can delete elements, from every maximal block of equal values we only need to keep one element. Therefore, the best answer without using the swap is just the number of blocks:

$$$ base = 1 + \sum_{i=1}^{n-1} [a_i \ne a_{i-1}] $$$

Now consider the swap.

It is enough to try swapping two elements that are already adjacent in the original array. If we choose two non-adjacent elements, we have to delete everything between them to make them adjacent, but those intermediate different blocks were already useful since we could keep one element from each of them.

So we only try swapping $$$a_i$$$ and $$$a_{i+1}$$$.

Locally, we have

... L | a[i] | a[i+1] | R ...

and after the swap

... L | a[i+1] | a[i] | R ...

The middle boundary does not change, since

$$$ [a_i \ne a_{i+1}] = [a_{i+1} \ne a_i]. $$$

Therefore, only the two outer boundaries can change. The change for this swap is

$$$ \Delta = -[a_{i-1} \ne a_i] -[a_{i+1} \ne a_{i+2}] +[a_{i-1} \ne a_{i+1}] +[a_i \ne a_{i+2}], $$$

ignoring terms that are outside the array.

Finally,

$$$ answer = base + \max(0, \max_i \Delta_i). $$$

Both base and the best delta can be calculated in the same loop.

Complexity: $$$O(n)$$$ time and $$$O(1)$$$ extra space.

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I loved C, D & E, Good Contest!

→ Reply
»
8 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hi, can anyone explain me this case in problem B... I was looking at the solution provided in the tutorial

1 , 1, 1, 2, 2, 2 ...... if i exchange middle 2 and middle 1 ..... I can keep all 6 but now answer is m+4 contrary to the answer provided in the tutorial ..... according to it i can only keep at max 4?

→ Reply
  • »
    »
    8 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    also in case 1, 1, 2, 3, 3 .... i don't have adjacent blocks of 2 but i can exchange 1 and 3 to keep all 5 (answer is m + 2 now)

    → Reply
  • »
    »
    7 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    In addition, thanks to a backup connection system, Hypercarp may swap two adjacent remaining modules at most once.

    So you can't swap middle 2 and middle 1, because they are not adjacent

    → Reply
    • »
      »
      »
      7 days ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Oh okay thanks , sorry I missed question's details

      → Reply