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 _kun_.

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

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: #60063170

Problems 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

I think your solution of D is same as the editorial solution

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.

The editorial never said that it had used sets, stacks/queues, tuples :(

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".

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) :)

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?)

An easier solution for D:

You just need to run a maxflow.

My code: https://codeforces.com/contest/1214/submission/59996918

Sorry for my poor English.

Might as well put that in the comment template.

Apologies, but I wouldn't call a max-flow solution "an easier one".

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.com/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.

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.

The flow is at most 2, so the complexity of Dinic is $$$\mathrm O(n+m)$$$.

Really preferred to use dp in A...

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. 60075870

This 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".

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.

But that's hard to code unless you already have existing code for it. But its quite overkill imo

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.

Not overkill if you copy+paste and code the rest in 5 minutes

Was ternary search by the position of the pair of the first element in F an intended solution?

Normal ternary search is just not correct. For example on test:

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 :)

I see a submission using ternary search in F, why is it works? 60035603

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.

I am sorry that I can't fully understand what's the meaning of f(x) and g(x).

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.

This time I understand, and why this greedy method works?

this is the same as the official editorial, maybe you can check it out.

Sorry, I find it's really hard to understand why this method it the same as the official editorial

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.com/contest/1214/submission/60144916

that is exactly what the sample solution does?

They are completely two different ways to implement the same idea you could say.

For the problem 1214D - Treasure Island, I'm getting a TLE on test 19 — 60144500. Can somebody please help me identify the error?

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)

Right sir. Thank you very much! :)

A can be solved in O(dlog(d))

My submission

Can A problem be solved in O(1)?

At least , O(d) is possible.

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."

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?

This picture only illustrates the method of coloring...

It's clear from the first statement that the answer is impossible for this case.

Yeah it is I just don't get why would they use the wrong pic

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

Nice solution!

But why does it work?

Can you please prove it (just the greedy part)?

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.

Thanks a lot!

Well, I find this solution the easiest to understand among all others.

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

You can only move right and down, that means this sample :

should be 0 instead of 1.

Thanks