### awoo's blog

By awoo, history, 8 months ago, translation, 1574A - Regular Bracket Sequences

Idea: BledDest

Tutorial
Solution (BledDest)

1574B - Combinatorics Homework

Idea: BledDest

Tutorial
Solution (awoo)

1574C - Slay the Dragon

Idea: BledDest

Tutorial
Solution (Neon)

1574D - The Strongest Build

Idea: BledDest

Tutorial
Solution (awoo)

1574E - Coloring

Idea: Roms

Tutorial
Solution (Roms)

1574F - Occurrences

Idea: BledDest

Tutorial
Solution (BledDest)  Comments (90)
 » Thanks :)
 » nice editorial, love the problems, appreciate it
 » In problem E, we only have to keep track of same-colour cells with an even number of cells between them?What about differently coloured cells with an odd number of cells between them? Doesn't that force a strip of width two as well?
•  » » Same colour is just a special case like adjacent cells, mentioned to arrive to the checkerboard intuition which works both for same colour and opposite colour cases without distinguishing them.
•  » » » @maxplus can you explain Problem E. I am new to CP. Like for input 2 2 7 1 1 1 1 2 1 2 1 1 1 1 0 1 2 -1 2 1 -1 1 1 -1o/p: 3 1 0 1 2 3 6 why 1 1 1 gives 3 as o/p . Initially the matrix is empty so there are 2 ways to fill it, either 0 or 1. then the answer should be 2 right. Similarly for 2 1 -1 whey o/p is 3. 2,1 wasn't filled yet, so it can filled in 2 ways with 0 or 1.
•  » » » » When the $2 \times 2$ matrix is empty, there are actually $6$ ways to fill it such that every square will add to $2$. Here are the options: Options10 10 11 00 01 01 01 10 00 11 01 10 So when we set the cell with coordinates $(1, 1)$ we get only first $3$ options out of the above.
•  » » I guess * The row and columns containing the cells of same color with even number of cells between them; can be confusing, so you're right, it's lines containing cells that correspond to both (contradicting) checkerboard line colourings that should be tracked.
•  » » » Thanks!
•  » » OK, I implemented my own version and I think the code is a bit more self-explanatory. If anyone has trouble understanding Roms' implementation (as I did), then maybe looking at mine (129556708) will help.
 » 8 months ago, # | ← Rev. 3 →   .
 » Problem E. What is cntx[] in Roms's solution and why are we (--res) only if it [0,1] or [1,0]. Shouldn't we always (--res) because same starting position shared between p2[n-ur] and p2[m-uc]?
•  » » cntx to the whole board as cntr to a row. If there is at least one strip, there are no colourings alternating nicely both vertically and horizontally so none are subtracted, and if no cells are coloured then there are two "shared" colourings.
•  » » » Thank you. Got it: cntr and cntc keep parity info for each col and row. While cntx keep parity for all board — how many of them correspond to their (virtual) color and how many doesn't. But what information does it provide us — why should we (--res) in case all {correspond} or all {notcorrespond}? It tells us if there can be shared state in the start — the position from which we can shift either vertical lines or horizontal. If there points in both {correspond} and {notcorrespond} positions — there cannot be such common starting position.
 » Is there a way of solving problem D with a trie?
•  » » 8 months ago, # ^ | ← Rev. 3 →   Yes, I solved D with Trie and DP (unfortunately I couldn't complete it during the contest). Here is the codeThe idea is put all the banned set into a trie. Then iterate through every possible prefixes. For each prefix, we will find the maximum possible suffix so that they will not form a banned set. For example we have a prefix of length $i$, there are 6 items for slot $i + 1$, current node has 3 children numbered $3$, $5$, $6$. So we may choose $4th$ item for slot $i + 1$ and choose whatever we want from slot $i + 2$The idea is simple but one should be careful while implement
•  » » As far as I can tell, I think I did it using a traverse of a trie structure without the structure itself. Take a look at my solution if you want to.129399828
•  » » you can check my implementation
 » I saw everyone using PriorityQueue for D, can anyone explain that approach.
