### awoo's blog

By awoo, history, 3 years ago, translation,

1093A - Dice Rolling

Tutorial
Solution (Vovuh)

1093B - Letters Rearranging

Tutorial
Solution (Vovuh)

1093C - Mishka and the Last Exam

Tutorial
Solution (PikMike)
Naive (PikMike)

1093D - Beautiful Graph

Tutorial
Solution (Ajosteen)

1093E - Intersection of Permutations

Tutorial
Solution (PikMike)

1093F - Vasya and Array

Tutorial
Solution (Ajosteen)

1093G - Multidimensional Queries

Tutorial
Solution (BledDest)
Solution (PikMike)

• +55

 » 3 years ago, # |   0 Can someone link this editorial to the contest materials?
•  » » 3 years ago, # ^ |   +1 Done
 » 3 years ago, # |   +1 Can someone explain the Intersection of Permutations editorial in more detail?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 You can read about 2D-BIT at topcoder.The idea about offline trick comes from the treap implementation. With treap you would do something like: for each BIT x in query sum up the amount of numbers which are less than or equal to y. Imagine processing the same thing with BIT. At first glance it seems like you would need to do operations "add 1 in y" and "get prefix sum up to y". However, you don't need all the points up to max coordinate. You can compress the numbers in each BIT and find needed position with binary search.
•  » » » 3 years ago, # ^ |   0 thanks.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » 2 years ago, # ^ |   0 awoo I have solved D with dp and am very proud of myself as it took me 2 hours to figure out the dp state . Here is my submission 51760005Don't downvote just wanted to share another approach. If there is any component which is not bipartite then the answer is 0 as it means graph contains a cycle of odd length and we can never satisfy the condition otherwise I stored in dp[i] the number of ways when we put 1 in ith vertex , 2 in ith vertex , and 3 in ith vertex .
•  » » » » 2 years ago, # ^ |   0 Yeah that's awesome. Here's another dp solution 55659665
 » 3 years ago, # |   0 Can anybody help me why I m getting Runtime Error On Test Case 9 in The Most Discussed Beautiful Graph Problem My solution.
•  » » 3 years ago, # ^ |   +5 You have set N = 10^5, but it can be 3 x 10^5. :)
 » 3 years ago, # |   0 Could someone tell me why I got TLE in problem D? Here's my submission. Thanks a lot!
•  » » 3 years ago, # ^ |   +1 Number of test cases = 3e5, and for each test case you memset the whole colour array and first array, which are also 3e5.It is stated that it is guaranteed that summation N over all test cases doesnt exceed 3e5, so for each test you should manually loop on array 0->n and clear it yourself, which gives a total accepted complexity of 3e5 over all test cases.Here is your 47162894 updated :D
•  » » » 3 years ago, # ^ |   0 Thank you for your detailed explanation, which helped me a lot :D
•  » » » » 3 years ago, # ^ |   +1 Its okay :D, I also got time limit for this reason in the contest :(
 » 3 years ago, # | ← Rev. 2 →   0 It's giving me runtime error on Scanner Class.https://codeforces.com/contest/1093/submission/47155880Every time I got stuck with this scanner shit.Please give me any alternative.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 The only reason i can think of is u have used 2 Scanner objects to scan from same source.I think this is ur solution
 » 3 years ago, # | ← Rev. 2 →   -8 Is there a recursive(with memoization) implementation of Problem F? I didn't fully get the editorial.
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 You can code it recursively but it won't look easier. I can tell you my more straightforward approach.Let it be the same dp and sdp definitions. Now you want to update dp[i][lst] by making the last segment of value lst. That means that there is some position prv, where the segment of maximum length of value lst could start (this length is found with len and position of the rightmost element not equal to  - 1 or lst.Thus you want to sum up all the dp[j][l] for j = prv... i - 1 and l = 1... k, that is sdp[j]. However, the previous segment couldn't end with lst, subtract dp[j][lst].Add a little bit of maintaining partial sums over both dp and sdp arrays and you'll get the same complexity. Code
 » 3 years ago, # |   0 Thanks for your fast Editorials
 » 3 years ago, # |   0 Can anyone explain to me why problem F's solution is right?
 » 3 years ago, # |   0 Can someone explain the reason behind solving 2^a+2^b in problem D ?
