### Dormi's blog

By Dormi, history, 11 months ago,

1534A - Colour the Flag

Author: crackersamdjam

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1534B - Histogram Ugliness

Author: Dormi

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1534C - Little Alawn's Puzzle

Author: Ninjaclasher

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

1534D - Lost Tree

Author: Plasmatic

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

1534E - Lost Array

Author: Plasmatic

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

1534F1 - Falling Sand (Easy Version)

Author: Dormi

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution

1534F2 - Falling Sand (Hard Version)

Author: Dormi

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Tutorial
Solution

1534G - A New Beginning

Author: Aaeria

Tutorial
Solution

1534H - Lost Nodes

Author: Ninjaclasher

Tutorial
Solution

• +314

 » 11 months ago, # |   +4 Thanks for quick editorial.
•  » » 11 months ago, # ^ |   +204 Here are video solutions to A, B, C, D, E, F1, and F2 for people who prefer that style.
•  » » » 11 months ago, # ^ |   +8 I prefer both, Thanks :)
•  » » » 11 months ago, # ^ |   +3 King.
 » 11 months ago, # | ← Rev. 2 →   0 This is hard :(
 » 11 months ago, # |   +9 B solution: should it be $a_i > a_{i-1}$?
•  » » 11 months ago, # ^ |   +13 While ai−1 < ai > ai+1 reduce ai
•  » » 11 months ago, # ^ |   0 Thanks for updating.
•  » » 11 months ago, # ^ |   +5 a[i] should be grater than a[i-1] and a[i+1]
•  » » » 11 months ago, # ^ |   0 i agree partner
 » 11 months ago, # |   0 Why I am getting WA on test case 4 in problem C. 119395523 . I used dfs and printed 2^(connected comp).
•  » » 11 months ago, # ^ |   0 Try running the initial for loop from 0 to n. [0,n].
•  » » » 11 months ago, # ^ |   0 thanks got it. I had to use 0 based indexing..
•  » » » » 11 months ago, # ^ |   0 Unlucky mate. You got the logic right though.
•  » » » » » 11 months ago, # ^ |   +22 will learn from this mistake and improve next time
•  » » 11 months ago, # ^ |   0 u messed up some where in counting CC, just check it once.
 » 11 months ago, # |   0 in question B editorial it is mentioned that "observe that decreasing a column will never affect whether it is optimal to decrease any other column, so we can treat the operations as independent."Why they are independent, Why it will never affect other columns?
•  » » 11 months ago, # ^ |   0 Initially consider just column i, all the columns in the range [1,i-2] and [i+2, N] won't be affected (since anything you do to column i doesn't change the outline of these columns). Since height of i column would be greater than the i-1 column (for any updation to height of i based on the algorithm), right outline of i-1 column won't change (left outline also doesn't change, by induction i.e. use i-1 as the central column). You could similarly argue for the i+1 column.
•  » » » 11 months ago, # ^ |   0 Thanks it helped!
 » 11 months ago, # |   +8 I tried a different approach for D, which I am not able to prove. So it would be great if someone can have a look and either prove or disprove it. My approachI took vertex 1 and rooted the tree on it. Then I calculated the levels of the other vertices for this rooted tree. Root is at level 0. All nodes at level 1 are children of vertex 1.From here, we will go to all the next levels from level 2 onwards in increasing order and query for all the nodes whose parent we don't know. From levels of the vertices and the array we get after querying a particular vertex, we can calculate the children of this vertex, the parent of this vertex, and the siblings of this vertex. We assign these values and move towards the next vertex.Link to my code
