### awoo's blog

By awoo, history, 5 weeks ago, translation,

1922A - Tricky Template

Idea: Roms

Tutorial
Solution (awoo)

1922B - Forming Triangles

Idea: Roms

Tutorial
Solution (Roms)

1922C - Closest Cities

Idea: BledDest

Tutorial
Solution (Roms)

1922D - Berserk Monsters

Idea: BledDest

Tutorial
Solution (Neon)

1922E - Increasing Subsequences

Idea: Roms

Tutorial
Solution (Neon)

1922F - Replace on Segment

Idea: Roms

Tutorial
Solution (Neon)
• +116

 » 5 weeks ago, # |   +43 If using a double linked list to implement 1922D, we can get a solution of O(n) time.
•  » » 5 weeks ago, # ^ |   +5 I created array for storing right & left alive monster // intialization int right[n+2] , left[n+2] ; for(int i=1 ; i<=n ; i++) { right[i] = i+1 ; left[i] = i-1 ; } // after each round for(int it : died_in_round) { left[right[it]] = left[it] ; right[left[it]] = right[it] ; } 
•  » » » 5 weeks ago, # ^ |   0 I wrote a similar solution but using sets was so elegant!
•  » » 4 weeks ago, # ^ |   0 Bro I messed up and used both set and double linked list. Can you tag your solution for me to view. I just wrote a bunch of code and somehow got AC.
•  » » » 4 weeks ago, # ^ |   0 D.Berserk Monsters Codecheck it out, may be helpful.
 » 5 weeks ago, # | ← Rev. 5 →   -15 We can do 1922B - Forming Triangles without binomial coefficient. 242267553 We can assume that the three sides chosen by us are (2^x,2^(x+d1),2^(x+d1+d2)) d1, d2 ≥ 0. Our triangle must meet these conditions 2^x + 2^(x+d1) > 2^(x+d1+d2). In the other way, sum of two minimum must be greater than maximum one.
•  » » 5 weeks ago, # ^ |   0 nice
•  » » 5 weeks ago, # ^ |   0 Can you explain more about your code? I was unable to understand it.
•  » » » 5 weeks ago, # ^ |   0 that is almost same idea with the idea in editorial but it's like dp observation form of it
 » 5 weeks ago, # | ← Rev. 2 →   +24 In problem E we could also construct an increasing sequence 1, 2, 3, ..., N. We could easily see that it has S = 2^N increasing subsequences (including the empty one).If S*2 equals X, we just need to add N+1 at the end, else we need to add some values to get X-S more increasing subsequences.Notice that if we add a value 1 <= v <= N to the end of the sequence, we would get 2^(v-1) more increasing subsequences, so we just need to check each bit from MSB to LSB.Submission: 242459743
•  » » 5 weeks ago, # ^ |   0 Thanks!!!.
•  » » 5 weeks ago, # ^ |   +4 I used this method in the contest
•  » » 5 weeks ago, # ^ |   0 This was very helpful. Thank you
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I thought of the same approach. But, I am getting first test case wrong on system test 6.For 905093722480139348, your code returns:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 56 52 51 50 49 48 44 41 40 39 38 37 33 32 31 30 29 28 24 23 21 20 19 17 15 13 12 11 7 5 3The largest number is 59, so according to your logic it should be 2^59. The remaining numbers: 59 56 52 51 50 49 48 44 41 40 39 38 37 33 32 31 30 29 28 24 23 21 20 19 17 15 13 12 11 7 5 3Should be 2^(v-1), which when I calculate turns out to sum with 2^59 as 905093722480139264. What am I doing wrong?This is the code I used to test:  ll ar[] = {59,56,52 ,51,50,49,48,44,41,40,39,38,37,33,32,31,30,29,28,24,23,21,20,19,17,15,13,12,11,7,5,3}; ll sm = pow(2LL, 59); for (int i = 0; i < 32; ++i) { sm += pow(2LL, ar[i]-1); } cout << sm; My submission num (Java): 242767859
•  » » » 5 weeks ago, # ^ |   0 Change the line sm += pow(2LL, ar[i]-1); to sm += (ll)pow(2LL, ar[i]-1); and it should produce the correct result. In C++ the pow function return double typed value, adding double in that range may give some miscalculation, I don't know much about Java but it could also be the same issue.
 » 5 weeks ago, # |   0 For problem B, I got accepted in the contest, but then I woke up this morning and got Time Limit Exceeded on Test case 6? I'm so confused why did this happen. I was supposed to hit expert.
