### awoo's blog

By awoo, history, 5 weeks ago, translation,

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

Tutorial
• +95

 » 5 weeks ago, # | ← Rev. 3 →   -21 why unrated?UPD:I understand
•  » » 5 weeks ago, # ^ |   0 It is rated. It has been announced that rating will be changed for educational round after div 2.
 » 5 weeks ago, # |   0 why unrated?
•  » » 5 weeks ago, # ^ |   +6 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."
•  » » » 5 weeks ago, # ^ |   +6 In what order will the ratings be filed? Ratings for div 2 will be filed after applying changes for editorial round?
 » 5 weeks ago, # |   -16 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
 » 5 weeks ago, # |   -8 is the contest unrated
 » 5 weeks ago, # |   +5 Correct me if I'm wrong, Educational contest will not effect the rating, right?
•  » » 5 weeks ago, # ^ |   +7 It was supposed to be rated for div2 people..I donot know why it is unrated though
•  » » » 5 weeks ago, # ^ |   0 Oh yeah, that's weird
•  » » » » 5 weeks ago, # ^ |   +4 Don't worry,he says this contest is also rated.
•  » » » » » 5 weeks ago, # ^ |   0 Sorry,I watch blog Edu 163.
•  » » 5 weeks ago, # ^ |   0 It is a rated contest and it will affect your rating
 » 5 weeks ago, # | ← Rev. 2 →   0 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?
•  » » 5 weeks ago, # ^ |   0 That's where log(A) factor is coming from.
•  » » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # |   +16 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.
•  » » 5 weeks ago, # ^ |   0 How to become GM in 3 months like you , having solved only 74 problems.
•  » » » 5 weeks ago, # ^ |   -9 may be that's his alternate account, if not then he is talented gem
•  » » » 5 weeks ago, # ^ |   +20 I used to be on GM level before retiring over 5 years ago, this year I decided to make a comeback.
 » 5 weeks ago, # |   0 Problem D, are there any similar problems with the idea of the 'standard problem' said in the solution?
•  » » 5 weeks 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 weeks ago, # ^ |   0 Thank you!
•  » » » » 5 weeks ago, # ^ |   0 For those interested in a formal proof, I think this might help: https://en.wikipedia.org/wiki/Tutte_theoremThe 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 :)
•  » » » » » 5 weeks ago, # ^ |   0 maybe also mention that we should connect each vertice with all vertices whose color is different from it at first.
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   +4 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
•  » » » 5 weeks ago, # ^ |   0 that helpsthanks :)
 » 5 weeks ago, # |   +16 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.
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   0 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 weeks ago, # |   +1 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.
•  » » 5 weeks ago, # ^ |   -8 I just wrote the exact same solution which looks intuitive to me
•  » » 5 weeks ago, # ^ |   0 Can you tell why sorting the array of colors is required?
•  » » » 5 weeks ago, # ^ |   0 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 weeks ago, # ^ |   0 Got it. Thank you very much
•  » » 5 weeks ago, # ^ |   +5 I created a video talking about the optimal placement for the balls in D: Colored Balls.
•  » » » 5 weeks ago, # ^ |   0 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
•  » » » » 5 weeks ago, # ^ |   0 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:30As 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] 
•  » » » 4 weeks ago, # ^ |   0 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*3sets with two elements {7,7}*3 value=7*3sets 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.
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 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
•  » » » » » 4 weeks ago, # ^ |   0 thanks for guiding,I should have used cyclic approach before posting, will be careful in future
 » 5 weeks ago, # |   0 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}$.
•  » » 5 weeks ago, # ^ |   0 Thanks, fixed.
 » 5 weeks ago, # | ← Rev. 3 →   0 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.
 » 5 weeks ago, # |   0 Thank you for fast editorial
 » 4 weeks ago, # | ← Rev. 2 →   0 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$.
 » 2 weeks ago, # |   0 Can I know what's the mistake — 46th case failed!! submission
 » 6 days ago, # |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } why did i find the link to this song https://www.youtube.com/watch?v=kSjj0LlsqnIin the A problem ? XD