### ch_egor's blog

By ch_egor, 23 months ago,

Thanks for the participation!

1214A - Optimal Currency Exchange was authored and prepared by Helen Andreeva.

1214B - Badges was authored by jury and prepared by Chmel_Tolstiy.

1214C - Bad Sequence was authored by meshanya and prepared by GoToCoding.

1214D - Treasure Island was authored by meshanya and prepared by malcolm.

1214E - Petya and Construction Set was authored and prepared by voidmax.

1214F - Employment was authored and prepared by grphil.

1214G - Feeling Good was authored and prepared by isaf27.

1214H - Tiles Placement was authored and prepared by cdkrot.

• +84

 » 23 months ago, # | ← Rev. 6 →   +10 Alternative solution for D: Treasure Island if you're using a language where sets and tuples can be expensive (e.g. JVM), is to simply convert the grid to a 2D character array. Then you can iterate through the array twice, once in forward order, once in backward order. The first time, you mark $(1, 1)$ with e.g. a '0' character, and "spread" the '0' characters over the '.' characters. The second time, you do the same from the goal backward, except changing from '0' to '1'. Now the '1' characters represent the intersection of the two sets of accessibility.It's basically a BFS/DFS variant that isn't actually either, but rather "reading-order first", taking advantage of the fact that successors always come later in reading order.Sample code in Kotlin: #60063170Problems like this and #1195E OpenStreetMap really makes me wish Project Valhalla was out already. Either that or it's time for me to learn another language :P
•  » » 23 months ago, # ^ |   +17 I think your solution of D is same as the editorial solution
•  » » » 23 months ago, # ^ | ← Rev. 3 →   0 It's the same basic idea, and represents the same things set-theoretically, but the implementation details (using arrays rather than hash-sets, stacks/queues, and tuples) make all the difference speed-wise.
•  » » » » 23 months ago, # ^ |   -8 The editorial never said that it had used sets, stacks/queues, tuples :(
•  » » » » » 23 months ago, # ^ | ← Rev. 2 →   0 It's implied by the suggestion to use DFS. To properly implement DFS, you need a stack (or a queue for BFS), and the most natural way to store the vertices (i.e. grid positions) is with tuples. My posted solution isn't a proper DFS nor a BFS; it takes advantage of the property for successors to always be later in "reading order".
•  » » » » » » 23 months ago, # ^ |   +10 I don't know about everyone but if I want to run a dfs on this kind of grid, I will simply make a recursive call from cell(1, 1) and backward from cell(n, m) :)
•  » » » » » » » 23 months ago, # ^ | ← Rev. 2 →   +4 That's technically also a stack, except you're using the call stack rather than an explicit object. :P Which also may cause problems in the JVM due to small default call-stack size. (StackOverflowException anyone?)
 » 23 months ago, # |   +23 An easier solution for D:You just need to run a maxflow.Sorry for my poor English.
•  » » 23 months ago, # ^ |   +1 Sorry for my poor English. Might as well put that in the comment template.
•  » » 23 months ago, # ^ |   +29 Apologies, but I wouldn't call a max-flow solution "an easier one".
•  » » 23 months ago, # ^ |   +10 You can implement Ford-Fulkerson implicitly in a simple way since all edges have infinite capacity and all nodes have 0/1 capacity: https://codeforces.cc/contest/1214/submission/60080823.The find() function is called at most three times due to the observation that the min cut / max flow is at most 2.
•  » » 23 months ago, # ^ |   0 I think if you don't converting a Plane Graph into a Dual Graph and use Dijkstra,the complexity of the algorithm is not right.
•  » » » 23 months ago, # ^ |   0 The flow is at most 2, so the complexity of Dinic is $\mathrm O(n+m)$.
•  » » 15 months ago, # ^ |   0 Can you please explain why you made edges with capacity 1/0 for nodes which are empty/forests. I thought just joining edges between nodes which have a path available with capacity 1, but then that is giving WA on tc 44.
•  » » 7 weeks ago, # ^ |   0 Hello, Can you please explain the logic behind how you created the above graph, Thanks in advance :)...
 » 23 months ago, # |   0 Really preferred to use dp in A...
 » 23 months ago, # |   +26 A really simple solution for D: just run a dfs and check if the destination is reachable and mark all nodes you saw. For every path you find like this you can increase the result by one. 60075870This solution works since the corresponding graph is planar, the start and destination both lie on the outer face, and the dfs is in fact a so called "right-first-dfs".
 » 23 months ago, # |   0 D can actually be easily solved using Dinic's algorithm in O(N*M). At first, it's clear that max flow from (1, 1) to (n, m) will be the answer, as max flow equals min cut, which is exactly what we need to find in the problem. Now, here's why Dinicz will find max flow in this graph in O(N*M). All the edges' capacity is 1, so one faze of the algorithm will work in O(M), where M is the amount of edges in the graph. The other thing is that Dinicz will stop after the first faze. Each faze lengthens the shortest path from S to T int the net, meanwhile in this one all the paths are the shortest.