•  » » People used a funky priority_queue based Dijkstra implementation! A very clever approach in my opinion.Each vertex is a build and each build is a vertex. However, these vertices aren't stored anywhere in memory but rather, they are procedurally generated. Two vertices (builds) are joined by an edge if and only if you get one of the builds by degrading exactly one item in the other build.Then, just implement a Dijkstra on these builds and remember to skip the neighbours of a vertex if the vertex is not banned, since the neighbours (degraded builds) can only be worse, as noted in the editorial.
•  » » The idea is basically to store the build in the priority queue, and we use custom comparator so that builds in PQ are sorted according to their total strength. We add the strongest build first to the PQ (in this case, the last item in each slot). When PQ is not empty, check if its top is not banned, if so then we get the answer. Otherwise we iteratively swap an item in some slot for the one that is the previous one by power and add to PQ.
•  » » » Got it... very clean.
•  » » » Thanks, I saw your solution and I must say it was very clear...
•  » » » very well articulated
•  » » » I have implemented the same algorithm as yours but i am getting TLE in java. Any suggestions for better complexity? I did a similar one using dfs in java, it worked. But funky dijkstras based one(same as yours) is getting TLE on T15. Please check my submission: https://codeforces.com/contest/1574/submission/129776871
 » In D part,i did simple brute force approach with some sort of memorization. But to my extreme surprise the code got accepted.129377465By the way one of the best contest for me. This contest boosted my rating to a great extent.
•  » » 8 months ago, # ^ | ← Rev. 2 →   lol its giving TLE for me though. My submission : https://codeforces.com/contest/1574/submission/129585401. Update : yeah i got it why im getting TLE
•  » » » What was the reason for TLE in your case?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   for (; max[ind]>=0; --max[ind]) { solve(ind+1, max, pos, set); } this loop makes the worst case complexity to O(10^(5n)).
•  » » » » » I'm also getting TLE #6, but I haven't found the issue. Here's my code
•  » » » » » » Oh, sorry man, I cant understand the operations which u have made since I dont know Java that much!!
 » great short approach for D
 » Can somebody please explain why we do if (ur.size() == 0 && uc.size() == 0) res = sum(sum(p2[n], p2[m]), -2); and if (cntx == 0 || cntx == 0) res = sum(res, -1); in E? Thanks in advance.
