### awoo's blog

By awoo, history, 5 months ago, translation,

1728A - Colored Balls: Revisited

Idea: BledDest

Tutorial
Solution (Neon)

1728B - Best Permutation

Idea: BledDest

Tutorial
Solution (Neon)

1728C - Digital Logarithm

Idea: BledDest

Tutorial
Solution (awoo)

1728D - Letter Picking

Idea: BledDest

Tutorial
Solution (awoo)

1728E - Red-Black Pepper

Idea: BledDest

Tutorial
Solution (awoo)

1728F - Fishermen

Idea: BledDest

Tutorial
Solution (BledDest)

1728G - Illumination

Idea: BledDest

Tutorial
Solution (awoo)

• +113

 » 5 months ago, # | ← Rev. 2 →   +13 Awesome problemset; I really liked Red-Black Pepper, even though I couldn't solve it on time!As for problem D... somehow, my O(n) greedy-ish algorithm passed all pretests and didn't get yoinked out of existence after system testing..... I'll be confused for a whileEdit: Here is my source code if anyone wants to look at it: Source code#include #include using namespace std; int t, n, dr, i; char s[2010]; int main() { cin >> t; while (t--) { cin >> (s+1); n = strlen(s+1); for (i = 1; i <= n/2 && s[i] == s[n-i+1]; i++); dr = n-i+1; for (; i <= dr && s[i] == s[i+1]; i += 2); if (i > dr) cout << "Draw"; else cout << "Alice"; cout << '\n'; } return 0; } 