•  » » 3 years ago, # ^ |   +1 The last sentence explains it? If the graph is bipartite then the only coloring exists (color vertices of the first partition white and the second is black). White is one of {1, 3}, black is {2}. That is 2size colorings. And then change white to {2} and black to {1, 3}.
•  » » » 3 years ago, # ^ |   0 Hard to Understand the solution of D. What have changed if there were only two numbers 1 and 2(not 3).Please explain the reason for 2^a + 2^b .
•  » » » » 3 years ago, # ^ |   +1 1 and 3 are the same in terms of making pairs. So you can put either 1 or 3 on each vertex, that is 2 options. Thus it's 2size. With only 1 and 2 you'll have a single option for each vertex, it would be just 1.
•  » » » » » 3 years ago, # ^ |   0 Then why, 2^size for both parts. By your explanation it should be 2^a for one part(1,3) and simply 1 for another part(2).Can also you explain why res = res * cur for each iteration on Node in Code.
•  » » » » » » 3 years ago, # ^ |   +1 It is 2a for part {1, 3} and 1 for part {2}. But then you swap parts and color the first part {2} and the second part {1, 3}.
•  » » » » » » » 3 years ago, # ^ |   0 Thanks, I understood it clearly. Can you explain why res = res * cur for each iteration.
•  » » » » » » 3 years ago, # ^ |   0 The colorings on each connected component are independent, so we multiply their answers.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Actually, it's (2^odd*1^even)+(1^odd*2^even), I understood it this way which was easier.
 » 3 years ago, # |   0 Can someone help me out with my code? I did exactly what is mentioned in the tutorial however couldn't pass the second pretest during the contest. Here is the link to my code: https://ideone.com/jWlp4l
•  » » 3 years ago, # ^ |   +1 Shouldn't fl be the other way around? The answer is 0 if at least one connected component isn't bipartite.
•  » » » 3 years ago, # ^ |   0 Oh! Didn't take care of that. Thanks, it worked by changing fl the other way round. Was a little bit confused.
 » 3 years ago, # |   0 Can someone help me out with my code? It kept getting Runtime Error on Test Case 10 in problem E. I'm using persistent segment tree and I can't find anything wrong with it. Here is my code. Thank you so much if you could help me figure out the problem.
 » 3 years ago, # |   +9 Another approach for problem F:Let dp[i][j][k] : the number of ways of fill the firsts i elements where j is the last element and appear k times, this is O(N * K * N) in memory, but only need dpi - 1 for update dpi so the memory become O(N * K).Looking what happen into the transition when a element x come? There is two cases:x ≠  - 1: how the element is fixed dp[j][k] will be 0 except for j = x, more precisely dp[j] should be shift one position because all the ways of end with j increase by 1, and a new value should by put in dp[x][1], these value is such that l ≠ j , in other words all the ways of end with other element, and if dp[x][len] become greater that 0 then make it 0, because this is a invalid array.x =  - 1: fix every possible element and do the same as for x ≠  - 1 K times.So i need something that support insert one element in the front and delete in the back, and have the sum of all of it's values, this is possible with a deque!!!Keeping K deque one for each possible element the transition can be done in O(K), and the time complexity become O(N * K).For more details of the implementation see my code: Solution47081307 #include using namespace std; typedef int ll; typedef long double ld; typedef complex point; #define F first #define S second const ll mod = 998244353; int main() { #ifdef DGC freopen("a.txt", "r", stdin); #endif ios_base::sync_with_stdio(0), cin.tie(0); int n, k, l; cin >> n >> k >> l; if (l == 1) { cout << "0\n"; return 0; } ll ts = 0, tts; vector s(k); vector> t(k); int x; cin >> x; x -= x > 0; if (x != -1) t[x].push_back(1), s[x] = 1, ++ts; else for (int i = 0; i < k; ++i) t[i].push_back(1), s[i] = 1, ++ts; auto put = [&]() { ll a = ts-s[x]; if (a < 0) a += mod; t[x].push_front(a); s[x] += a; tts += a; if (s[x] >= mod) s[x] -= mod; if (tts >= mod) tts -= mod; if (t[x].size() == l) { s[x] -= t[x].back(); tts -= t[x].back(); if (s[x] < 0) s[x] += mod; if (tts < 0) tts += mod; t[x].pop_back(); } }; for (int i = 1; i < n; ++i) { cin >> x; x -= x > 0; if (x != -1) { tts = ts; put(); ts = tts; for (int j = 0; j < k; ++j) if (j != x) { t[j].clear(); ts -= s[j]; if (ts < 0) ts += mod; s[j] = 0; } } else { tts = ts; for (x = 0; x < k; ++x) put(); ts = tts; } } cout << ts << "\n"; return 0; } 
 » 3 years ago, # |   -7 Can someone explain me, In the F problem.. Why are we subtracting dp(cnt-len,lst) as well and not only sdp(cnt-len). Thank you.