•  » » 11 months ago, # ^ |   0 This approach is same as given in tutorial. As you start from level 2, at this level you will get parent of all nodes at level3 so you would never query about nodes at level3 and go to level4 and will continue in similar fashion
•  » » » 11 months ago, # ^ |   0 No, I may go to level 3 as well. I am querying those vertices whose parents I don't know currently. If there exists a sibling for a node, I will calculate the parent of sibling as well. Now, I will not query this sibling node as its parent is known and it may have children which will be in level 3. So when I reach level 3, I will query for the children.
•  » » 11 months ago, # ^ |   0 How you calculated the number of queries required for your implementation?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +9 You are basically querying on all the even level vertices. Which is a form of bipartite graph. But it might get hacked. Say the total number of nodes present on even levels is more than n/2. How are you tackling this? I queried on even/odd nodes whichever set is smaller.
•  » » » 11 months ago, # ^ |   +6 Read this comment as I may not have been very clear in my explanation.
•  » » 11 months ago, # ^ |   +9 Yes I also used the Same Approach . The Correctness of this method can be proved by simply Saying that for any edge in the tree this approach will ask for max 1 node as a query (0 in case of that edge which connects it's parent and Sibling ) . Thus the maximum Number of Queries asked in the process will definitely <= ceil(n/2) and upper limit will be reached when no node has any sibling , straight structure like 1->2->3->4->5
•  » » » 11 months ago, # ^ |   +6 That makes sense. Thanks.
•  » » 11 months ago, # ^ |   +6 even i did it with the similar approach i tried on three four examples ans its working fine. This seems intuitive to me as for non leaf nodes we are querying only one time for finding parent and in this query only we also get info of one children also so we basically covered two nodes at least in one query it can be even more if node has siblings so that's why number of queries will always be less than ceil(n/2). Also if any particular depth has only single node than we don't require any query to find parent for all the nodes at depth+1 as there is only one option for parent at previous depth. my submission - https://codeforces.com/contest/1534/submission/119432261
•  » » 11 months ago, # ^ |   0 hey, we got a similar approach. I tried to prove it here.
 » 11 months ago, # |   -63 Implementation forces.
 » 11 months ago, # | ← Rev. 2 →   0 Nice problemset. "Lost Problemset"
•  » » 11 months ago, # ^ |   -16 *bugabooset
 » 11 months ago, # |   +33 जय हनुमान ज्ञान गुन सागर। जय कपीस तिहुं लोक उजागर।।Nice questionset.
 » 11 months ago, # |   +22 So interactive :D
 » 11 months ago, # |   0 Can anyone provide few intermediate level interactive problems.I found one easy in google kickstart (guess the number). All the other interactive problems I could find seem to be too advanced. Is there any resource where I could find many interactive problems to practice as a beginner?
•  » » 11 months ago, # ^ | ← Rev. 4 →   -9 :)
 » 11 months ago, # |   0 119391919 Can someone please tell me why I'm getting TLE in problem C?
•  » » 11 months ago, # ^ |   0 You're creating array of size 400005 for every test case. There can be a lot of test cases so you're basically trying to create 4*10^9 integers which will take too long.
•  » » » 11 months ago, # ^ | ← Rev. 3 →   -11 I think it would've been better outside that loop .
 » 11 months ago, # |   +1 liked the beauty of problem D, great job!
•  » » 10 months ago, # ^ |   0 Yes! Exactly! It took me one hint to solve though.
 » 11 months ago, # | ← Rev. 3 →   0 For E, I think we can also do greedy:First, if $n$ is odd and $k$ is even, we can never win.Notice that two moves always results in even number of bits flipped. So if $n$ is odd and $k$ is odd, then we will have odd number of moves, so start by turning on some $k$. Now we are left with turning on even number of $0$ bits.Let's denote $action1$ as turning on some $k$ bits using one move, and $action2$ as using two moves to turn on $x$ bits, where $x$ is even, and $2\le x\le min(2k, 2(n-k))$.If $action2$ is unavailable(there are no possible values for $x$), and our current number of zeros is not divided by $k$, we lose.Otherwise, if $k$ is odd we can just do action2 greedily, and if $k$ is even, before the greedy, we might need to do a single $action1$ (this is easy to check).Code: 119401441
 » 11 months ago, # | ← Rev. 2 →   +26 Kinda different solution to E. I'm sad, tired, and hopelessly hardstuck, so this is the short verThe answer is NO iff $n$ is odd and $k$ is even. The if part is true because we can't distinguish between any two arrays $a$ and $b$ such that for all $i$, $a_i \oplus b_i = 111111...$.Let's show that it's possible otherwise. The case where $k$ divides $n$ is trivial.Consider all other cases except for ($k$ is odd, $n$ is even, $2k$ > $n$). We can greedily form segments of length $k$ until there is an even number (let this number be $r$) of elements remaining such that $r < 2k$. It takes $2$ more queries to solve the problem. We can show that this is optimal via a parity condition.In the case ($k$ is odd, $n$ is even, $2k$ > $n$), we can set $k = n - k$ and solve the problem as in the former case, except that we query the complement of things. Pretty sure this is provable (the problem becomes strictly harder if you're given the complement xor, and you can solve it in the optimal number of moves in the equivalent easier version), but my head is foggy :/I think solving it this way is very impractical tho, the bfs solution should be the "correct" one to think of during contest
 » 11 months ago, # |   0 Can someone explain why my O(N^2) solution give TLE in problem D? My Submission My ApproachLet the current printed vertex be r. For those vertices v where d[v] == 1 has an edge with r. So we set graph[r][v] = true. Also, if we get sequences like 0 1 1 2 3 4, we can say the there is definitely an edge between 2-3, and 3-4 because there is only one shortest way to go from 2-3 and from 3-4. So we can keep track of distance values which occur only once, (0, 2, 3, 4) in this case and their corresponding vertex ({0, 1}, {2, 4}, {3, 5}, {4, 6}). Now we will loop through this array and add edge between two adjacent elements (element.second) of this array, if the difference in their d values (element.first) is equal to 1.To decide the next r value we look at the distance value (d[v]) of each vertex and count of elements having distance value (d[v] + 1). We want to select a vertex v such that the count of element having distance (d[v] + 1) is maximum. I am not sure if the my approach itself is accurate, but still O(N^2) solution must not be giving TLE.?Thanks.
 » 11 months ago, # |   +5 Please, someone, explain 2nd problem, Thanks :|