•  » » 5 months ago, # ^ |   +14 It can be proven that Bob have no winning strategy for every string. And a draw can be if and only if string have form ABC, where C is reversed A and B consists of pairs of identical letters standing next to each other (i.e. have form aabbcc...)
•  » » 5 months ago, # ^ |   +3 I wanna know the intuition about your approach . Y does Bob never loose ?
•  » » » 5 months ago, # ^ |   +12 Since Alice always goes first, she can just pick the most optimal letter which remains. If there is a letter that Bob can pick to beat Alice, Alice can just pick that letter instead of the last letter she chose.
•  » » » » 5 months ago, # ^ |   +8 This seems like a plausible explanation. But always going first doesn't guarantee a win(even though in this case it does). A good example would be of zugzwang in chess.
•  » » » » 5 months ago, # ^ |   +6 But Alice can not pick s[2], s[n — 1] before s[1] or s[n] be picked。
•  » » » » » 5 months ago, # ^ | ← Rev. 3 →   +6 True, Alice can't pick s[2], s[n-1] in the first turn. But she can force Bob to not be able to pick one of them.For example consider: "zazz"Obviously if Alice picks s[1] then Bob will win by picking s[2]. So instead, Alice can force the game so that she will be the one to pick s[2]. If Alice picks s[n] on her first move then Bob has to pick one of s[1] or s[n-1] and Alice wins.You can apply the same logic to larger strings:"zabcaz" Alice picks s[1] Bob picks s[2] Alice picks s[3] Bob picks s[4] Alice picks s[5] Bob picks s[6]
•  » » » » » » 5 months ago, # ^ |   +4 Thank You! This greedy approach is cool
•  » » » » » » 2 months ago, # ^ |   0 Will this approach work for "yabz"? Because for both the choices Alice has, she'll lose.
•  » » » » » » » 10 days ago, # ^ |   0 Yes it will. Remember, the chosen character needs to be prepended and not appended. So, the game can go as follows : Alice chooses z, Bob chooses b, Alice chooses a and Bob chooses y. Hence, Alice wins. You can try all possible combinations and you'll notice that Alice will win in all of them.
•  » » » 5 months ago, # ^ |   0 My approach to Problem D is an O(n) solution. Since Bob never wins(Can check using strings of length 2,4,6 and manually verifying cases), what we need is to find the condition for the conclusion when the game ends in a draw. Firstly let us modify the input string given from s->s' where s' is s after removing all consecutive letters from start and end such that s[i]=s[length-1-i] and break the loop when s[i]!=s[length-1-i]. The reason is that if Alice picks one such letter then Bob can pick the letter from the opposite end to get a string to be the same as Alice's. Next the string s' left after removing all such letters (even 0 letters can be removed) ought to be of the form AABBCC.....ZZ where A,B,C,Z represents any letter. Reason is that if the string was AABBCC.....YZ,then Alice can pick Z and Bob has no other option but to pick either A or Y....i.e. He can never Draw with Alice and hence can only lose.
•  » » » 10 days ago, # ^ |   0 I think the most important thing to note here is that the length of the string is even + the chosen letters are prepended in the string. If either of the above conditions were not true, then Bob could have had a chance to win.
•  » » 5 months ago, # ^ |   +3 please explain your approach
•  » » » 5 months ago, # ^ |   0 It was just like what magni93 described. I guessed heuristically (proof by lack of counterexample) that Bob can't win, so that he can at best force a Draw. Additionally, a Draw can be forced only if the string looks like this: ABC, where A is an arbitrary sequence of characters, C is its reverse, and B is a sequence of pairs of adjacent identical numbers. Example: abcgghhddcba. Thus, for the first part (palindromic part), if Alices chooses a side, Bob can choose the other and maintain the Draw, and for the second, Bob can always choose the same side as Alice.
•  » » » » 5 months ago, # ^ |   +4 this is outta my league.. for now.. thx for explaining though i need more experience with questions
•  » » » 5 months ago, # ^ |   +3 If we already know that Bob can never win, then we can proof as below.Proof: One necesary condition for a draw is "The occurence number of Every letter cnt[letter] is even". Let's proof that s=ABC by induction (where C is reversed A and B consists of pairs of identical letters standing next to each other). For len(s) == 2, it's obvious. Suppose len(s) > 2 and cnt[letter] is even for every letter.In the first turn, if Alice's best choice is s[1], and Bob's is s[n]， s[1] == s[n], then by induction, s must be s[1] ABC s[n] which is also a form of ABC.If the first turn Alice's best choice is s[1], and Bob's is s[2]，then s[n] = s[1] or s[n] = s[n — 1] or else Alice will win. If s[n] = s[n — 1]，Alice can alway pick one from the same side before a letter equals s[n] is met，by the induction s is the form of B. If s[n] == s[1] and s[n] != s[n — 1], Alice can choose s[n], Bob can choose s[1], and the remains must be draw too, otherwise Alice have no reason to choose s[1]. By induction, s also has form B.
•  » » » » 5 months ago, # ^ |   +3 thank you
•  » » 5 months ago, # ^ |   +4 Me after seeing other's D codes after contest and finding everyone used the same 100+ line dp algorithm and that doesn't remotely resemble my code.
 » 5 months ago, # | ← Rev. 2 →   +4 (Problem E) Let $d_1, d_2, ..., d_n$ be the sequence of values of $-a_i - b_i$ in a non-increasing order. Shouldn't it be $-a_i + b_i$?UPD: Fixed now, thanks!
 » 5 months ago, # |   0 Let xi be the value of the variable x after i steps. Note that xn−1 should be less than pn for xn to be not equal to 0. It means that xn does not exceed 2pn−1. I think this statement is not enough to prove that we can not get a better value than 2n-1.
 » 5 months ago, # | ← Rev. 2 →   +3 for C my approach is like first remove element if it is present in both the arrays. After that only distinct element remains then decrease all the elements > 9 to single digits and add 1 to ans. Then repeat step 1 to remove duplicates. now only one digit distinct element remains for each of these elements add 1 to ans(if it is != 1). I think that my approach is right but it is not working can anyone tell why https://codeforces.com/contest/1728/submission/171533183