•  » » 3 years ago, # ^ |   +1 If you don't connect new correct segment of color lst with some previous one then you'll never break any conditions. And if optimal answer has these segments merged then you'll still visit this state.
•  » » » 3 years ago, # ^ |   -11 Where does this color come from? Are you saying that gray is much far from Red? :P
 » 3 years ago, # |   0 For Problem F... I still can not understand why the number of the bad status is sdpcnt - len-dpcnt - len, lst,can you explain it more specifically?Thx...
 » 3 years ago, # |   0 Hi everyone,Just wanted to say that this was my 1st rated competition on Codeforces and I am really enjoying the learning process. Also wanted to mention that everyone in the comment section are quite helpful and give constructive feedback, so thank you :) !
 » 3 years ago, # |   0 From what I understand, the soln for G will NOT work if the queries is asking for minimum distance, right? Is there some other way to solve it if the problem asks for minimum?
 » 3 years ago, # |   0 if((col[v] ^ col[to]) == 0) bad = true; anyone please explain the working of the statement from the editorial of BEAUTIFUL GRAPH??
•  » » 3 years ago, # ^ |   0 If two neighbor vertices have numbers 2 or {1,3} both then sum would become even. So it's checking this only. Like col[1]=1 and col[2]=1 then col[1]^col[2]=0.
 » 3 years ago, # |   0 Any one can help me with graph problem. I have no idea how to get started
 » 3 years ago, # |   0 can any one help me figure out why my submission is failing on test-case number 10 (for beautiful graph problem) https://codeforces.com/contest/1093/submission/47175967
 » 3 years ago, # |   0 Can please anyone explain me problem E editorial here, I am unable to get it even after reading the editorial. Please share any other approach if you have got. Thanks a lot, Problem Link...
 » 3 years ago, # | ← Rev. 2 →   0 For problem E, I don't understand what the tutorial is talking about. What is "update in point and sum on rectangle"? And how exactly are we remunerating the numbers?Edit: Finally got it, I was imagining you meant reordering rather than renumbering. So for example if a = [5, 1, 4, 2, 3, 6] b = [2, 5, 3, 1, 4, 6] then the new b should be [4, 1, 5, 2, 3, 6], changing each number in b to the position of the corresponding element in a. So the first element in b becomes 4 because the index of 2 in a is 4.
 » 3 years ago, # |   +19 Despite what they said in the editorial sqrt decomposition is fast enough to pass E. General idea split a and b into chunks. Each chunk of b has a segment tree that keeps track of how terms the chunk has in common with all other chucks of a. Updates take , since you have to update at most four segment trees. For the other type of query you brute force part of the query so you only have to deal with intersections between whole chunks of a and whole chunks of b. Then for each chunk of b contained in the query you use the segment tree to find the number of terms it has in common with all chunks of a contained in the query. Worst case complexity for queries is . Final complexity , and yes this is fast enough to pass. My code 47287195.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I used a similar sqrt-decomposition technique with BIT. One important thing to note is block size you choose can have a big impact on your runtime. For my implementation, I was updating the BITs for each block frequently, so it was advantageous for me to choose a larger block size. With a block size of , I was able to get it to run under 2000 ms, faster than the official soln. 47315299