•  » » 8 months ago, # ^ | ← Rev. 2 →   I do not understand what the variable names mean exactly but based on what I've written in my solution, the first bit of code should be the embodiment of the following train of thought: if there are no forced stripes (horizontal or vertical) and no rows or columns have any cell coloured in them (they are not set in place) then the possible number of colourings is: Assume there are horizontal stripes, that gives 2^n different colourings. Assume there are vertical stripes, that gives 2^m different colourings. But the two cases above share two colourings, which is the checkerboard pattern and the anti-checkerboard pattern, which have to be subtracted from the total. The second bit of code I couldn't decipher, but it's likely something similar.
•  » » 8 months ago, # ^ | ← Rev. 4 →   ur == used in rows; uc == used in columns. It keeps indexes of rows and columns that already used — ones that have 1's and 0's written in one of their cell.Now every possible permutation can be achieved in one of two ways: either by left-right shift/move of horizontal lines or by up-down shift/move of vertical line. And every shift is creating doubled-lines in that direction — except starting position end ending. They are identical (if we consider starting position — a permutation that looks like a chessboard, and ending position — 2^n or 2^m positions, when all rows or all columns are shifted (inverted chessboard)). This means that every vertical shift creates position unachievable by horizontal shift and vice versa. Except starting and ending positions — if we shift non vert (or all vert) — thay will be the same like if we would shift non (or all) horizontal. If both of ur and uc them is empty — we haven't written any numbers — both starting and ending positions are achievable, so we should substruct 2. If there at least one cell with written 1 or 0 — we wouldn't have same starting and ending position. We could maximum have only one of those 2 positions — corresponding to written number and its cell.cntx is variable that keeps count of 'parity'. If you'll imagine an m*n chess board with black square in upper left corner (that is {1,1} coordinate), than you can say that cntx is counting how many 0s you placed on black cell and 1s on whites. cntx is counting how many 0s you placed on white and 1s on black. If there some 1s (or 0s) on both black and whites — there cannot be same starting and ending position. We should not decrease result by on. But if all 1's are on same color and all 0s on other — there could be match for one position — this position is both contained in sum(res, p2[m — uc.size()]) and sum(res, p2[n — ur.size()]), so we should substruct it.
•  » » » Sorry for asking noob question. I still don't understand why the total permutation is 2^n+2^m-2 (like the way to count up to a total of 2^n+2^m, then subtract 2 cases that is identical). Could you please explain in more detail with example.Now every possible permutation can be achieved in one of two ways: either by left-right shift/move of horizontal lines or by up-down shift/move of vertical line. And every shift is creating doubled-lines in that direction Thank you.
•  » » » » I don't know what to add. If you imagine a chess board of m*n — any permutation is achievable either by moving some horizontal "zebra-lines" 1 square left (or right — it doesn't matter, they are indistinguishable) OR by moving some vertical "zebra-lines" 1 square up (or down — doesn't matter). There 2^n variants of horizontal shifts — each line either shifted or not. And 2^m verticals — same logic.If you observe 2^n horizontal shifting — there 1 "starting" position when none is shifted, and one "ending" position — when all shifted and chess board becomes inverted — they correspond to "starting" and "ending" position in 2^m vertical shifts. So those 2 should be substructed.Case with cntx and -1 is much more interesting :)
 » Problem D please help! Can someone explain me this statement, "The optimal answer can be one of only two types. Either it contains the last item of each slot. Or it's some banned build with one item swapped with the previous one.I couldn't understand the 2nd part how the answer can be part of banned build with one swapped with previous one ?? Thanks in advance
•  » » Suppose (b1,b2,b3,...bs) is a banned build.Then one of our possible candidate for the best possible build is (b1,b2,...bi-1,...bs), given bi>1.This build is adjacent to one of our banned build so if not banned too will be a potential candidate.
 » 8 months ago, # | ← Rev. 6 →   I actually used $BFS$ to solve problem $D$. This might not be the fastest solution to implement, but I think it's easy to understand. Here's my idea. The state of the $BFS$ is the array $b$, which is the index of items chosen on each slot. The value of the state is the sum of the chosen items. We start with all index maxed out for each slot and manually calculate the sum of all the last index as the value. Every time we transition to another state, we decrease one of the $b[i]$ by $1$, iterating $i$ from $1$ to $n$. Thus, the value would only be affected by one of the slot. To maintain the value, we need to remove the previous value and add the current value, i.e. the value would decrease by $a[i][b[i]]-a[i][b[i]-1]$ ($b[i]$ here is before we decrease by $1$). By using $BFS$, we will get the states in descending order without skipping any states. We should use max heap for the $BFS$ because we prioritize the higher sum. We would stop when the current state is not banned and output it as the answer.Complexity Analysis: Since we would directly stop when it is not banned, the number of states visited would only be $O(M)$ at most. Since we use a priority queue and assuming we check a visited state using set/map, the complexity would be $O(N^2MlogNM)$.My code: https://codeforces.com/contest/1574/submission/129387703 (Note that I used a slightly different value definition, which is the difference of the current sum with the maximum sum, but the main idea is still the same)Edit: I miscalculated the complexity. Big thanks to maxplus for pointing this out.
•  » » Thank you so much, I was having the same approach but I was struggling very much implementing , you makes it looks so simple
•  » » » Glad to help!
•  » » » » Sorry just wanna ask, I'm wondering why "Glad to help!" got so many downvotes. Is it insulting or negative in any way?
•  » » 8 months ago, # ^ | ← Rev. 2 →   Isn't it $O(N^2 M log N M)$? Although at most $M + 1$ states are extracted from priority queue, for each of them $O(N)$ children are processed in $O(N log N M)$ each.
•  » » » I see, my bad I think you're right, sorry I will fix that.
•  » » » I am thinking perhaps one could improve this solution's complexity by using hashing perhaps? Although in this problem, the N is small so it still passes the time limit.
•  » » » » With hashing we'll process each child in $O(N)$ since worst case we need to create each of them, so $O(N^2M + NMlogNM)$ (in your solution you'll need to provide pq with a custom comparator so that it can ignore state). $N^2M$ is hard to shake off because it's also the space complexity independent of lookup algorithm. Instead of hashing we could visit children in such a way that each gets exactly one parent — we can stop generating children after we encounter the first not maxed slot, same complexity.If we use hashing, replace priority queue with queue, update best answer instead of terminating on the first not banned state and skip states whose children can't improve the answer, $O(N^2M)$.If we update hash in $O(1)$, update current best answer before placing a child into the queue and skip useless children (that aren't better than current best answer), we get $O(NM)$ but it becomes hard not to notice that only banned states are placed into the queue and we don't need queue at all.One also has to be careful with updating the best state if he wants to avoid $N^2$ (in the solution from the editorial too): if we assign it each time it gets improved, it can be up to $NM$ updates of length-N array.
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   Nice! Thanks for the insight. I learn a lot even when my code have already got Accepted.
 » B. Why this code in GO is dealing reversed results when sent? On my local machine everything is working fine. Spoilerpackage main import ( "fmt" "sort" ) func main() { var t int fmt.Scanf("%d", &t) for ; t>0; t-- { var a int var b int var c int var m int fmt.Scanf("%d %d %d %d", &a, &b, &c, &m) arr := []int{a, b, c} sort.Ints(arr) a, b, c = arr, arr, arr if (m>=c-(a+b+c)) && (m<=a+b+c-3) { fmt.Println("YES") } else { fmt.Println("NO") } } } 
 » Will anyone help me in upsolving C problem. I find that the editorial is giving TLE. Please help me
•  » » 8 months ago, # ^ | ← Rev. 3 →   You may notice that test#5 has n = 2*10e5 took 1,7 secs. Test #6 has n = 2*10^5 size too (thought we don't know how big is m in both), but we can see that "a" now is not a bunch of 1s and 2s {1 2 1 2 1 2 1 2 ...} but big numbers like 873579811631 — which means they will took your algorithm longer to digest.Take a look at "fast input output c++" topic. Google it.And be sure to take a look at this.
•  » » » Thanks, agarus, I was facing the same issue, and this helped me :)
 » Even though I have used binary search to find the heroes in question 1574C — Slay the Dragon it is giving TLE. Pls can someone check why is it giving so? my code is : 129554543