•  » » 5 months ago, # ^ |   0 Your greedy approach doesn't work. For instance, if the distinct elements are a = 11, b = 12345678901. In this case, you have f(b) = a. In your approach, you would need more steps.
•  » » » 5 months ago, # ^ |   0 but the array elements are always < 10^9
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 not a valid testcase, ai,bj<10^9 is given in conditions
•  » » 5 months ago, # ^ |   +3 You were doing ans++ instead of ans += i.second on lines $296$ and $304$. Also, iterating and changing elements in map at the same time can cause bugs. For some reason, just using map instead of unordered_map does the trick in this case, but I am not sure why. I used to think that changing values while iterating would always mess the map's pointers up. Anyway, avoid using the standard unordered_map, you can get hacked in a contest. You can read more about it in this blog.AC solution
•  » » » 5 months ago, # ^ |   0 Thankyou.
•  » » 5 months ago, # ^ |   0 As pointed out by brenner1, there was a trivial error in the code. I was wondering if the algorithm can be deemed incorrect even if it passes the test cases. Because it doesn't solve a more general problem (with higher constraints).
•  » » » 5 months ago, # ^ |   0 For higher constraints, we can keep repeating the steps in a while loop until both arrays are equal (won't have much impact on time complexity aswell). Also I think this is more of a brute-force kind of approach.
•  » » » 5 months ago, # ^ |   0 A problem is a problem under the given constraints. If you make a problems constraints higher of course a lot of solutions won't pass. But this given problem is for this given constraint and he only has to solve for it.
•  » » » » 5 months ago, # ^ |   0 I just find it convenient to believe that the correct algorithm is more important. A correct algorithm is correct independent of the constraints. That's the only difference between a problem and an algorithm ig. I now realize that it's futile to discuss/categorize this.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 No algorithm is correct independent of constraints unless the algorithm works in constant time. Sieve of erastothenes is an algorithm in O(sqrtn), which would only work work upto n<10^18. So would you not call it an algorithm?
•  » » » » » » 5 months ago, # ^ |   0 What does time complexity have to do anything with whether the algorithm is correct or not? Given any n, I can always find primes less than n using the Sieve of Eratosthenes. Hence, it's an algorithm. Just as a brute force check for prime is also an algorithm. However, some trick that would be able to calculate primes only less than a certain number 'm' would not be termed an algorithm.
•  » » » » » » » 5 months ago, # ^ |   +1 Ah u were talking like that. In that case you just have to get used to the fact that in a contest its better so solve the problem with given constraints than not at all.
•  » » » » » » » » 5 months ago, # ^ |   0 Understood :)
•  » » 5 months ago, # ^ |   0 My solution is as same as you and I get accepted https://codeforces.com/contest/1728/submission/171984436
 » 5 months ago, # |   0 How to prove that Bob never wins in Problem D ?
•  » » 5 months ago, # ^ |   +1 One way would be to look dp transitions. Having dp[i][i + 1] being equal to "Alice" or "Draw" there's no way to build winning dp of longer length.The other way would be the following: if Bob's string does not equal to Alice's, then it is no draw for sure. Consider there is some letter in result so Alice's string differ in that letter of Bob's string and all the other on prefix are the same. No matter how Bob plays Alice manages to take smallest letter when the left string is xSS...SSy. Regardless the step we encounter this configuration at. In fact Alice's strategy to take smallest letter at each step also leaves Bob no place to win.
 » 5 months ago, # |   +3 Having the maximum values in C as $10^9$ actually allows for a simpler (imo) solution. A multi-digit number will always become a single-digit number by performing the operation. It's impossible for an operation to produce a multi-digit number.So after you get rid of all the overlaps from the initial arrays, you can now safely perform the operation on every multi-digit number in both arrays (if a multi-digit number is present in one array but not the other, it's impossible for it to be generated on the latter, so you must apply the operation on it in the former). No sorting needed here. Now everything is a 1-digit number. We can check for overlaps again, and get rid of them. When there are no overlaps remaining, we need to turn everything that isn't 1 into a 1, so we count how many non-1s we have, add that to our operation count, and get our final answer.