•  » » 11 months ago, # ^ |   0 Basically, for a given array ugliness is sum of abs(arr[i]- arr[i+1]) (insert 0 at front and back of the array). We can perform an operation which is decreasing arr[i] to arr[i]-1 provided arr[i]>0. ugliness in increased by 1 on each operation We need to minimize the ugliness of the array by performing the operations >=0 times or 0<=i<=n.
 » 11 months ago, # |   +38 Benq orz. SpoilerBenq will break the highest rating achieved in the history of codeforces after rating changes.
 » 11 months ago, # |   0 I really enjoyed the round, I think it was well balanced.
 » 11 months ago, # |   0 For D, is n/2 queries tight? (i.e., there isn't any other algorithm that can do it in fewer queries) If so, how to prove?
 » 11 months ago, # |   0 I wonder why so many contestants including me got WA on F1. And my solution is similar to toturial's (using strongly connected components) . That confuses me. (Ahh...I spend more than an hour during the contest on debugging my F1 code!!!)Here is my submissionCan somebody provide some details to be careful on F1? Or some special test cases?
•  » » 11 months ago, # ^ |   0 Hi Dormi, What I have done is that I created a directed graph as mentioned and then choose a vertex with in-degree 0 and started DFS, and marked all reachable vertices as done, Then choose another vertex with in-degree zero and so on, My answer is the number of times I start DFS. Why would this solution give Wrong answer? Why do we need to find SCC instead of doing DFS on the fly?
•  » » » 11 months ago, # ^ |   0 I start with 0 indegree vertices but try to visit all of them, here is my submission. Please help.
•  » » » » 11 months ago, # ^ |   0 Consider two rows in distance 2, each completly filled with sands.Both rows each build a circle of dependencies (an SCC), the above row triggers the below row, and there is no vertex with indegree 0.To see that the whole construct is triggered with only one operation we need to somehow see that the triggereing must start in the top row. That is, a SCC with indegree 0.
•  » » » » » 11 months ago, # ^ |   0 Yes, but in this case, my code reports correctly because since there are no vertices with in_degree = 0, it tries to visit unvisited vertices starting from vertices with greater height.The case where my code will fail is when an SCC at a lower height triggers two or more SCC's at a height above it.
•  » » » » » » 11 months ago, # ^ | ← Rev. 2 →   +3 Greater hight is not a good criteria, as seen in example 2. We can construct grids where we must not start from greatest height.Something like this: x.... x..xx x.... xxxx. 
•  » » » » » » » 11 months ago, # ^ |   0 Yes for your example my code doesn't work. Thank you.
•  » » » » 11 months ago, # ^ |   0 You could use topological sort here, instead of going with the indegre==0 idea
•  » » » » » 11 months ago, # ^ |   0 Are you suggesting that instead of shrining SCC into one node and then counting vertices with zero in degree, we can just do a topological sort and find the number of in-degree 0 vertices?
•  » » » » » » 11 months ago, # ^ |   0 We don't exactly need to find nodes with indegree==0 as a starting node. Just topological sort it and then start from reverse. This will make sure you are using the least number of nodes as a starting point.
 » 11 months ago, # | ← Rev. 2 →   0 is it possible to get different verdict in pretest and submission?