•  » » 5 weeks ago, # ^ |   0 That's because someone made this test case to hack some code and succeeded during the hack phase, and these successful hacks were added to the system tests, which were used to judge the final results.Such rules are described in this blog: https://codeforces.com/blog/entry/21496
•  » » » 5 weeks ago, # ^ |   0 oh ok, my same solution translated to java (as opposed to my original python) somehow gets accepted. i'm very confused
•  » » » » 5 weeks ago, # ^ |   0 In general,C++ is faster than java,and java is faster than Python.It has to do with the feature of each languages.
•  » » » » 5 weeks ago, # ^ |   0 hell it s*cks man same happened to me! I think its about time that codeforces set different time limits for python and c++ for questions otherwise it seems like there's no point in having multiple languages
•  » » » » » 5 weeks ago, # ^ |   0 oh yea sorry to hear! I ended up passing in python after the contest by simply not using a dictionary and instead using an array. i think it is because dictionary is only O(1) access on average so i guess that adversarial test case made all the values in the array hash to the same slot or smth. that's evil haha
•  » » » » » » 5 weeks ago, # ^ |   0 yeah true
 » 5 weeks ago, # |   +21 Problem F can also be solved in $O((n^3 \cdot x)/64))$ using bitsets: linkNote that since $x$ is at most $100$, we can simply use 128 bit integers instead of bitsets for an even better constant factor.
 » 5 weeks ago, # | ← Rev. 3 →   0 I'm very confused by the editorial for E, so I feel like sharing my own (AC) approach:First, observe that a strictly increasing array with $k$ elements will have $2^k$ increasing subsequences (including the empty subsequence), the elements to be removed can be any subset of all the elements. So for input $n$, we can find the largest power of 2 which is $\leq n$, e.g., for integer $p$ such that $2^p \leq n < 2^{p + 1}$, we can form an increasing array of $p$ elements to create $2^p$ subsequences (including the empty subsequence). But what about the remaining $n - 2^p$ subsequences? Let's say the largest power of 2 you can fit in the remaining value is $2^q$, i.e., $2^q \leq n - 2^p < 2^{q + 1}$. Initially, I considered creating a separate subarray of $q$ elements, but having to do this with every power in the worst-case (e.g., if $n = 2^{59} - 1$) would exceed the 200-length limit (and we also have to avoid double-counting the empty subsequences). Instead, however, we can generate $2^q$ new increasing subsequences by adding only one element to the end of the array: an element which is greater than the first $q$ elements of the original sequence (of $p$ elements) but smaller than the rest. The new subsequences generated involve the new element with any subset of the first $q$ elements, resulting in $2^q$ new subsequences (there are no empty subsequences here, since the new element is always included in these new subsequences).This leads to the following algorithm: for the highest power $p$ of 2 that fits (i.e., leftmost 1 bit), prepare $p$ elements in strictly increasing order. This is the primary reference sequence. Then for the next power $q$ of 2 that fits, e.g., we simply add one extra element to the end whose value is between the $q$-th and the $(q + 1)$-th element of the primary reference sequence. Repeat for each power of $q$ that fits from the remnants of the previous step.My submission: 242314370. The variable prm denotes $p$, the length of the primary sequence. I used multiples of 1000 for the primary sequence. Some of the code details overcomplicated this by considering when we might have multiple instances of the same $q$ value, but this is unnecessary with clear-headed hindsight, since we're basically just going through all the 1-bits in the binary representation from left to right. The __builtin_clz(n) function (count leading 0s) would likely have improved this, to quickly find the leftmost 1-bit each time.
•  » » 5 weeks ago, # ^ |   0 I was able to come up with something similar, but I thought there would be cases where overlaps would occur and didn't manage to come up with any way to resolve them. Your explanation provides oversight in my eyesight.
•  » » 5 weeks ago, # ^ |   0 Thanks I am stuck with the part of compressing the length of array. I might be able to do it now.
 » 5 weeks ago, # |   0 My submission to E 242474581. I got long long overflow when I had (1ll<
•  » » 5 weeks ago, # ^ |   0 use (1LL<
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Yep, I've used 1ll in my wrong submission
•  » » » » 5 weeks ago, # ^ |   0 Maybe your program may let i bigger than $64$ then it will cause an overflow. Check the variable i to fix this.
•  » » » » » 5 weeks ago, # ^ |   0 I checked it on a debugger and i=59 is where it overflowed. Also the same code where I substituted (1ll<
 » 5 weeks ago, # |   0 We can think of Problem-B in another way, we can assume that the three sides chosen by us are $(2^x, 2^{x+d_1}, 2^{x+d_1 + d_2})$ where $d_1, d_2 \geq 0$. As mentioned in editorial in order to make a degenerate triangle we want $2^x + 2^{x + d_1} > 2^{x +d_1 + d_2}$ (Sum of two minimum is greater than maximum).After simplfying above inequality we get $2^{d_1} \cdot (2^{d_2} - 1) < 1$, which is only possible when $d_2 = 0$, thus for each $a_i$ we just want to find out the number of $a_i's$ after it. As for the first side length i.e., $2^{x}$ it doesn't matter what we choose so our final answer is just $\sum_{i = 0}^{N - 1} i \cdot \text{count of}\ a_i\ \text{in range i + 1 to n - 1}$. (Note 0-indexing)Here is my submission.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Same idea but as a pure DP, without precomputed numbers count: 242489424. State is number of triangles with current element $a_i$ as longest edge.
 » 5 weeks ago, # | ← Rev. 2 →   0 why this code give wrong answer forn D question 242491110