•  » » 8 months ago, # ^ | ← Rev. 2 →   Your input/output is too slow. This is caused by using iostream (cin/cout) with stdio (printf/scanf) synchronisation. Add the following lines to boost the speed considerably. ios_base::sync_with_stdio(0); cin.tie(0); Beware, however, that this makes it dangerous to use cin/cout alongside printf/scanf.I submitted your code with these two lines and it works within the time limit (129564251), albeit still a bit slow.
•  » » » Thanks a lot for helping me!
•  » » » I don't know why(still) my code is getting TLE, but after writing those two lines it got accepted. Thanks for that reply. Here is my code which got me TLE CODE
 » Hey, can someone please explain Geothermal's approach to question D: https://codeforces.com/contest/1574/submission/129399246It runs in approx 400 MS and my pq method is running in ~2900 MS: https://codeforces.com/contest/1574/submission/129568774
•  » » A banned build is hashed into a pair in Geothermal's code. Your code just push the whole build into the heap, obviously it's much slower.
•  » » » https://codeforces.com/submissions/Ashishgup# see this, he simply uses set
•  » » » » Yes, but he is not moving them through PQ.What is impressive — is his strange "recurse" function with quick return shortcuts. And strange line < ans &= (i + 1 == c[idx]); >
•  » » » » » yes :'), did you get his approach?
•  » » » » » » Yes, he is doing kind-of-dfs until he finds allowed build where all except current node are ones. Than he goes one node up and trying do the same. He is looking into same node that stupid-bfs does, but in different order. Thought bfs has chance of early exit, so it might not visit every blocked build, and this approach does not.
 » Thanks for the problems. Regarding problem C: how does the last paragraph explain that achievable m values form a range? Could someone clarify? I am thinking of different proof: Consider a string of form C...CB...BA...A that has maximum possible value of m (as in editorial A <= B <= C). Then take A or B and put it between some 2 letters C. This decreases number of equal adjacent pairs by 2. If one needs to decrease number of pairs by odd number, just put the A or B at the beginning of the sequence. It will decrease number of adjacent pairs by one.
•  » » You need to start with the string where m=0. Then, you need to remove the most recurring character in that string and reform that string for m=0. Then, you need to append the removed character and repeat this approach for the remaining string. In your example string CCBBAA, for m=0, we will first form ABCABC. Suppose we remove one C here and reform the string for m=0, we get CABABA. Appending the removed C, we get CCABAB. Now, we need to repeat this approach for the rest of the string: ABCABC, m = 0 CCABAB, m = 1 CCBAAB, m = 2 CCBBAA, m = 3
 » someone please explain graphical approach of D.
•  » » Here the nodes are considered as the banned builds... so it is basically a BFS swapping every single element of that banned build to get a new node... I guess this is what they meant to say about the graph approach.
 » Hello I'm newbie can someone write code for first example in c++ thank you
 » In B,"Now build the string for m=0"How to prove that we can always build for m = 0?
