### Dormi's blog

By Dormi, history, 7 weeks 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

 » 7 weeks ago, # |   +4 Thanks for quick editorial.
•  » » 7 weeks ago, # ^ |   +204 Here are video solutions to A, B, C, D, E, F1, and F2 for people who prefer that style.
•  » » » 7 weeks ago, # ^ |   +8 I prefer both, Thanks :)
•  » » » 7 weeks ago, # ^ |   +3 King.
 » 7 weeks ago, # | ← Rev. 2 →   0 This is hard :(
 » 7 weeks ago, # |   +9 B solution: should it be $a_i > a_{i-1}$?
•  » » 7 weeks ago, # ^ |   +13 While ai−1 < ai > ai+1 reduce ai
•  » » 7 weeks ago, # ^ |   0 Thanks for updating.
•  » » 7 weeks ago, # ^ |   +5 a[i] should be grater than a[i-1] and a[i+1]
•  » » » 7 weeks ago, # ^ |   0 i agree partner
 » 7 weeks ago, # |   0 Why I am getting WA on test case 4 in problem C. 119395523 . I used dfs and printed 2^(connected comp).
•  » » 7 weeks ago, # ^ |   0 Try running the initial for loop from 0 to n. [0,n].
•  » » » 7 weeks ago, # ^ |   0 thanks got it. I had to use 0 based indexing..
•  » » » » 7 weeks ago, # ^ |   0 Unlucky mate. You got the logic right though.
•  » » » » » 7 weeks ago, # ^ |   +22 will learn from this mistake and improve next time
•  » » 7 weeks ago, # ^ |   0 u messed up some where in counting CC, just check it once.
 » 7 weeks 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?
•  » » 7 weeks 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.
•  » » » 7 weeks ago, # ^ |   0 Thanks it helped!
 » 7 weeks 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
•  » » 7 weeks 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
•  » » » 7 weeks 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.
•  » » 7 weeks ago, # ^ |   0 How you calculated the number of queries required for your implementation?
•  » » 7 weeks 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.
•  » » » 7 weeks ago, # ^ |   +6 Read this comment as I may not have been very clear in my explanation.
•  » » 7 weeks 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
•  » » » 7 weeks ago, # ^ |   +6 That makes sense. Thanks.
•  » » 7 weeks 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.cc/contest/1534/submission/119432261
•  » » 7 weeks ago, # ^ |   0 hey, we got a similar approach. I tried to prove it here.
 » 7 weeks ago, # |   -63 Implementation forces.
 » 7 weeks ago, # | ← Rev. 2 →   0 Nice problemset. "Lost Problemset"
•  » » 7 weeks ago, # ^ |   -16 *bugabooset
 » 7 weeks ago, # |   +33 जय हनुमान ज्ञान गुन सागर। जय कपीस तिहुं लोक उजागर।।Nice questionset.
 » 7 weeks ago, # |   +22 So interactive :D
 » 7 weeks 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?
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   -9 :)
 » 7 weeks ago, # |   0 119391919 Can someone please tell me why I'm getting TLE in problem C?
•  » » 7 weeks 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.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   -11 I think it would've been better outside that loop .
 » 7 weeks ago, # |   +1 liked the beauty of problem D, great job!
•  » » 9 days ago, # ^ |   0 Yes! Exactly! It took me one hint to solve though.
 » 7 weeks 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
 » 7 weeks 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
 » 7 weeks 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.
 » 7 weeks ago, # |   +5 Please, someone, explain 2nd problem, Thanks :|
•  » » 7 weeks 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.
 » 7 weeks ago, # |   +38 Benq orz. SpoilerBenq will break the highest rating achieved in the history of codeforces after rating changes.
 » 7 weeks ago, # |   0 I really enjoyed the round, I think it was well balanced.
 » 7 weeks 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?
 » 7 weeks 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?
•  » » 7 weeks 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?
•  » » » 7 weeks ago, # ^ |   0 I start with 0 indegree vertices but try to visit all of them, here is my submission. Please help.
•  » » » » 7 weeks 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.
•  » » » » » 7 weeks 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.
•  » » » » » » 7 weeks 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. 
•  » » » » » » » 7 weeks ago, # ^ |   0 Yes for your example my code doesn't work. Thank you.
•  » » » » 7 weeks ago, # ^ |   0 You could use topological sort here, instead of going with the indegre==0 idea
•  » » » » » 7 weeks 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?
•  » » » » » » 7 weeks 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.
 » 7 weeks ago, # | ← Rev. 2 →   0 is it possible to get different verdict in pretest and submission?
