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.
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Я решил D совершенно по-другому: я пытался дойти до точки максимально "справа" и максимально "слева" и смотрел есть ли пересечение путей. Решение тут:60010755, задача засчитана. Может есть контер-тест для такого? Считать все возможные пути и авторское решение выглядят сложновато.
Я сделал дфс, где для всех точек из которых достижима $$$(n, m)$$$ добавить +1 к $$$way[dist]$$$, где $$$dist$$$ — дистанция от точки $$$(1, 1)$$$.
После чего сделаем $$$ans = min(ans, way[i])$$$ для всех $$$1 \le i \le n + m - 3$$$ (дистанции $$$0$$$ и $$$n + m - 2$$$ проверять не надо — таких точек всего по одной, это 1;1 и n;m).
Собственно это упрощённое авторское решение — если какой то $$$way[i] == 1$$$, значит все пути проходят через эту точку (нет альтернативы на такой дистанции от 1;1) и можно её заблокировать.
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?)
я решал D почти схоже с этим но у меня WA что я делаю я сначала смотрю можно ли добраться из (1, 1) до (n, m) и если нет то ответ сразу 0 после нахожу все точки сочленения и сохраняю их затем я смотрю все (x, y) к которым можно добраться из точек (1, 1) и (n, m) затем перебираю все сохраненные ранее точки сочленения и проверяю входят ли они в ранее проверенные позиции достигаемые с начального и финишных точек если нет то убираю их из списка точек сочленения в конце после проверки если остается хотя бы одна точка сочленения то ответ 1 иначе 2
спасибо сэкономили мне кучу времени
An easier solution for D:
You just need to run a maxflow.
My code: https://mirror.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://mirror.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)$$$.
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.
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://mirror.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)
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
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://mirror.codeforces.com/contest/1214/submission/61191311
I can't figure out my mistake on code,can anyone help me?
Answer is 2
My code is actually giving the correct answer for this test case. Thank you.
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.
Are you sure? https://ideone.com/gc6HOQ
I have tried with http://mirror.codeforces.com/contest/1214/customtest and C++ 17 and then i'm getting the correct answer which is 2.
Maybe you somehow changed the code during testing? I get 1.
Answer is 2
I tried it and my code outputs 2 for this test case. I have done the test using the custom invocation and c++ 17
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.
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://mirror.codeforces.com/contest/1214/submission/111791400
Can anyone explain me B question. I can't understand the test case
for 1st test case:-
Boys-5(b),
Girls-6(g),
participants-3.
Possibilities of participants:-
1. 0b,3g
2. 1b,2g
3. 2b,1g
4. 3b,0g
so answer is 4
An alternate solution for problem D, Just block any whole path from ({1,1}->{n,m}) and if afterblocking all cells of that path you can reach target from source then answer can never be 1 it must be 2.
Sorry for my poor English and necroposting.
Alternative solution for D. Create a graph consisting of valid paths, now our task is to find such node that removing causes $$$(1, 1)$$$ and $$$(n - 1, m - 1)$$$ to disconnect. We can use D&Q and DSU rollback for this, let $$$[l, r]$$$ range mean that we are considering all edges excluding edges that have endpoint of node in range $$$[l, r]$$$ then if we are at leaves, we simply check whether they are connected or not.
Submission: 361180231