awoo's blog

Educational Codeforces Round 164 Editorial
By awoo, history, 2 weeks ago, translation, In English

1954A - Painting the Ribbon

Idea: BledDest

Tutorial
Solution (BledDest)

1954B - Make It Ugly

Idea: BledDest

Tutorial
Solution (awoo)

1954C - Long Multiplication

Idea: BledDest

Tutorial
Solution (Neon)

1954D - Colored Balls

Idea: BledDest

Tutorial
Solution (Neon)

1954E - Chain Reaction

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1954F - Unique Strings

Idea: adedalic

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

»
2 weeks ago, # |
← Rev. 3   Vote: I like it -21 Vote: I do not like it

why unrated?

UPD:I understand

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

    It is rated. It has been announced that rating will be changed for educational round after div 2.

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

why unrated?

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    if you read the blog for latest div 2 contest it states that "UPD: The rating changes for Educational Codeforces Round 164 will be applied after this round."

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      In what order will the ratings be filed? Ratings for div 2 will be filed after applying changes for editorial round?

      → Reply
»
2 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

Alternative solution for E: transpose the array (find indices of each value), then iterate from $$$a_{max}$$$ to $$$1$$$ and count $$$islands[k]$$$ — the number of groups of connected monsters after doing $$$k$$$ dmg. Then just sieve $$$ans[k] = \sum_{i=1,2,3,..,\lceil \frac{a_{max}}k\rceil} islands[i \cdot k] $$$. 256372546

→ Reply
»
2 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

is the contest unrated

→ Reply
»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Correct me if I'm wrong, Educational contest will not effect the rating, right?

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

Talking about the complexity of E — do we need to multiply it by 1+1/2+...+1/A? Or should we count it as a constant?

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

    That's where log(A) factor is coming from.

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

      My bad. I had a solution similar to authors' one, but I used a binary search for counting, so that I got O(n + A * (log(A) ^ 2)) complexity

      → Reply
»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

F has almost linear (O(n*log log n)) solution: The high-level idea is the same, but I managed to calculate FixedPoints(g) in O(g). Since sum of divisors grows as O(n*log log n), the overall time complexity is the same.

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

    How to become GM in 3 months like you , having solved only 74 problems.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      may be that's his alternate account, if not then he is talented gem

      → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I used to be on GM level before retiring over 5 years ago, this year I decided to make a comeback.

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

Problem D, are there any similar problems with the idea of the 'standard problem' said in the solution?

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

    Check this one out. It is based on that standard problem. FYI, editorial for this does a good job of explaining it. If you still have confusions on how it works think Bipartite Graphs.

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

      Thank you!

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

        For those interested in a formal proof, I think this might help: https://en.wikipedia.org/wiki/Tutte_theorem

        The problem of maximizing the number of pairs can be reformulated as determining whether graph has a perfect matching (or near perfect matching if |V| is odd).

        As for the theorem, the only way to create >1 connected components is to remove all colors except one (i). Theorem says that a[i] <= number of removed vertices, which is sum(a[j]) for all j except i.

        Hope this helps anyone :)

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

          maybe also mention that we should connect each vertice with all vertices whose color is different from it at first.

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

problem E

Whats the coefficient thing? I understand that we need to have some coeff for all ai so that its easier to sum over, and then formula is given to find coeff, whats the intuitive rational on what are we trying to achieve?

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

    The coefficient comes from expanding the equation. We can see when max(0, a[i] — a[i — 1]) contributes to the sum.

    For this a[i-1] should be less than a[i]. Then if a[i-1] < a[i], a[i] adds to the formula ( (+1) * a[i], where +1 is the coefficient). Now notice that a[i] also appears in the next consecutive difference, namely a[i+1]-a[i]. So if a[i] < a[i+1], as you see we should subtract a[i]. Thus ( (-1) * a[i] ) should be added. So for example, coefficient is (+1) + (-1) = 0 when both if's hold

    → Reply
»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

For problem D, O(N * V) solution works. Actually when upsolving I didn’t notice the restriction on the sum of a[i] but still solved with all core ideas which are in the official solution. The idea is that for an element to be > (sum of other elements), sum of elements is bounded by 2V.

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

In problem D, during the contest, I did not notice a limit on the sum of all the elements of the array. However, even without this limitation, the problem can be solved in O(N* maxA). In my solution, I keep a knapsack for sums less than 5000, and separately store the number of possible even/odd sums, as well as the sum of all possible even/odd sums of subsets. There is my code for this task: 256335037

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

    I did the same. But u dont have to calculate number of subsets with odd sum using dp. Number of subsets with odd sum for n numbers is 2^(n — 1), if there is at least one odd number.

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

Hey guys, can you suggest some problems similar to "D" in here. I am seeing too many different implementations of the same exact ideas with massive variations in runtime & memory. I implemented the same idea with a take / not-take dp where I consider both possibilities of taking/not-taking current element in a set : 256634006.