•  » » 5 months ago, # ^ |   +1 Even if the limit on C was larger, this algorithm would be fine if we just replace $9$ by the max digits that any of the array element can have.
 » 5 months ago, # |   +11 I'm going to link this $O(n)$ solution for Problem D here: https://codeforces.com/blog/entry/106726?#comment-951491
 » 5 months ago, # |   +24 I'll copy my approach for problem D from the annoucement :First, because Alice play first and the length of the string is even, Alice can force Bob to take any particular character in the string by simply never take it. After Bob take this character either the string become empty and the game end, or it become a shorter string with even length, then we use this strategy again for the shorter string. By take advantage of this, when play optimally Alice will never lose.The only way for Bob to draw is to always take the same character as Alice. Now we reverse the game from the end to begin to see what the original string would look like :For each double turn of Alice + Bob, we add 2 identical character to the same side or different side of our string (for example : aa→aabb,bbaa or baab)The critical point is that if we add to the different side, we can't add to same side anymore. Take the example baab→baabcc, here Alice can take b and Bob can't take any b so he will loseSo the form of our string is : half palindrome + some pairs + other half palindrome, the 1st and 3rd part form a palindrome
 » 5 months ago, # | ← Rev. 3 →   +16 I have another solution for 1728E - Red-Black Pepper which runs in $O(N \log_2{(N)} + NK \log_2{(K)} + M \frac{N}{K})$ where $K$ is a constant. I have been able to obtain a runtime of $1606$ ms by setting $K = 150$ in this submission: 171530099.My solution doesn't require the knowledge of diophantine equations and doesn't use some of the observations given in the editorial above. It relies on a square root idea.Setting $K = \sqrt{N}$ results in a complexity of $O(N \sqrt{N} \log_2{(\sqrt{N})} + M \sqrt{N})$ which, I suspect due to poor constant factor, unfortunately TLEd for me.Edit: Thanks to satyam343 for pointing out a flaw in my complexity analysis. I've fixed it.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +19 If I am not wrong, your solution runs in $O(N \log{(N)} + N \cdot K \log{(K)} + M \frac{N}{K})$.So on setting $K = \sqrt{N}$, your complexity is $O(N \cdot \sqrt{N} \cdot \log{(N)} + M \cdot \sqrt{N})$.Now you can improve the part of your solution which is contributing $N \cdot K \cdot \log{(K)}$. Instead of iterating over all numbers from $1$ to $K$, just iterative over all factors of $N-j$ which are smaller than $K$. This improves the constant factor.Here's my submission. I obtained a runtime around $1150$ ms by setting $K=500$.Edit: On putting $K=1000$, my submission runs in $826$ ms.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 You're right — thank you!I thought the bottleneck was the query part of the program because I had analysed the complexity incorrectly. Constant factor optimising by iterating over smaller factors sounds like a good idea.Also, I believe you you meant to write $O(N \sqrt{N} \log_2{(\sqrt{N})} + M \sqrt{N})$ instead of $O(N \sqrt{N} \log_2{(N)} + M \sqrt{N})$.
•  » » » » 5 months ago, # ^ |   +8 It was intentional as $O(log(\sqrt{N})=O(log{N})$ :p
•  » » » 2 months ago, # ^ |   0 Can you explain your approach folks ? I understand the concept that you use , but it's still kinda hard to read
•  » » 5 months ago, # ^ |   0 I solved it in $O(N log_2(N) + NK)$ this is my solution
 » 5 months ago, # |   0 Very good round, hope more. -w-
 » 5 months ago, # |   0 In the editorial of E: Then everything to the left of is is non-increasing. Everything to the right of it is non-increasing. Shouldn't it be "Then everything to the left of it is non-decreasing"?
•  » » 5 months ago, # ^ |   0 It's kinda non-increasing if you look at it from the maximum outwards. I meant to show that both parts behave the same.
•  » » » 5 months ago, # ^ |   0 I see. Thanks!
 » 5 months ago, # | ← Rev. 2 →   0 Can anyone please explain the solution to problem D? Why the question is of DP and not greedy?
•  » » 5 months ago, # ^ |   0 I solve it greedy in O(n) : if string s writing as s1 + s2 + s3 and s1,s3 is palindrome and s2[i]==s2[i+1] for any i :i is even then it is a draw else Alice win example string s=abbcca ,s=abeerrba ,s=abccba ,s=aabbcc here it is a draw here my submission :https://codeforces.com/contest/1728/submission/171626668but I suggest to solve it using DP suppose we have string of length n : s[l],s[l+1],,,,,,,,s[r-1],s[r] we have four cases : p1 : Alice choose s[l] and Bob choose s[l+1] ,p1=solve(l+2,r) if p1==0 then you need to compare s[l] , s[l+1]p2 : Alice choose s[l] and Bob choose s[r] ,p2=solve(l+1,r-1) if p2==0 then you need to compare s[l] , s[r] p3 : Alice choose s[r] and Bob choose s[l] ,p3=solve(l+1,r-1) if p3==0 then you need to compare s[r] , s[l]p4 : Alice choose s[r] and Bob choose s[r-1] ,p4=solve(l,r-2) if p4==0 then you need to compare s[r] , s[r-1]then the ans[l][r] = max(min(p1,p2),min(p3,p4)) you should calculate any substring with length 2 before here my submission using DP : https://codeforces.com/contest/1728/submission/171633331
•  » » » 5 months ago, # ^ |   0 Understood it thanks!
 » 5 months ago, # |   0 Suppose Problem D also asked to print the two optimal strings that the players will select, how do we proceed then?