•  » » 5 weeks ago, # ^ |   0 Okay, I understand where my code failed. Thank you.
 » 5 weeks ago, # |   +10 Can anyone please explain how tester of E could have been written so that it checks the answer in polynomial time? I can't think of one.
•  » » 5 weeks ago, # ^ |   0 let dp[i] be number of increasing subsequences ending at position i, then it's O(n^2) to check. If we use sorting+fenwick to find dp starting from the lowest value, then it's O(nlogn).
•  » » 5 weeks ago, # ^ |   0 I've written a checker for myself while solving problem E. Here's how it works: — Iterate through the sequence from left to right, and compute how many subsequences end with this index, and we store this value in a bBST — We check which numbers are less than the current one in our bBST (so to the left), and add their values up, because for each of these subsequences we can append the current number to the end — Then we store this value + 1 (because this value itself is also a valid increasing subsequence) in the bBST — Finally, we add up all elements in the bBST and add 1, because an empty one is also valid Here's my implementation: https://pastebin.com/5RFbryrk
•  » » 2 weeks ago, # ^ | ← Rev. 5 →   0 Using number of occurrences of number in every sequence and calculating all subsequences. [1,2,3,4,5] -> 2*2*2*2*2 — 1 + 1 [1,1,2,2,2,3,4,5,5] -> 3*4*2*2*3 — 1 + 1 Is this correct ? Never mind
 » 5 weeks ago, # |   0 I feel like my D should get hacked. Can someone try? submission
 » 5 weeks ago, # |   0 why is my code for problem D 242468805 getting a time limit exceeded signal ? shouldn't it be faster than this approach using sets?
•  » » 5 weeks ago, # ^ |   0 Consider the case in which only 1 monster dies every round. In that case you will iterate $(n + 1 - i)$ times in round-$i$, which makes you solution $O(n^2)$.
•  » » » 5 weeks ago, # ^ |   0 doesn't the approach provided here using tree also have to go through all the alive monsters for each of the round .Or have i misunderstood the solution provided here?
•  » » » » 5 weeks ago, # ^ |   0 They only consider monsters who can die in next round. See the use of set ncur.
 » 5 weeks ago, # | ← Rev. 3 →   0 For F, I feel like we don't need to precompute that much to eliminate cyclic dependencies. Instead, we consider two cases: ifa[l]==k: we calculatedp1[l][r][k]fromdp1[l+1][r][k] first, then calculatedp2[l][r][kk]fromdp1[l][r][k], where k!=kk. ifa[l]!=k: we calculatedp2[l][r][k]fromdp2[l+1][r][k] first, then calculatedp1[l][r][k]fromdp2[l][r][k]. My Codevector>> dp1(n, vector>(n, vector(m, INF))); vector>> dp2(n, vector>(n, vector(m, INF))); for (int len = 1; len <= n; len++) { for (int l = 0; l + len - 1 < n; l++) { int r = l + len - 1; for (int k = 0; k < m; k++) { if (len == 1) { dp1[l][r][k] = (int) (a[r] != k); dp2[l][r][k] = (int) (a[r] == k); continue; } for (int i = l; i < r; i++) { dp2[l][r][k] = min(dp2[l][r][k], dp2[l][i][k] + dp2[i + 1][r][k]); } for (int i = l; i < r; i++) { dp1[l][r][k] = min(dp1[l][r][k], dp1[l][i][k] + dp1[i + 1][r][k]); } // here are the two cases. if (a[l] == k) { dp1[l][r][k] = min(dp1[l][r][k], dp1[l + 1][r][k]); for (int kk = 0; kk < m; kk++) { if (k != kk) { dp2[l][r][kk] = min(dp2[l][r][kk], dp1[l][r][k]); } } } else { dp2[l][r][k] = min(dp2[l][r][k], dp2[l + 1][r][k]); dp1[l][r][k] = min(dp1[l][r][k], dp2[l][r][k] + 1); } } } } 
 » 5 weeks ago, # |   0 In the solution to D, what does prev(it) return in case "it" is the iterator pointing to the first element in the set?