•  » » 23 months ago, # ^ |   0 But that's hard to code unless you already have existing code for it. But its quite overkill imo
•  » » » 23 months ago, # ^ |   0 Yeah it is. I didn't actually code it on the contest, just thought about it afterwords. This problem can really help understanding flows and Dinic's algorithm better though.
•  » » » 23 months ago, # ^ |   +17 Not overkill if you copy+paste and code the rest in 5 minutes
 » 23 months ago, # |   +10 Was ternary search by the position of the pair of the first element in F an intended solution?
•  » » 23 months ago, # ^ |   0 Normal ternary search is just not correct. For example on test: 10 20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5 10 10 10 10 10 4 4 4 4 4 4 4 4 4 4 4 5 4 4 4 Solution 60008635 (AC on round) don't work. Because a lot of offsets give the same value, and this value is not optimal.However there are some other implementations, for example 60002491. There the search is for the number of people crossing 0=M bound, And for some values it calculates not the optimal score, but smth larger. And I'm curious how to challenge it :)
 » 23 months ago, # |   0 I see a submission using ternary search in F, why is it works? 60035603
•  » » 23 months ago, # ^ |   -7 Consider function $f(x)=\sum_{i=1}^{n}|a_i-x|$ , it's easy to see that $f(x)$ is a lower convex function.So the function $g(x)=\sum_{i=1}^{n}|a_i-b_{i+x}|$ is similar to $f(x)$ if $a,b$ are non-decreasing.And it's easy to transform the original problem to this : find the minimal value of $g(x)$ $(-n\leqslant x \leqslant n)$.Sorry for my poor English.
•  » » » 23 months ago, # ^ |   0 I am sorry that I can't fully understand what's the meaning of f(x) and g(x).
•  » » » » 23 months ago, # ^ |   0 Consider a greedy mathods:transform $a_i$ to $a_i+m$, and $b_i$ to $b_1,b_2,\cdots ,b_n,b_{n+1}+m,\cdots, b_{2n}+m,b_{2n+1}+2m,\cdots,b_{3n}+2m$, after that the length of $b$ is $3n$.then let $g(x)=\sum_{i=1}^{n}|a_i-b_{i+x}|(0\leqslant x\leqslant 2n-1)$.it is a lower convex function because it's made up of $2n$ points in $f(x)$ from left to right.
•  » » » » » 23 months ago, # ^ |   0 This time I understand, and why this greedy method works?
•  » » » » » » 23 months ago, # ^ |   0 this is the same as the official editorial, maybe you can check it out.
•  » » » » » » » 23 months ago, # ^ |   0 Sorry, I find it's really hard to understand why this method it the same as the official editorial
 » 23 months ago, # |   0 An alternative solution for D:: Use top down or bottom up approach to find the points (r,c) which can access (n,m) => those points which can traverse freely to (n,m). At this point we do not care where to create blockages. Then observe that if we block any of the diagonal (0,0) gets cut off from (n,m). We use this fact and the information we extracted earlier to find the ans. Then use BFS from (0,0). Create a diagonal list say dp[]. As we are traversing each element, if the element (x,y) can access (n,m) we add 1 to dp[x+y].Then we recur over this dp and find its minimum. That is the answer. https://codeforces.cc/contest/1214/submission/60144916
•  » » 23 months ago, # ^ |   0 that is exactly what the sample solution does?
•  » » » 23 months ago, # ^ |   0 They are completely two different ways to implement the same idea you could say.
 » 23 months ago, # |   0 For the problem 1214D - Treasure Island, I'm getting a TLE on test 19 — 60144500. Can somebody please help me identify the error?
•  » » 23 months ago, # ^ |   0 there are many things you should change (but the tle is probably due to huge constant factors...):try to avoid a set if it will contain 10^6 elements (which can happen if I understand your code correct). 10^6 elements in a set are really much...don't use new and delete in competitive programming. Use a vector and let it do the allocations. (this makes writing code much simpler)don't use pointers. Use references. (again this makes things for competitive programming easier to write and we almost never need pointers)
•  » » » 23 months ago, # ^ |   0 Right sir. Thank you very much! :)
 » 23 months ago, # | ← Rev. 2 →   0 A can be solved in O(dlog(d))My submission
 » 23 months ago, # |   0 Can A problem be solved in O(1)?
•  » » 23 months ago, # ^ |   0 At least , O(d) is possible.
 » 23 months ago, # |   +3 I problem D what is the meaning of this statement "f answer is one, there must exist such cell (x,y) that each path from (1,1) to (n,m) goes through that cell. Also we can notice that in each path the cell (x,y) goes on the (x+y−1)th place."
 » 23 months ago, # |   0 Isn't the pic from the H editorial incorrect? There is a path 1->2->1 on the left of the diametr. Overall the editorial isn't clear. When we repeat the algorithm recursively, do we proccess it on each subtree coming out of the diametr?