•  » » » 3 years ago, # ^ |   +3 That makes sense to use a larger block size. It seems like the trade off is between how far you travel to get to the ends and starts of blocks in the brute force part which favours a smaller block size and how many blocks you have to iterate over in the segment tree/BIT query part which favours a larger block size. The second part is more costly because there is an extra log factor when you do the queries. I suspect you could use calculus to figure out the optimal block size. For my implementation a block size is much slower (3931 ms) than (2558 ms). The best block size that I have found for my implementation is it gets (1825 ms) 47317374. It is interesting how a similar sqrt-decomposition approach can have such different optimal block sizes.
 » 3 years ago, # | ← Rev. 2 →   0 Problem D Can someone help me? My solution is giving TLE on test case 13 https://codeforces.com/contest/1093/submission/47291028
 » 3 years ago, # |   0 1093Ahttps://codeforces.com/contest/1093/submission/47239530Why was this solution not accepted? Can somebody help?
•  » » 2 years ago, # ^ |   0 plz the read all the information on your soultion page. it says your ans is wrong for xi = 36
•  » » » 2 years ago, # ^ |   0 Thanks. Got it. Reversing the loop solves the problem.
 » 2 years ago, # | ← Rev. 2 →   0 nice questions...
 » 2 years ago, # |   0 Anybody please explain why 2^a+2^b work in problem 1093D — Beautiful Graph.I need mathematical proof.Please help
•  » » 2 years ago, # ^ |   0 You have two parts of size a and b, we want to proof that one of them should be totally odd and one of them should be even. We obtain this fact using induction on length of a path. We assume that vertices of this path should be like: odd,even,odd,even,... now erase the last vertex and we can apply to induction hypothesis, after that add this vertex and the erased edge. Since one of the endpoint of that edge is odd(for example), this vertex should be even. So for each two vertex in same part, they should be as same cause length of every path between them is even. Now there is two case: 1:part with a vertices be odd, we have 2^a to choose that every vertex should be 1 or 3. 2:part with b vertices be odd, we have 2^b like previous case.
•  » » » 2 years ago, # ^ |   0 Thanks you <3. i love your explanation.
 » 2 years ago, # |   0 Thanks for problem G, short and nice.
•  » » 2 years ago, # ^ |   0 Need help for problem G, from what i understand from the tutorial, we will build 2k segment tree, each tree will be based on the value of , then we will take the maximum and the minimum of each 2k and take optimal distance as the result, is this right? and how can do this since each of |ax, i - ay, i| already has their fixed ci?
 » 2 years ago, # |   0 can anyone explain me the last statement in pikmike solutions forn(mask, 1 << k) ans = max(ans, abs(bst[(1 << k) — 1 — mask] + bst[mask])); printf("%d\n", ans);
•  » » 2 years ago, # ^ |   0 In bst I have the minimum value for each mask (the values of ci of editorial). And I also know that ci will have all its signs turned if I replace 0 with 1 in mask and 1 with 0. That is the same as doing (2k - 1)^mask (or minus as I do). Thus bst[(2k - 1)^mask] will have the maximum value of mask but with multiplied by -1. I wanted to update the answer with (max - min) and I have min and ( - max). So I can do ( - ( - max) - min) or |max + min| (as I surely will have the non-negative value in a result).
•  » » » 2 years ago, # ^ |   0 all clear.
 » 2 years ago, # |   0 In tutorial for problem G, should time complexity be for the code you give? I think they are quite different.