•  » » 5 weeks ago, # ^ |   0 It points to the last element of container (here, std::set). Another example here
 » 5 weeks ago, # |   0 Wow, problem E is so creative, revolutionary and original — learned a lot about bitwise operation from that one!!!!! What inspired you to create such a ground-breaking, intuitive and simply perfect problem???.?!!!!!!
 » 5 weeks ago, # |   0 can someone explain problem D. I don't understand why the problem setter's claim is valid.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Let's assume 3 monsters i-1, i, i+1 are alive after some round R. Then monster i will be be alive even after round R+1. SpoilerBecause the neighbors of i are same before and after round R.
•  » » » 5 weeks ago, # ^ |   0 Thanks a lot! I misinterpreted the question. I thought d[i] behaves like health and gets decreased by a[i — 1] + a[i + 1] every round.
 » 5 weeks ago, # |   0 Hey, could someone explain how removeing cyclic dependencies in problem F works. Is there a general approche or can we only do this for this spezific problem. Thanks!
 » 5 weeks ago, # |   0 Can somebody explain why my solution is getting TLE'D on test 15 for problem D 242631259
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   0 In problem E, it is written that : If we add a new maximum to the end of the array, the number of increasing subsequences in the new array equals 2x (since the new element forms increasing subsequences with any other elements).I think this is not well explained. In fact, if we have x increasing sequences, there are x-1 non-empty sequences and 1 empty sequence. When we add a new maximum, there will be x new non-empty increasing sequences (x-1 from the previous sequences and 1 sequence composed only of the new element). if we count again the empty sequence, the total will be (x-1) + x + 1 = 2x.
 » 5 weeks ago, # |   0 I'm getting Memory Limit Exceeded in test 5 of Problem E, why is it so?
 » 5 weeks ago, # |   0 can anyone help me with the claim that when only the particular element is dead the suitable candidates would be its Neighbours ? in problem D
 » 5 weeks ago, # |   0 BledDest The editorial solution for D problem is a little bit wrong in the case where our i in cur is equal to 0 then the nxt and prev values give us the garbage value this is working because of the summation of the garbage values is always less than INT_MAX, but if we use long long vector to store the attack and defense value than the garbage value given will also be long long which will exceed the INT_MAX value so then it will give wrong answer. sorry for my bad English.
 » 5 weeks ago, # | ← Rev. 2 →   0 It was already mentioned, sorry.
 » 5 weeks ago, # |   0 Why somebody solve F so quickly?
•  » » 4 weeks ago, # ^ |   0 because it is a standard dp on ranges problem as long as you get the dp2 idea quickly. Their method of handling cyclic dependencies is very very unnecessary.
•  » » » 4 weeks ago, # ^ |   0 how did you handled the cyclic dependencies ? Also I dont think it is that that bad , this was my solution after I read the editorial : https://codeforces.com/contest/1922/submission/242787688As you can see the only thing I did to get rid of cyclic dependencies was adding the 2 lines of code at the beginning of the function : while(l < (n-1) and l < r and ((a[l] == value) ^ typ))l++; while(r > 0 and r > l and ((a[r] == value) ^ typ))r--; Nonetheless I am still curious about how you handled because your approach is clearly faster than mine , and I couldnt really understand your logic from your submission
 » 5 weeks ago, # |   0 I shouldn't be able to understand problem F solution, why am I? :-)
 » 4 weeks ago, # |   0 can enyone help me with this problem? I am tring to solve it using Hash in c++ but can'thttps://codeforces.com/contest/271/submission/243292259
•  » » 4 weeks ago, # ^ |   0 Bigger prime for hash gets the job done.243325452
•  » » » 4 weeks ago, # ^ |   0 Thank you!
 » 4 weeks ago, # |   0 Hello everyone, I am having some trouble with problem F. I solved it with the help of the code from Dominater069.From what I understood. He did and I copied something like: Break dp2 subproblems and calculate (OK) Break dp subproblems and calculate (OK) dp[i][j][k] can be formed by 1 extra step after dp2[i][j][k] dp2[i][j][x] can be formed by any k other than x and we need the minimum one Now the part where the part 3 and part 4 just relies on each other I want a closure of why this is not in recursion or recurance. I tried solving it like Bellmanford where if the weights stop relaxing we stop the algorithm between step 3 and 4 and it will work but it doesn't even matter. I', interested in the doesn't matter part. Can someone prove it. Thank you for reading my comment and special thanks if you can shed some light on it. Thanks everyone.
 » 4 weeks ago, # |   0 The second question was very nice problem!!
 » 4 weeks ago, # |   0 Surprised that the editorial lists an $O(n^4)$ for problem F, when it can be done in $O(n^3)$, also surprised that no one has mentioned it in the comments.243829676
 » 4 weeks ago, # | ← Rev. 2 →   0 for D: why if the neighbors of $i$-th monster are alive we don't have to check the $i$-th in the next round? Isn't it possible that the neighbors to kill it in the next round? UPD: I thought the defense (d) is being decreased each round