I want to make sure if this method is enough for such problems or should I consider other implementation too. Hence, if you know any similar problems, please reply.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I just wrote the exact same solution which looks intuitive to me

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

    Can you tell why sorting the array of colors is required?

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

      To calculate the minimum number of groups formed in a set, it is either the biggest element or ceil(half of total sum). Now why is that? Its because if the biggest element is bigger than or equal to the sum of the rest of the elements, you can completely pair up every other element with it, if it is less than the sum of rest of the elements in that set, then you will do random pairing which will result in ceil(sum/2) teams.

      To avoid calculating the biggest element, I have sorted it. So that the last element in a set is automatically the biggest element in it.

      Refer to dry running sample case 3 for complete understanding.

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

        Got it. Thank you very much

        → Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I created a video talking about the optimal placement for the balls in D: Colored Balls.

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

      Very good video and nice proof by using pigeon-hole principle! Can you share some insights on using contribution technique to solve this problem? Like in these solns : 256348397 , 256465864

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

        Sure, you can take a look at my submission where I do the same thing, but with explicit DP arrays.

        For a prerequisite, watch this video timestamp 10:50 to 14:30

        As stated in the video, in iterative DP problems, you should always think about how you can "refresh" the answer when you append an element to the already constructed answer.

        Suppose you are processing elements in increasing order, and you've already created all the subsets possible so far, denoted by dp[sum]. Now, what happens when you append a new element? There will be 2 new class of subsets : Those which are already created, and those where you compulsorily add the current element in all of the already created subsets.So

        ndp[sum] = dp[sum] + dp[sum - a[i]]

        But if you keep on constructing the subsets and wait to compute the answers at the end, it'll be too late, because by that time, you might not know that maximum element of the subset. So, we'll impose a rule : Construct the answer for all the subsets necessarily containing $$$a[i]$$$ when you see $$$a[i]$$$ for the first time.

        So, in order to avoid mixing the subsets, we will first compute the answer when we add $$$a[i]$$$. Let's create a temporary DP $$$ndp$$$, which will contain all possible subsets that have $$$a[i]$$$. It's clear that

        ndp[sum] = dp[sum - a[i]]

        Note that we intentionally removed the addition since we don't want to pollute our subsets. Now, what is special about the subsets represented by $$$ndp$$$? All these subsets would have max element as $$$a[i]$$$. Therefore, we can compute the answer as $$$max(sum/2, a[i])*ndp[sum])$$$

        Once we've computed the sum, we can finally mix these subsets, because we no longer need to track the max info anymore. Therfore,

        ndp[sum] += dp[sum]
        → Reply
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This approach & one mentioned in tutorial seem to faulter in case of suppose input is 3 balls with count 7 7 7 respectively, the approach mentioned gives 53 as output but manually checking it gives 56 as output.

      Is input I mentioned valid, if valid then kindly someone guide why is this happening. tutorial approach:

      singleton sets {7}*3 value=7*3

      sets with two elements {7,7}*3 value=7*3

      sets with three elements {7,7,7} value=11 because no element is greater than half of sum of balls (21+1)/2, but actually value should be 14 as two colored balls 7 each will be paired together & form 7 groups and 3rd colored ball will also form 7 groups so total is 14 not 11.

      BledDest pls guide.

      → Reply
      • »
        »
        »
        »
        8 days ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Call the colors as A, B, C. Here is an arrangement that only requires 11 boxes and not 14 boxes.

        A | A | A | A | A | A | A | B | B | B | B
B | B | B | C | C | C | C | C | C | C | _

        Each box contains one ball from the top line and one ball from the bottom line. It uses the same strategy from the video, i.e arrange all balls of the same color in a cyclic manner.

        By your reasoning, answer for 2 2 2 with 3 elements should be 4, because you pair up the first 2 balls with each other. But if you don't be greedy and instead pair up the first and last color, you only need 3 box

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

          thanks for guiding,I should have used cyclic approach before posting, will be careful in future

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

There's a typo in editorial for F. Formula for $$$all$$$ should be $$$\sum_{i=0}^{on}\binom{g}{i}$$$ instead of $$$\sum_{i=0}^{on}\binom{g}{on}$$$.

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

Can author explain me why "It means that if gcd(i,n)=gcd(j,n) then FixedPoints(i)=FixedPoints(j) since in both cases we'll get exactly the same group division. So, we can rewrite the answer as following" true ? while FixedPoint(i) depend on "no more than c+k ones and at least c consecutive ones" and group of 2 case different. Thank.

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

Thank you for fast editorial

→ Reply
»
12 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I was wondering if there is a way to find $$$min$$$ groups that can be formed if we are allowed to have atmost $$$k$$$ different balls in one group in general. Is there a way to find that in $$$o(n)$$$ time just like the tutorial states for $$$k <= 2$$$.

→ Reply