•  » » 5 months ago, # ^ |   +8 You can build the same dp table as before, except in each entry, you also write down which indices $\ell$ and $r$ the dp value was copied from. The implementation gets a lot more annoying, but it's ultimately doing the same thing. After that, once the table is filled up, you can construct Alice's and Bob's strings by going backwards on the dp table. Start with $dp[0][n]$, check whether the value came from $dp[1][n]$ or $dp[0][n - 1]$, add the appropriate character to the Alice string, and then go to that corresponding entry. Use the same process to add the appropriate character to the Bob string, and so on, until the string has no characters left.
 » 5 months ago, # |   0 someone please make a video tutorial for D — Letter Picking... or if there is one then please point me towards it.
•  » » 5 months ago, # ^ |   0 Video Solution for Problem D.
•  » » » 5 months ago, # ^ |   0 thank you so much
 » 5 months ago, # | ← Rev. 2 →   0 Could someone explaine a D problem case "baab": Alice can pick only "b", then Bob picks "a". So "a.." < "b.." anyway. So Bob wins, but the solution contradicts this?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 Since the letters are being prepended to the player's strings, if Alice chooses 'b' and then Bob chooses 'a', Alice will chose the other 'a' forcing Bob to take 'b' resulting in these strings below which makes Alice win:Alice : "ab"Bob : "ba"So Bob also chooses "b" in his first chance and in the end both have string "ab" which would result in a draw
•  » » » 5 months ago, # ^ |   0 Thank you!
 » 5 months ago, # |   +1 My solution to the C problem was hacked 171387514. Next day I resubmited the same code 171579962 and it passed all the tests. How do I understand my solution basicaly is correct or not? I thought that the hachs are added to tests. Could someone clarify this please? (It's not neccesary to check my code, just explain how the system works)
 » 5 months ago, # |   0 anybody with recursion solution for C
 » 5 months ago, # | ← Rev. 4 →   +10 Some clarifications on the tutorial for 1728G - Illumination SpoilerIt may be easier to think of the submask multiplying step as first sorting the points-of-interest by distance from the current lantern, keeping indices and breaking ties arbitrarily. Then over the points of interest we are multiplying the mask patterns (bits shown in ascending distance from left to right) 1*****, 01****, 001***, etc.A zero in the mask pattern doesn't mean "illuminated", it means "may or may not be illuminated", while a one means "definitely not illuminated". We use the zeros because we have already accounted for those masks when iterating over the previous points of interest. This also handily explains why the editorial and model solution uses $\lt d$ on one side but $\le d$ on the other to decide where to assign zeros, the important thing is that ties are broken somehow.
 » 5 months ago, # |   0 For question D:-171677046 simple o(n^2) solution using min-max We need to observe the fact that since Alice is going first therefore either Alice can win or it will be a draw. 1 means Alice wins and 0 means it is a draw. Also remember, (0|1)=1(bitwise or). I approached it considering all the possibilities when Alice is at [l,r]. It can follow with either Alice choosing s[l] or s[r]. dp[l][r] denotes who will win after considering substring s[l,l+1.....r]. If Alice chooses s[l] then Bob will choose either s[l+1] or s[r]. So, dp[l][r]=min((s[l]> &dp,int l, int r,string &s){ if(l>r) return 0; if(dp[l][r]!=2) return dp[l][r]; int ans1=find(dp,l+2,r,s),ans2=find(dp,l,r-2,s),ans3=find(dp,l+1,r-1,s); dp[l][r]=max(min(ans1|(s[l]>s; n=s.size(); vector> dp(n,vector(n,2)); //initialiazation int ans=find(dp,0,n-1,s); if(ans==1) cout<<"Alice\n"; else cout<<"Draw\n"; return; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t=1; cin>>t; while(t--){ solve(); } return 0; } 
 » 5 months ago, # | ← Rev. 2 →   0 Why am I getting TLE in Problem C?It seems like a O(n) solution. #include using namespace std; int calc(int k){ return to_string(k).size(); } int solve(){ int i,j=0,n,z,c=0,one=0; cin>>n; vector b(n); unordered_map mp; for(i=0;i>z; mp[z]++; } for(i=0;i>z; if(mp[z]!=0){ mp[z]--; } else{ if(z>9){ b[j]=calc(z); c++; } else b[j]=z; j++; } } if(j==0) return c; unordered_map mp1; for(auto [x,y]:mp){ if(y==0) continue; if(x>9){ c+=y; mp1[calc(x)]+=y; } else mp1[x]+=y; } z=0; for(i=0;i>t; while(t--){ cout<