•  » » 23 months ago, # ^ |   +12 This picture only illustrates the method of coloring...It's clear from the first statement that the answer is impossible for this case.
•  » » » 23 months ago, # ^ |   0 Yeah it is I just don't get why would they use the wrong pic
 » 23 months ago, # | ← Rev. 2 →   +3 Yet another solution to problem D — no graph algorithms required! Precompute $d_{i,j}$ — whether $(i,j)$ is reachable from $(1, 1)$. Now, greedily find two paths from $(n,m)$ to $(1,1)$, one where you prioritize moving along the x-axis, and another one where you prioritize moving along the y-axis. If these two paths intersect somewhere other than in $(1, 1)$ or $(n, m)$, you can block that cell and the answer is $1$, otherwise it's $2$.Code: 60184416
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 Nice solution!But why does it work?Can you please prove it (just the greedy part)?
•  » » » 23 months ago, # ^ |   +14 Proof by AC :)Just kidding, one direction is obvious, if this algorithm finds two disjoint paths, then clearly the solution is 2.The other part is not so obvious. It's enough to show that if the two greedy paths intersect, then every valid path has to pass through these intersection vertices. This is exactly the definition of a blocking vertex.I will show that all valid paths lie between the lowest and the highest path. Assume the contrary — some part of a valid path "sticks out", say, it sticks out below the lowest path. We can use this part which sticks out to find an even lower path, meaning that our original lowest path was wrong, a contradiction.This means that every path has to pass through every intersection vertex, because that's the only vertex between the two paths.
•  » » » » 23 months ago, # ^ |   0 Thanks a lot!Well, I find this solution the easiest to understand among all others.
 » 23 months ago, # |   0 For D, I have written a code which similar to "Permeability of soil" problem.But I am getting WA. Can someone help me with it? 60012934
•  » » 23 months ago, # ^ | ← Rev. 3 →   +8 You can only move right and down, that means this sample : 5 4 .... ###. .... .### .... should be 0 instead of 1.
•  » » » 23 months ago, # ^ |   0 Thanks
 » 22 months ago, # |   0 I have been trying to pass problem D with the following approach: Check if there is not a path between (0,0) and (n-1, m-1), then the answer is 0. Check if there is not a path between (0,0) and (n-1, m-1) without using articulation points, then the answer is 1. Otherwise the answer is 2. Submission: https://codeforces.cc/contest/1214/submission/61191311I can't figure out my mistake on code,can anyone help me?
•  » » 22 months ago, # ^ |   +1 Simple test3 5 ..... ..... #.#.. Answer is 2
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 My code is actually giving the correct answer for this test case. Thank you.
•  » » » » 22 months ago, # ^ |   0 I'm sorry I forgot to say that I consider the edges in both ways when checking if there is a path between (0,0) and (n-1, m-1) without using articulation points.
•  » » » » 22 months ago, # ^ |   +1 Are you sure? https://ideone.com/gc6HOQ
•  » » » » » 22 months ago, # ^ |   0 I have tried with https://codeforces.cc/contest/1214/customtest and C++ 17 and then i'm getting the correct answer which is 2.
•  » » » » » » 22 months ago, # ^ |   +1 Maybe you somehow changed the code during testing? I get 1. Try this test too5 5 ..... .###. ..#.. .###. ..... Answer is 2
•  » » » » » » » 22 months ago, # ^ |   0 I tried it and my code outputs 2 for this test case. I have done the test using the custom invocation and c++ 17
•  » » » » » » » » 22 months ago, # ^ |   0 You are correct. My code and my solution are incorrect. Here is another test case in the same "style" as your test case: 5 5 ..... .#.#. .#.#. .###. .....I think that the problem with my solution is that i'm taking into consideration the entire graph, but to use this solution i should take into consideration only the graph with the paths between (0,0) and (n-1,m-1). Thank you very much.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 See articulation point will work but you need to modify you graph which is little tedious. After you modify u considers those vertices of edges only which are on the path from (1,1) to (n,m). See suppose graph are having branches which aren't leading to destination then simply remove that branches(vertices with them).After this you will have a new graph in which every point is on path to destination. Now on this graph if any point is articulation point you can claim graph will divide into parts one part containing (1,1) and other (n,m). If you have any queries do ask. https://codeforces.cc/contest/1214/submission/111791400
 » 22 months ago, # |   0 WTF。I am always in queue.what i can do?
 » 19 months ago, # |   0 Can anyone explain me B question. I can't understand the test case
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 for 1st test case:-Boys-5(b),Girls-6(g),participants-3.Possibilities of participants:-1. 0b,3g2. 1b,2g3. 2b,1g4. 3b,0gso answer is 4
 » 13 months ago, # | ← Rev. 2 →   0 This is my code for the solution of problem C It failed at test case 18 and I don't understand why Ignore that # isnt presentPlease help! include 2.using namespace std; define ll long long int main(){ int tt; cin>>tt; while(tt--){ ll n; cin>>n; 10.string s; cin>>s; int cnt=0,tmp=0; for(auto x:s){ if(x=='(') cnt++; 16.if(x==')'&&cnt) cnt--; else if(x==')'&&!cnt) tmp++; 20.if(tmp>1) 21.break; } 23.if(tmp<=1&&!(n%2)) cout<
 » 7 weeks ago, # |   0 who else didn't even understand the B question :(