Educational Codeforces Round 164 Editorial

1954A - Painting the Ribbon

Idea: BledDest

1954B - Make It Ugly

Idea: BledDest

1954C - Long Multiplication

Idea: BledDest

1954D - Colored Balls

Idea: BledDest

1954E - Chain Reaction

Idea: BledDest

1954F - Unique Strings

Idea: adedalic

• 7 days ago, # ^ | It is rated. It has been announced that rating will be changed for educational round after div 2.

• 7 days ago, # ^ | 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."

  • 7 days ago, # ^ | In what order will the ratings be filed? Ratings for div 2 will be filed after applying changes for editorial round?

• 7 days ago, # ^ | It was supposed to be rated for div2 people..I donot know why it is unrated though

  • 7 days ago, # ^ | Oh yeah, that's weird

    • 7 days ago, # ^ | Don't worry,he says this contest is also rated.

      • 7 days ago, # ^ | Sorry,I watch blog Edu 163.

• 7 days ago, # ^ | It is a rated contest and it will affect your rating

• 7 days ago, # ^ | That's where log(A) factor is coming from.

  • 7 days ago, # ^ | 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

• 7 days ago, # ^ | How to become GM in 3 months like you , having solved only 74 problems.

  • 7 days ago, # ^ | may be that's his alternate account, if not then he is talented gem

  • 7 days ago, # ^ | I used to be on GM level before retiring over 5 years ago, this year I decided to make a comeback.

• 6 days ago, # ^ | ← Rev. 3 →   0 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.

  • 5 days ago, # ^ | Thank you!

    • 5 days ago, # ^ | 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 :)

      • 4 days ago, # ^ | maybe also mention that we should connect each vertice with all vertices whose color is different from it at first.

• 6 days ago, # ^ | 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

  • 6 days ago, # ^ | that helps thanks :)

• 6 days ago, # ^ | 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.

• 5 days ago, # ^ | I just wrote the exact same solution which looks intuitive to me

• 5 days ago, # ^ | Can you tell why sorting the array of colors is required?

  • 5 days ago, # ^ | 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.

    • 5 days ago, # ^ | Got it. Thank you very much

• 5 days ago, # ^ | I created a video talking about the optimal placement for the balls in D: Colored Balls.

  • 5 days ago, # ^ | 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

    • 4 days ago, # ^ | 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]a[i] when you see a[i]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]a[i]. Let's create a temporary DP ndpndp, which will contain all possible subsets that have a[i]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 ndpndp? All these subsets would have max element as a[i]a[i]. Therefore, we can compute the answer as max(sum/2,a[i])∗ndp[sum])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]

  • 26 minutes ago, # ^ | 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.

• 6 days ago, # ^ | Thanks, fixed.