•  » » This means we have to try to build the string with no repetition, for ex if we are given input as 5A 2B 1C and we try to build the string for m = 0. the string should look like this A__A__A__A__A as you can see we have 4 empty spaces but not enough B's and C's to make a string with no same adjacent letters.
 » Using banned builds to get good build is crazy idea[problem:D]
 » 8 months ago, # | ← Rev. 2 →   I have a different solution for D.It's based on the fact that if you have two arrays a and b of lengths n1 and n2, you can build the largest m+1 sum pairs (out of n1*n2 pairs) using binary search. You can do this sequentially for every array or use divide and conquer to find all largest m+1 possible builds. One of them must be the answer as only m builds are banned.Here is the implementation.
 » 8 months ago, # | ← Rev. 2 →   i wonder if i can solve problem C in another way:first find the maximum value in array and the sum of the array.Call them $m$ and $s$then,if $m  » 8 months ago, # | ← Rev. 2 → 。 •  » » show your code please.  » What does question D even mean?? I didn't understand it  » Problem D. I have implemented the solution in the editorial, however, I'm getting TLE #6. Can anyone please take a look at my solution and figure out the reason for TLE? Thank you. •  » » You never update your visited set •  » » » OMG! So silly mistake. Thanks!! Giving a long break in competitive programming has shown itself.  » Please explain the o/p. Like for 1574E — Coloring, I wasn't able to figure how the o/p was reached.  » How can we solve problem F using FFT?  » https://codeforces.com/contest/1574/submission/129811930 GETTING TLE for test case 6  » I am have understood B and submitted it. But I want to try to print any string of that type if it exists. I m not sure how to implement it. Need little help. I don't want to multiple if-else conditions.  » can anybody help me in slay the dragon problem i am getting WA in test case 3 https://codeforces.com/contest/1574/submission/129995361  » If someone found the editorial solution of E trickier to understand, probably this might help.Convention: Stripe:- Band of alternate 0 & 1, eg: 0101010101.... or 1010101010... RowStripe0: A stripe that starts with 0, and forms the row of the grid. Eg: 010101... RowStripe1: A stripe that starts with 1, and forms the row of the grid. Eg: 101010... Similarly, ColStripe0, ColStripe1 n: number of rows, m: number of columns chess pattern: grid with chessboard pattern(first cell white) anti chess pattern: grid with inverted chessboard pattern(first cell black) Observations:O1: A valid grid consists of either Combination of n RowStripes: 2^n ways or Combination of m ColStripes: 2^m ways chess & anti chess patterns can be obtained by both 1) & 2) # ways to form valid grids, when all cells are empty = 2^n + 2^m - 2 O2: As we can see we can segregate the answer into two-part, Grids which are formed by RowStripes Grids which are formed by ColStripes Thus, from now on, we treat them separately. O3: Partially filled grid. Say column c has some cells already filled. Case 1: c has cells filled according to the chess(or anti chess) pattern only Then, column c can have only one possible configuration. => # ways to form valid grid with ColStripes = 2^(m-1) If such k columns are already filled => # ways to form valid grid with ColStripes = 2^(m-k) Case 2: Column c has cells corresponding to both chess and antichess pattern Then, we can't fill the cell c neither with ColStripe0 nor with ColStripe1 => # ways to form valid grid with ColStripes = 0. c is thus a bad_column Similar derivation if some row r is filled Collission case: If the grid was completely empty then there were two collisions, as explained in O1.3 If the grid was partially filled Case 1: If grid filled with either chess (or anti chess) pattern => Subtract 1 from final answer Case 2: If grid is filled with both patterns => No subtraction is required, as chess or anti chess pattern cant be achieved together. Code C1 Mark columns that are already filled For each column maintain whether it is filled in ColStripe0 pattern or ColStripe1 pattern C2 Similar to C1, mark rows that are filled C3 maintain bad_rows, bad_cols, empty_row, empty_cols See implementation here: 130091893(Solution was inspired by tourist's submission: 129358674) •  » » Thank you so much!  » 8 months ago, # | ← Rev. 2 → Can anybody explain how (c-1)-(a+b) <= m <= (a+b+c-3) is taking care of the case when (c-1)  » For the tutorial of problem E, how to understand "If there are two cells of same color in the same row with even number of cells between them then there is the vertical strip (because there are always two adjacent cells with same color between them)?" Can someone help me with an example？Thanks.In my opinion, there is obviously a counterexample: 1 0 0 1 0 1 1 0 There are no vertical strips?  » can anyone explain me in the problem B's tutorial: the strength of defend heroes is equal to$\sum_{j = 1}^{n}a[j] - a[i]$but not the sum of remained heroes not involved in killing the dragon?  » On problem C:Why we should only consider those 2 cases? Any proof on this? •  » » For the second case maximum$a$? One way might be to look at the two possible cases for$a
»

//for problem no. 1574A //code in c++

# include <bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; while(t--){ int n; cin>>n; int n1=n; for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ cout<<"()"; } for(int j=0;j<(n-i);j++){ cout<<"("; } for(int j=0;j<(n-i);j++){ cout<<")"; } cout<<endl; } } return 0; }