•  » » 2 years ago, # ^ |   0 What makes you think that?
•  » » » 2 years ago, # ^ |   0 In your code, it cost you time on the segment tree and O(2k) time to modify or update bst after it for each modification or query. The time used when building the tree is O(n2k). Thus the time complexity is . To get the result , we could build 2k segment trees, and I got TLE when implementing this(my submission). Actually, the difference occurs when dealing with query and modification, one is each time and the other is , which makes me think they are quite different.
•  » » » » 2 years ago, # ^ |   0 It costs me on both update and get queries. There are loops of 2k iterations on each of these functions. I also do have 2k segment trees, it's just the traversal order that differs. I have the other submission, which does about the same as yours and it works twice as slow. It seems, you should consider the time spent jumping around in memory while implementing it.
•  » » » » » 2 years ago, # ^ |   0 I got it. Thanks for your explanation and sorry to take up your time.
 » 2 years ago, # |   0 While I (somewhat) understand how the solution to problem E works, and I've also read the article on Topcoder (about BIT, and another about RMQ),I really don't understand how to come up with such a solution , the rectangle method seems quite non-intuitive .... can someone give any suggestions on this based on their own experience ?Thanks a lot !
•  » » 2 years ago, # ^ |   +3 To be fair, problems of kind "answer something on a segment" don't come in lots of different forms. Like all of them are divided into: precalculate something on prefix segment tree Mo This problem clearly doesn't fit into Mo category, prefix is also kinda weird here. Thus is probably segment tree or some other online structure.And there is another common trick. When you have several synchonized permutations but the exact values on them doesn't matter, you can renumerate one of them to identity permutation. I personally met this technique quite a few times.
•  » » » 2 years ago, # ^ |   0 Hi PikMike,Thank you for taking out the time to answer my question.Could you kindly clarify what you mean when you say "renumerate one of them" ? Do you mean getting rid of one of the permutations by finding a common property of the elements of the permutation (like in this question we reduce 2 permutation arrays to a single array by representing each number as a coordinate) ?
•  » » » » 2 years ago, # ^ |   +4 Yeah, essentially it is getting rid of one permutation. In some cases you can just abandon this one, in some you will still need it (but at least in will be 1, 2, ..., n). The latest problem on this trick I remember should be 1043D - Mysterious Crime.
•  » » » » » 2 years ago, # ^ |   0 Thanks for your replhy ... also, it was an interesting question so thank you for the problem as well.
 » 2 years ago, # |   0 Need help for problem G, from what i understand from the tutorial, we will build 2k segment tree, each tree will be based on the value of , then we will take the maximum and the minimum of each 2k and take optimal distance as the result, is this right? and how can do this since each of |ax, i - ay, i| already has their fixed ci?
•  » » 2 years ago, # ^ |   0 You don't take arbitrary ci but the opposing ones. Take the easiest case — point x is larger on each coordinate than point y. Thus, you'll need cx be all ones and cy be all minus ones. However, for any other pair of opposing in each position values of c the sum will not exceed the appropriate pair. This concludes that the right values of cx and cy will have the maximum result of all candidates. The other cases of relative positions also follow the same principle.
•  » » » 8 months ago, # ^ |   0 Hi @pikmike, i was solving october Long challenge and that has question very similar to question G . Can you please explain how we are querying the max and min in the range ??
 » 2 years ago, # |   0 I think the naive solution for Mishka and the Last Exam is not correct. It's getting TLE on the 9th test case. http://codeforces.com/contest/1093/submission/47462619 Or Should it get a TLE that's why it is the naive solution?
•  » » 2 years ago, # ^ |   0 Yeah, it's TL but much simpler logic. That's why it's called naive.
 » 2 years ago, # |   0 can someone explain PROBLEM E in easier manner? i really confused.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +3 Try reading the topcoder article and then read this on SO: https://stackoverflow.com/questions/15439233/bitusing-a-binary-indexed-treeI think the SO explanation was decent. Visualize the 1) Query operation: going backwards (from a leaf node) on the right link.2) Update operation: going backwards (from a leaf node) along left link, The solution to problem E will simply extend this to both x and y dimensions. The GeeksforGeeks article also explains this well with a diagram: https://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree/