•  » » 5 months ago, # ^ |   0 Use map instead of unordered_map
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 You are right. But, can you explain the reason?
•  » » » » 5 months ago, # ^ |   +3 Worst case Time Complexity of operations in case of unordered_map is O(n). For map, it is O(log n)
•  » » » » 5 months ago, # ^ |   +4 https://codeforces.com/blog/entry/62393 read this :)
•  » » » » » 5 months ago, # ^ |   +1 @aggressor_ thank you very much. It was helpful
•  » » » » » » 5 months ago, # ^ |   0 you're welcome!
 » 5 months ago, # |   0 In the solution for D. Letter Picking in the code inside the two for loops after these lines int r = l + len; dp[l][r] = 1; { why this brackets is used, these are used after for loop while loop if statements but what work these brackets are doing here in this code , I am unable to understand it
•  » » 5 months ago, # ^ |   0 They do nothing except for separating parts of the code.
 » 5 months ago, # |   +8 For problem G,why not DP?Dp from l1 to ln,only the leftmost unilluminated interest is useful,and we can do it similarly from ln to l1.
 » 5 months ago, # |   0 1728C — Digital Logarithm Can be done in O(N) with HashMap.
 » 5 months ago, # |   0 Nice Tutorials :)
 » 5 months ago, # |   0 Did anyone solve problem D with memoization?I'm very used to throwing a memo table in a recursive function and not worrying about coming up with a bottom-up DP approach (like the one in the solution) but it doesn't seem to work for me in this problem.
•  » » 5 months ago, # ^ |   0 1728D - Letter Picking Finally figured it out if anyone is interested in a memoization solution. 172506863 I had difficulty making my recursive function in a way that dp[l][r] had the result for the optimal play for the string from position l (inclusive) to position r (inclusive). I first tried a classic minimax approach but the problem was that the same position [Sl, Sr] was being reached many times and each time the result was different due to the fact that Alice and Bob had previously made different selections and my function was naive.Here is the minimax approach without dp that is correct with exponential time complexity. 171427579 and here is the same approach with memoization which is wrong. 171428537Very interesting problem, I learned a lot!
 » 5 months ago, # | ← Rev. 2 →   +5 Alternate solution for G using binary search and inclusion-exlusion -(POI = point of interest)Accepted Solution Sort lanterns and POIs by coordinate For each mask, calculate the number of ways that at least all the POIs whose bits are set are unlit(eg. for mask 101001, POI 0, 2 and 5 should be unlit, rest can be whatever)To do this, you binary search for leftmost lanterns which have each POI in the mask as their closest, if lanterns $l_a$ through $l_b$ have $p_i$ as the closest POI, then multiply number of ways for that mask by $|p_i - l_a|*|p_i - l_{a+1}|*...*|p_i - l_b|$, let's call this $ways_{mask}$ For each mask, find the number of ways that exactly all the POIs whose bits are set are unlitYou can do this using inclusion-exclusion, let's call this $ways_{mask}'$, then $ways_{mask}' = [\Pi_m ways_m*(-1^{popcnt(m)+popcnt(mask)})]$ where $m$ & $mask = mask$ With $ways_{mask}'$ computed, we can move to answering the queries -Let the new lantern be at $pos$ For each POI, calculate distance from $pos$ and sort them in decreasing order, let's say the distances are $[4, 2, 1]$ for POIs $[2,0,1]$, then we calculate the sum of $ways_{mask}'$ where mask contains bit no. 2, for all these masks, if the new lantern has a brightness of 3 or less, all POIs are still not lit. Next we calculate the sum for masks where mask contains bit no. 0 but not bit no. 2, for all these masks, if the new lantern has a brightness of 1 or less, all POIs are not lit. We continue this procedure m times, giving us the final number of ways in which the POIs are not fully illuminatedFor sum of $ways_{mask}'$ and for calculating $ways_{mask}'$ in the first place, you would need to use SOS DP Final time Complexity — $O(m*2^m*log(n) + q*m*log(m))$
 » 4 months ago, # |   0 For the tutorial on Problem E — since we're checking how many dishes with black peppers we are going to include in our answer, it should say "Then we would want to check the answer for b*y black peppers" Right ?Great problem and editorial btw. (y)
 » 3 months ago, # |   0 Is Test Case 13 for Problem 1728C — Digital Logarithm a Hash Hack?I submitted my code for it using unordered_map and it got a TLE. 181042311But as I changed it to map it got AC. 181042409.I think it is a Hash Hack but I am not sure.