•  » » 11 months ago, # ^ |   0 Yes, it happened to me twice.
 » 11 months ago, # |   0 Can anyone please tell why i am getting wrong answer on pretest 2? 119361708
•  » » 11 months ago, # ^ |   0 There can be no 'R' or 'W'. Your code fails on test cases when all characters are '.'
•  » » » 11 months ago, # ^ |   0 Now, the same code got accepted, does that mean the testcase with only '.' is not there ? Here it is 119409968
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +3 Emmm, last time I use a 3*3 grid only has '.' on your code 119361708 , and it outputs wrong answer. But now your code 119409968 can output right answer.So it must have been changed something... (doge
•  » » » » » 11 months ago, # ^ |   0 Thanks, i got it now. i forgot, i had changed a line, which handled the '.' case with default initializing with 'W'. i need to be more careful with such edge cases.
 » 11 months ago, # |   0 Please can anyone tell me what does "set" mean in "bipartite set" in problem D?
 » 11 months ago, # | ← Rev. 2 →   0 I could only pass the pretest 1 in problem problem A.....this is my .119393289 I would appreciate if someone could help to check it.
 » 11 months ago, # |   0 what are the Algorithms i need to learn so that i can consistently solve A and B problems Ps: newbie:)
•  » » 11 months ago, # ^ | ← Rev. 2 →   +7 none. That's the good part.
•  » » 11 months ago, # ^ |   +3 You don't need to learn many algorithms, A, B problems are mostly ad-hoc, just solve Div2 A, B, C problems from previous contests and you'll be good.
•  » » » 11 months ago, # ^ |   0 Thankyou ☺️ [user:DontLookBack][user:RNR]
 » 11 months ago, # |   0 Why is getting wrong answer on this 119391694 because it gives correct answer on local compiler i simply do the 2^(connected components) ,please help thanks:)
 » 11 months ago, # |   0 In problem E does d, the maximum no. of queries also varies with n and k? I thought we just have to make it within 500 queries irrespective of n or k. T_T
 » 11 months ago, # | ← Rev. 3 →   0 Can someone help ? I overcomplicated the solution to problem A and got wrong answer . Can someone tell me why ? I used graph theory. Your code here... ll n , m; vector dx = {-1 , 0 , 1 , 0}; vector dy = {0, -1 , 0 , 1}; bool dfs(ll i , ll j , vector> &arr ,vector> &vis){ vis[i][j] = 1; for(ll itr = 0 ; itr < 4 ; ++itr){ ll X = i + dx[itr]; ll Y = j + dy[itr]; if(X >= 0 && Y >= 0 && X < n && Y < m){ if(arr[i][j] == arr[X][Y]) return false; if(arr[i][j] == 'R'){ arr[X][Y] = 'W'; }else if(arr[i][j] == 'W'){ arr[X][Y] = 'R'; } if(!vis[X][Y] && !dfs(X , Y , arr , vis)){ return false; } } } return true; } int main(){ ll t; cin >> t; while(t--){ cin >> n >> m; vector> arr(n ,vector (m)); ll cnt = 0; for(ll i = 0 ; i < n ; ++i){ for(ll j = 0 ; j < m ; ++j){ cin >> arr[i][j]; if(arr[i][j] != '.'){ cnt++; } } } if(cnt == 0){ ll flag = 1; for(ll i = 0 ; i < n ; ++i){ if(flag){ arr[i][0] = 'R'; }else{ arr[i][0] = 'W'; } cout << arr[i][0]; for(ll j = 1 ; j < m ; ++j){ if(arr[i][j-1] == 'R'){ arr[i][j] = 'W'; }else{ arr[i][j] = 'R'; } cout << arr[i][j]; } flag ^= 1; cout << endl; } continue; } bool fine = true; bool done = false; vector> vis(n , vector (m , 0)); for(ll i = 0 ; i < n ; ++i){ for(ll j = 0 ; j < m ; ++j){ if(arr[i][j] != '.'){ fine = dfs(i , j, arr , vis); done = true; break; } } if(done){ break; } } if(!fine){ cout << "NO" << endl; continue; } cout << "YES" << endl; for(ll i = 0 ; i < n; ++i){ for(ll j = 0 ; j < m ; ++j){ cout << arr[i][j]; } cout << endl; } } } 
 » 11 months ago, # |   +15 One of the best Editorial for Problem E. Lost Array, I could find on the net is this one by MagentaCobra, Solution for Lost Array (E).
•  » » 11 months ago, # ^ |   +18 Thanks! Really happy to see my editorials help others :D
•  » » » 11 months ago, # ^ |   0 Wonderful explanation! Thanks a lot!
 » 11 months ago, # |   -8 In problem D, sample test case 2. How can we tell for sure after just one query? It's given the tree is ? 5 gives 2 2 1 1 0. So can the tree be not like this?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +13 Yes really confusing. It is just authors example, they can know the solution without even attempting:))
•  » » 11 months ago, # ^ |   +8 Testcases in interactive problems doesn't make any sense. They are there just for helping understand interaction protocol, without giving hint to solution.
 » 11 months ago, # | ← Rev. 4 →   0 Update: Got the wrong case:What's wrong in my code 119358197 ? got Wrong Answer test case 4. my logic was exactly same as editorial .
 » 11 months ago, # |   0 Did anyone solve problem C using maths, like a single formula or something?
•  » » 11 months ago, # ^ | ← Rev. 8 →   0 Sorry for that, I think sieve and modular exponentiation was the only math in it, no single formula.
•  » » » 11 months ago, # ^ |   0 He is using DSU. I am asking if it was possible to solve it using only some mathematical formula?
•  » » 5 months ago, # ^ |   0
 » 11 months ago, # |   0 Problem A What is the bug of my code https://codeforces.com/contest/1534/submission/119429114
•  » » 11 months ago, # ^ |   0 Try this 1 2 2 R..R It's correct but your code says no :)
•  » » » 11 months ago, # ^ |   0 No my code showing me 1 2 2 R..RYES RW WR
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   0 Change your input to Char str[a][b]; and take input as matrix with double loops And check this testcase too should print no 1 2 3 ..RR..
 » 11 months ago, # | ← Rev. 5 →   0 Can anyone explain intuition behind hint 4 for problem D The min(number of black, number of white) nodes is ≤⌈n/2⌉. why can't it be <=floor(n/2) symbol? any counter example? UPD: problem solved, the editorial is updated.
•  » » 11 months ago, # ^ |   0 number of black and white can obviously be same if n is even.
•  » » » 11 months ago, # ^ |   0 Sorry for asking wrongly, I am confused with the ceil(n/2), why can't it be <= floor(n/2).
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   0 It is =ceil(n/2) in case of equal parts
•  » » » » » 11 months ago, # ^ |   0 It will be =floor(n/2) in case of almost equal parts. eg n=4 min(2,2)=2 , n=5 min(2,3)=2 <-(<=floor(5/2))
•  » » 11 months ago, # ^ |   0 This means there can be equal number of black and while nodes. in this case the equality holds.For example, consider the following tree.1---2---3---4 this has n/2=2 number of nodes of each color.
 » 11 months ago, # |   0 nice editorial!
 » 11 months ago, # |   0 In problem B why it is not optimal to reduce the height of a[i] a[i]>a[i+1] when i==0consider case n=2 5 1 initally ans = 5+4+11 1 now ans = 4+1+1or I missing something.
•  » » 11 months ago, # ^ |   0 It is optimal. You just reduced the ugliness score from 10 to 6 right?
•  » » » 11 months ago, # ^ |   0 yeah, but why in the editorial this condition is not given if(a[0]>a[1]) a[0]=a[1]the condition for optimal ans given in the ediorial is only when (a[i]>a[i-1] and a[i]>a[i+1]) but what about the end points
•  » » » » 11 months ago, # ^ |   0 Yeah it should be a[i]>a[i-1] or a[i]>a[i+1].
 » 11 months ago, # |   0 https://codeforces.com/contest/1534/submission/119444809Any ideas why?
•  » » 11 months ago, # ^ |   0 I figured it out. It turns out it's because I loop till the bottom of the table for every sand block I have. I found an optimization for this with storing the first block of sand below each block with DP.
•  » » » 11 months ago, # ^ |   0 A possibly easier way than DP (and I used this in White Pawn from a recent Atcoder contest) was to store the values in a set, and use lower_bound / upper_bound depending on what you want. It's slower to run, being $O(\log n)$ rather than $O(1)$ after pre-calculation, but it's faster to implement, and that extra computation time is almost always ok.
•  » » » » 11 months ago, # ^ |   0 Can you please elaborate? Store which values
•  » » » » » 11 months ago, # ^ |   0 In my solution, I had $top_j$ store the values of $i$ for which there was a block of sand in $grid_{i,j}$. So I can easily query the next block under $(i, j)$ with top[i].upper_bound(j) (upper_bound because lower_bound will give $i,j$)
•  » » » » » » 11 months ago, # ^ |   0 Oh, I got it. Thanks! But tbh for me DP was easier to implement XD But your solution is definitely useful in many other cases
 » 11 months ago, # |   +8 The hints before the solutions are very helpful . I think every editorial should have hints .
 » 11 months ago, # | ← Rev. 3 →   0 I think my solution for D seems more creative/easy because you dont need any experience with standard/similar problems, so I am putting it hereSo we will root the tree at 1 and evaluate parent for each node.first we will ask for depths (i.e. distances from 1), and for all nodes with depth 1 we will set 1 as their parentNow, let's iterate over all nodes in increasing order of depth. Whenever we encounters a node (let's call it r) without a parent assigned we will make a query with r, and set it as a parent of all nodes with distance 1, except one which already had a parent, let's call it p. Now take r and other nodes which have a dis of 2 with r and same depth as r, set p as their parent.Proof: Let's ignore 1st query and node for simplicity Note, for each node that we made a query with, we skipped at least 1 node (obviously its parent) above it... also notice that each node is covered by at most 1 of its children (analyze the last operation). So, chosen <= skipped // ignoring 1st node/query in the worst case chosen = skipped, total_nodes = chosen + skipped + 1 = odd number // added 1 for node 1 chosen + 1 == ceil(total_nodes/2) // added 1 for 1st query to LHScodeI only had a blurred picture of it in the contest :(Please correct me if something was wrong, and also feel to ask.
 » 11 months ago, # |   0 I wasn't able to take this contest, but I just did a virtual and I have to say — These problems were brilliant! They were unique, easy to understand, and not too complicated to implement (even F1, if you just look at the solution, it seems complicated, but it's really not).
 » 11 months ago, # | ← Rev. 2 →   +39 My solution to E was much more direct than using BFS. The first observation is that each query just gives you a linear equation (mod 2) containing $k$ of the variables. Then, in order to find the XOR-sum of everything, it's necessary and sufficient to make some queries such that a linear combination of them is the desired XOR-sum. In particular, because we're working mod 2, the coefficient of each equation is either $0$ or $1$, and we can just not query the 0's, so we need exactly a set of queries such that the total XOR is the XOR-sum. In other words, we need to query each variable an odd number of times.Now, the problem is much simpler: first, consider a number of queries $d$, so that we will make exactly $d$ queries each with exactly $k$ distinct variables. Then, if we fix the frequencies of variables, the greedy strategy "always query the $k$ variables with the greatest remaining frequency" is guaranteed to work unless the max frequency is $> d$, in which case there is no solution. Thus, we want to minimize the max frequency while keeping all frequencies odd and having sum of $dk$; this is achieved by making the frequencies as similar as possible, either $1+2\lfloor (dk-n)/2/n \rfloor$ or $1+2\lceil (dk-n)/2/n \rceil$. In particular, $d$ is valid iff $dk \ge n$, $dk \equiv n \pmod{2}$, and $1 + 2 \lceil (dk-n)/2/n \rceil \le d$, so we can find the minimum $d$ with a simple linear search.
•  » » 11 months ago, # ^ |   0 I was thinking of something similar and got all the inequalities for necessary $d$. But then I got stuck at step of showing that the $d$ is sufficient (the greedy strategy you mentioned). Can you give some more insight on why it works and how did you think of that? Thanks!
•  » » » 11 months ago, # ^ |   0 The intuition is just that having smaller groups is better than larger groups because small groups can always be split into separate queries, but large groups can get stuck, so you want to prioritize cleaning up the largest groups. The k=2 case is definitely quite well known: you can form pairs of distinct elements as long as there's no single majority element. You can prove this formally by inspecting the greedy algorithm, or you can use a max-flow-min-cut/Hall's marriage theorem argumrnt.
 » 11 months ago, # |   0 F1 is similar to https://dmoj.ca/problem/wc99sp5.
 » 11 months ago, # | ← Rev. 2 →   0 In question D I'm getting an error "wrong output format Unexpected end of file — int32 expected". I don't understand if I used wrong approach because my code works fine on small test cases and counter test cases. If someone could help me resolve it that would be a great help. Thank you. My code: 119541888
 » 11 months ago, # | ← Rev. 2 →   0 Okay I got a stupid question.What does at most [n/2] operations means in problem D ? what does [n/2] in general ? Is it floor or ceil? TIA
 » 11 months ago, # |   0 Problem B would have been even more interesting and difficult if height of bars could be increased as well. Which sadly how I misinterpreted it.
 » 11 months ago, # |   0 In problem G, $dp[x][y] = (\min{dp[a][b]} \forall y-(x-a) \leq b \leq y+(x-a)) + (\sum{\frac{|y-z|}{2}} \forall potatoes (x,z))$ all such b's aren't reachable, won't that create any problem? Also what should be our intial function, I think it should be like $f(0) = 0,$ else $\infty$. Somebody please help me out.
•  » » 11 months ago, # ^ |   +8 Many times, you can analyze the version of the problem where positions are allowed to be reals rather than integers, and then prove they have the same result. This problem has that property, because all inflection points are integers, so you might as well only visit integer points.Your initial function is correct. It's actually enough to treat it as $f(x) = (n+1)|x|$.
•  » » » 11 months ago, # ^ |   +13 Thanks a lot!! I understood it now. Actually what I understood is : The answer always occur at one of the given points in the final graph(we need not think that whether we have our calculated minimum achievable or not) Whenever we expand our graph about the center, all the points in domain get their new values from the points which were in domain previously(here I want to say that they are not taking any junk value from the previous states which were not achievable). This can be seen from parity of points and the offset we have. Actually this was the main confusion for me. Basically at every transition all the points in domain are correct and we do not care about others, and in the end we will surely be having some point (which was given intially) on the global minimum line.Please correct me if I am wrong somewhere.
 » 11 months ago, # | ← Rev. 2 →   0 Its mysterious to me. Please point out what is wrong in this easy problem A-solution.
•  » » 11 months ago, # ^ |   0 This loop checks only positions with same parity, but should check all positions.  for(int i=0 ; i
•  » » » 11 months ago, # ^ |   0 Thanks bro :)
 » 11 months ago, # | ← Rev. 2 →   0 In F2 we need to mark the minimum number of nodes in a DAG such that a set of "special nodes" can be reached by at least one marked node.Because any special node can be reached by a contiguous range of other nodes we can solve this problem efficiently in this case.Is this problem NP-hard in a general graph?
 » 11 months ago, # |   0 For problem F2 to solve the last task like covering every special node via segments we can use easy dp that seems to work in O(size^2) but actually the sum of all segments` length is O(n). Here is my solution https://codeforces.com/contest/1534/submission/120320191
 » 10 months ago, # |   0 I did problem C using DSU 124814179. But I get a wrong answer on test case 2. Is my approach correct? What am I doing wrong?
 » 9 months ago, # | ← Rev. 2 →   0 can some one tell me what's wromg in my approach Problem C..i got WA at 3rd testcase. Link for my submission http://codeforces.com/contest/1534/submission/125680024.let n=5; a[i]={1,2,3,4,5} b[i]={3,5,1,2,4}I simply checked for pairs like a[i]=1,b[i]=3 and a[j]=3 b[j]=1, counted them and if some unpaired are left they form a another single cycle like a[i]=2 b[i]=5, a[i]=4 b[i]=2 , a[i]=5 b[i]=4. So number of ways we can generate another solved sequence is 2 ^(cnt +1).
 » 9 months ago, # |   0 For the Problem G,if offsetting all values in the left of the min point by −(j−i) and offsetting all values of the min point by (j−i) to get fj from fi,fi shuold be a convex function.but we need add fi to gi,how to prove that fi+gi is a convex function and can support the next operation?
•  » » 9 months ago, # ^ |   0 That is to say how to prove that we can get a convex function when we add a convex function onto another convex function.
•  » » » 9 months ago, # ^ |   0 Ok,I know how to prove that now. Thanks.