•  » » » 2 years ago, # ^ |   +3 Thanks for the article, but what is addupd and addget for? Especially the i |= i+1 part and why do we have to sort them?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Actually even I did not understand the editorial and didn't bother to after some attempts. I wrote my own solution, and it is more straightforward compared to the editorial: https://codeforces.com/contest/1093/submission/47477762it is a direct approach taken from the articles I linked above. This solution does NOT pass after test 10 because of memory space usage but you can still read it to see how the 2D BIT is implemented (it is very easy in terms of implementation ...)The final solution that worked used a GNU PBDS "ordered set" data structure called tree (since a set can be implemented using AVL trees) ... I'm not too familiar with it but I saw some codeforces posts about it after the contest.Here is the link to the final solution: https://codeforces.com/contest/1093/submission/47479386It uses the standard BIT for the x-dimension but uses the GNU PBDS "ordered set" for the y-dimension. As you will read in other Codeforces posts about this, this solution will only work if you wish to "count" something (in this case, points inside a rectangle), since the solution uses the "index" of the item in an ordered set, which is a shortcut for finding the prefix sum if you simply have to count the number of elements before a certain element. (I found this the best way to understand the usage of the GNU PBDS ordered set.).
 » 2 years ago, # | ← Rev. 2 →   0 In problem E, square root decompsition + binary indexed tree solution is getting accepted, when block_size is fixed about 800, but getting TLE when block_size is used by sqrt(n). In both solution each update is O(4*logn) and each query is O(2*block_size + (n/block_size)*logn) and pre build is O(nlogn).So, is data set weak for problem E? Isn't it possible to create such input so that this solution can't get accepted?Accepted using block_size = 800: 47504503 TLE on test 16 using block_size = sqrt(n): 47504554**Update: ** Accepted solution runs in about 2.5 sec, when block_size is 1700.
•  » » 8 months ago, # ^ |   0 My algorithm with block_size sqrt(n)[about 500] get Accepted. 96324829. I think it's not necessary use BIT and vector is enough.
 » 2 years ago, # |   0 I keep getting TLE in D on test case 22. Can anyone tell me what's the problem? Here's my solution.
•  » » 2 years ago, # ^ |   0 u should set by hand, not memset ! With memset u get a complexity of O(N) so a total of O(N ^ 2). setting it by hand would result in a complexity of O(N) because the sum of N over all test cases is smaller than 3e5
•  » » » 2 years ago, # ^ |   0 Yes, I realized memset can be bad at times. Thank you!
 » 2 years ago, # |   0 can someone explain me Q1? Why x//2 is the solution??
 » 2 years ago, # |   0 Can someone please explain QC : Mishka and the Last Exam question! How is the greedy approach working?
 » 2 years ago, # |   0 Dice pulling sample output looks wrong...What do you think guys??
 » 2 years ago, # |   0 Can somebody help me with my code on F ? I checked myself many times with the provided code but i find nothing suspicious. I get WA on test 4 47825046
 » 2 years ago, # |   0 Please, someone, suggest me some material of how to compress numbers in a 2D BIT. I am unable to get how Editorialist of the Problem E is compressing the numbers in each BIT.
 » 2 years ago, # |   0 I am getting wrong answer in prob. D, test case 3,that is , for some cases my code is giving output 0, anybody got any ideas? Link to the code :
•  » » 2 years ago, # ^ |   0 Nevermind , I solved it :D
 » 2 years ago, # | ← Rev. 2 →   0 can someone please help in beautiful graph??dont know why i m getting wrong answer in test case3 here is my link https://codeforces.com/contest/1093/submission/49533934
 » 2 years ago, # |   0 Hello, can anyone explain to me why my code of problem "D-Beautiful Graph" is not working? I tried to make it as similar to example code as possible but still does not work. my code
 » 20 months ago, # |   0 I did the same approach as Editorial for problem D but I got wrong answer at test 3. Could anyone help me figure out what wrong with my submission 62551741
•  » » 20 months ago, # ^ |   0 I found out the bug.
•  » » » 10 months ago, # ^ |   0 what is the bug, i am getting WA in test case 3. https://codeforces.com/contest/1093/submission/91230458 this is my code, if you could highlight how you resolved the bug
•  » » » » 10 months ago, # ^ |   0 okay i replaced LONG with LONG_LONG everything worked fine then .
 » 5 weeks ago, # | ← Rev. 2 →   0 solution of A using DP 116408246