•  » » 7 weeks ago, # ^ |   0 Yes, it happened to me twice.
 » 7 weeks ago, # |   0 Can anyone please tell why i am getting wrong answer on pretest 2? 119361708
•  » » 7 weeks ago, # ^ |   0 There can be no 'R' or 'W'. Your code fails on test cases when all characters are '.'
•  » » » 7 weeks ago, # ^ |   0 Now, the same code got accepted, does that mean the testcase with only '.' is not there ? Here it is 119409968
•  » » » » 7 weeks 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
•  » » » » » 7 weeks 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.
 » 7 weeks ago, # |   0 Please can anyone tell me what does "set" mean in "bipartite set" in problem D?
 » 7 weeks 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.
 » 7 weeks ago, # |   0 what are the Algorithms i need to learn so that i can consistently solve A and B problems Ps: newbie:)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +7 none. That's the good part.
•  » » 7 weeks 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.
•  » » » 7 weeks ago, # ^ |   0 Thankyou ☺️ [user:DontLookBack][user:RNR]
 » 7 weeks 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:)
 » 7 weeks 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
 » 7 weeks 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; } } } 
 » 7 weeks ago, # |   +15 One of the best Editorial for Problem E. Lost Array, I could find on the net is this one by hu_tao, Solution for Lost Array (E).
•  » » 7 weeks ago, # ^ |   +18 Thanks! Really happy to see my editorials help others :D
•  » » » 7 weeks ago, # ^ |   0 Wonderful explanation! Thanks a lot!
 » 7 weeks 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?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +13 Yes really confusing. It is just authors example, they can know the solution without even attempting:))
•  » » 7 weeks 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.
 » 7 weeks 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 .
 » 7 weeks ago, # |   0 Did anyone solve problem C using maths, like a single formula or something?
•  » » 7 weeks ago, # ^ | ← Rev. 8 →   0 Sorry for that, I think sieve and modular exponentiation was the only math in it, no single formula.
•  » » » 7 weeks ago, # ^ |   0 He is using DSU. I am asking if it was possible to solve it using only some mathematical formula?
 » 7 weeks ago, # |   0 Problem A What is the bug of my code https://codeforces.cc/contest/1534/submission/119429114
•  » » 7 weeks ago, # ^ |   0 Try this 1 2 2 R..R It's correct but your code says no :)
•  » » » 7 weeks ago, # ^ |   0 No my code showing me 1 2 2 R..RYES RW WR
•  » » » » 7 weeks 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..
 » 7 weeks 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.
•  » » 7 weeks ago, # ^ |   0 number of black and white can obviously be same if n is even.
•  » » » 7 weeks ago, # ^ |   0 Sorry for asking wrongly, I am confused with the ceil(n/2), why can't it be <= floor(n/2).
•  » » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 It is =ceil(n/2) in case of equal parts
•  » » » » » 7 weeks 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))
•  » » 7 weeks 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.
 » 7 weeks ago, # |   0 nice editorial!
 » 7 weeks 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.
•  » » 7 weeks ago, # ^ |   0 It is optimal. You just reduced the ugliness score from 10 to 6 right?
•  » » » 7 weeks 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
•  » » » » 7 weeks ago, # ^ |   0 Yeah it should be a[i]>a[i-1] or a[i]>a[i+1].
 » 7 weeks ago, # |   0 https://codeforces.cc/contest/1534/submission/119444809Any ideas why?
•  » » 7 weeks 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.
•  » » » 7 weeks 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.
•  » » » » 7 weeks ago, # ^ |   0 Can you please elaborate? Store which values
•  » » » » » 7 weeks 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$)
•  » » » » » » 6 weeks 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
 » 7 weeks ago, # |   +8 The hints before the solutions are very helpful . I think every editorial should have hints .
 » 7 weeks 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.
 » 7 weeks 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).
 » 7 weeks 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.
•  » » 7 weeks 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!
•  » » » 7 weeks 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.
 » 7 weeks ago, # |   0 F1 is similar to https://dmoj.ca/problem/wc99sp5.
 » 7 weeks 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
 » 7 weeks 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
 » 6 weeks 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.
 » 6 weeks 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.
•  » » 6 weeks 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|$.
•  » » » 6 weeks 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.
 » 6 weeks ago, # | ← Rev. 2 →   0 Its mysterious to me. Please point out what is wrong in this easy problem A-solution.
•  » » 6 weeks ago, # ^ |   0 This loop checks only positions with same parity, but should check all positions.  for(int i=0 ; i
•  » » » 6 weeks ago, # ^ |   0 Thanks bro :)
 » 6 weeks 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?
 » 6 weeks 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.cc/contest/1534/submission/120320191