Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3539 |

2 | Radewoosh | 3464 |

3 | V--o_o--V | 3338 |

4 | Um_nik | 3307 |

5 | Petr | 3297 |

6 | ecnerwala | 3282 |

7 | LHiC | 3266 |

8 | wxhtxdy | 3264 |

9 | Vn_nV | 3182 |

10 | xyz111 | 3147 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 207 |

2 | Errichto | 176 |

3 | neal | 159 |

4 | Ashishgup | 158 |

5 | PikMike | 157 |

5 | Petr | 157 |

7 | majk | 156 |

7 | rng_58 | 156 |

9 | Um_nik | 154 |

9 | 300iq | 154 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #375 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/19/2019 00:14:29 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Can anyone solve problem D when statement require replace land by water instead of replace water by land ??

Read the statement:

"You task is to fill up with the earth the minimum number of water cells"

water should be filled up with the earth.

It's just a translation from Russian and word order can be a bit unusual for native English speakers.

At least, you always have some examples, and can guess, what you are requered.

And, of course, you are allowed to clarify all the "dark" places, just asking the jury))

I think you misunderstood the statement, he is assuming that the situation he mentioned was the question instead.

I have no idea how to solve it with a decent time complexity though.

I think it’s just a matter of curiosity: is it possible to solve a similar problem where you have to replace land by water instead?

if N,M<=20, it will be easy to solve.

Hi, i got accepted in main tests to all my submissions then all of it was skipped and i became out of competition , but i didn't cheat ; can anyone please explain in which cases that happens

thanks in advance

I can!

Also you have really bad karma:

I hope you can find the strength to apologize not to me, but to community.

Codeforces police arrived

apologies for my rating_greed

why aren't both of the accounts disqualified/banned? it should decrease cheating by a great extent

the great cheater detector (:

My friends' template is same as my template, and it is quite long(20 lines). Can this be a problem in future?

shame on you

Shame on you !

Thief's mind is always like a police... "I didn't cheat" :P

Check the replies above my comment !

I wonder why users with a lower rating always get downvoted !

I think the letter s being lower case is not the problem here ! maybe it's the exclamation mark ?

Maybe he is 3 hour late for the karma train.

It happens all the time on Codeforces. When one said something interesting and got upvoted, another one would comment a very similar statement with a hope to increase his contribution point. It is not because of lower rating that make people click downvote button. It's because of "following trends" in comments. I was also the one who downvote those repeated comments.

Exact code as in tutorial for D CODE

Holy molly the solution for div2E is very elegant.

I solved it without one observation and it was less elegant

Why is molly holy?

Because it's molly silly!

PS: It was rhyming. So...

Why in problem D contraints for n, m was set so low? I thought bruteforce would work fine, but it failed me :(

Why do people refer to the problems like “div2E” when div2 is the only div in this contest?

It helps in using Ctrl+F to find the comments related to that question.

Can anyone explain what's wrong with this solution — Link. Thanks

I had the same error getting WA in test 8 with answer 433 instead of 422 in 21177336 and now i have fixed it 21181912

For me ,it's hard to follow PROBLEM C, Can someone explain ? Thanks .

Hi, I described my solution to problem C (Div2C) as Comments in my Accepted Code

Thanks so much. Sorry for causing problems.Please ignore me.

5 5 1 3 1 4 1 5 2 3 2 4 1 2 2 2

Participant's outputNoJury's answerYes 5 1 3 2 4 2 1 3Your output is No

I met a very strange problem, it cost me a lot of time and badly affect my standing. I still cannot figure out what the problem is. It's problem B. I ran it correctly locally but it could not even pass pretest 1. And When I debug it on code forces, it became very weird.

This is is my code for problem B. You can see the line I commented. If I uncomments it, it outputs correct number for pretest1. However, when I comment it, it outputs 13 or 7 sometimes randomly. Is this a bug? Again, when my code runs locally, it outputs correct answer. Hope someone could help me. What's wrong? It drives me crazy!

You never initialize

`buf`

, so when you do`string(buf)`

for the first time, you get garbage. In fact, to be more pedantic, the`string(buf)`

call has what’s calledundefined behaviour, so literally anything can happen from there on. Fixing this gets your solution accepted.Thank you very much for the help!

There's also a similar but easier solution.That is using Kruskal to build a MST.The weight between two vertices is 3 if they are s and t,and the weight is 1 if one of them is s,and the weight is 2 if one of them is t,and the weight is 0 if they are not s and t.Then you can use Kruskal as usual with the limit of ds and dt.But when I finished coding this problem,the contest had been over. :(

PS:This solution is a wrong one.But I cannot delete this comment.:(

It's wrong actually imo, i had similar to this during contest, got WA on 68. You got very lucky with this thing.

Look this test

5 5 1 3 1 4 1 5 2 3 2 4 1 2 2 2

If you were to mark 1 if equal to t, and 2 if equal to s, your solution would fail on this testcase.

Your solution, as described, fails this test:

(should be Yes) (this is system test #68)

Or as you implemented it (with a weight of 1 for

tand 2 fors), this equivalent test:(should be Yes; your code gives No)

Can't he do that for both cases? I mean once t=1 and s=2 and vice-versa?

Like, try to solve with t=1 and s=2, and if it fails, try to solve with t=2 and s=1? Okay, here’s a new test:

This solution fails to find an answer and outputs “No”: with t=1 and s=2, it starts by adding edges 2 3, 2 4, 2 5 and fails to connect node 7 to the tree, and with t=2 and s=1, it starts by adding edges 1 3, 1 4, 1 5 and fails to connect node 6 to the tree.

Meanwhile, the correct answer is “Yes”: for example, 1 6, 2 7, 1 3, 2 3, 1 4, 2 5.

I should note that this solution can get lucky: the order in which Kruskal adds edges of equal weight is unspecified, so it can just happen to add the right edges first. The problem is that the opposite can happen equally well.

Yes,you are right.My solution is wrong.Thank you very much.

I first added the bridges to the MST and then applied kruskal....it passed all tests,dont know if its actually correct.

Care to explain?

Wanted to know why any sequence of alphabets is a word if it is at the end . The question specifies that it should begin and end at "(" ,")" or "_". So a word athe end like "_c_abc" should give an answer 1 0 as abc is at the end and there is no special character at the end of abc . P.S I am a beginner so forgive me if my doubt seems too stupid

In the task description they say if the beginning/end is a special character OR doesn't exist. So it's like there's a _ added before and after the string you input. :)

ok thanks :)

can someone explain the solution for problem D. i am not able to understand the editorial

Let's find all lakes with thier sizes, sort it by size and delete first sz — k lakes, where sz — number of lakes. That's all.

i am not even getting statement of problem D , after getting pretests passed and WA in system testing.

Why are you using BFS? DFS is better and shorter, I think

but why it is giving WA..

Because you must use std::multiset to save sizes of lakes

but i am using set<pair<ll,ll> > and second value of all pairs will be different so i think that it should not affect the answer.

Yes, you are right.

http://codeforces.com/contest/723/submission/21170916

You can denote all STL containers as global variables. Maybe it will help.

You can add the same cell to the BFS queue more than once, and you’re incrementing

`ss`

every time. You should update`a`

when adding to the queue, not when removing from the queue; or at least check that`a`

is still 0 when removing from the queue.After changing it takes MLE at 26 test because long long http://codeforces.com/contest/723/submission/21171332

finally got it, thanks a lot

I disagree. BFS and DFS take the same amount of code, and, being used to BFS myself, I actually had to double-check that BFS wasn’t shorter! BFS is also faster and ensures there’s no need to worry about stack overflow.

Finally, I personally find it easier to write. (Personally. You can find DFS easier to write, and that’s fine too.) For example, I normally declare my variables locally within functions, and with DFS, I need to move them out to the global scope, whereas BFS works as is. (Unless it’s moved to its own function, but this is rarely done during contests. And while modularization is great in practical programming, during contests I tend to find it easier when the search code is right where it happens rather than in a distant place that I need to jump to when writing or reading my code.)

Firstly, thanks for taking the time to write a useful and well considered comment. I disagree with what you have said, but I am not looking for a fight! I just want to give a gentle rebuttal in defense of DFS.

The "BFS is faster than DFS" sentiment doesn't seem right to me. They both examine every edge once, and every vertex comes on/off the stack/queue once. The only difference is their memory patterns. BFS puts more data in the queue when the graph has a large frontier. The DFS stack is larger when the graph is very long with few branches. For most randomly generated graphs, it is the case that BFS is slower because random graphs have large frontiers (this is related to research on small-world networks and other random graph properties). In addition, when working on a grid, BFS usually must allocate more queue space because the implicit graph has a large frontier. Finally, a stack typically has better cache locality than a queue, since it only ever accesses one end of the data structure. My own ad-hoc experiments show that, until your input is so large that is breaks L3 cache, DSU is actually faster, despite the inverse-Ackerman factor.

The "easier to write" part also doesn't seem right to me. You can code a DFS simply by replacing queue with stack. No need for any recursive function. This means you can use a DFS any time you could use a BFS, as long as you aren't using any of the special properties of either.

One final note on stack-overflow. In competitive programming it is common to set the stack size to be effectively unbounded. You will get MLE rather than stack-overflow on Codeforces and similar websites, I believe. In Python/Java it is trivial to set the stack-size/recursion-limit to whatever you want, I think.

Don't get me wrong, I don't think DFS >> BFS. Certainly you should keep using a BFS if you prefer it; I am not trying to convert you to the one-true-way. I am just worried about people using BFS even when they prefer DFS.

Thanks for your well-thought-out response!

I should note that I don’t want to pressure anyone to stop using DFS and switch to BFS either. By all means, use whichever you’re most comfortable with. Perhaps this thread will just serve to shed a little more light on the various benefits and drawbacks of each approach.

You make a good point about nonrecursive DFS. Indeed, if your DFS doesn’t need to do any extra work after returning from a node’s child, you can implement it just like a BFS but with a stack instead of a queue. (Or if it does, you can’t easily use BFS proper either, so recursive DFS is your only choice.) I’ll admit I don’t have a developed opinion of this sort of DFS. I’ve considered this myself, and I do agree that sometimes the BFS frontier should be much larger than the DFS stack, and then it seems beneficial to prefer DFS. Maybe I should switch to this as my default search in contests.

When I said earlier that BFS was faster, I was only comparing it to recursive DFS. And the only reason such DFS should be slow is that it involves a lot of function calls, and function calls are unfortunately slow. The call itself isn’t fast, and then there is stack frame management! On this note, recursive DFS also uses more memory than a nonrecursive DFS because it needs to preserve all the local variables on the stack.

This is also where the stack overflow danger crops up: the more locals you have within the recursive DFS function, and possibly also the longer the function code is, the larger the stack frame. Perhaps this is not as much a problem nowadays, but I’ve seen DFS overflow the stack. The automatic stack extension in Linux that gives the impression of an infinite stack isn’t extremely reliable either, or at least wasn’t some years ago; and Windows doesn’t have such a thing at all AFAIK. Indeed, Codeforces specifies a fixed 64 MB or 256 MB stack where applicable. Of course, in many cases in competitive programming, there is a relatively easy workaround: don’t use locals in recursive DFS! Put your data in global arrays instead.

As a quick test, I took my solution to this contest’s problem F that used BFS and resubmitted it with recursive DFS. This test is by no means conclusive, as it gives just one data point and I don’t have an awful lot of trust in Codeforces’ timings, but I got 405 ms using BFS and 623 ms using DFS.

Just for completeness, one final note regarding function calls: calls that are inlined are fast! But recursive calls, other than tail-recursive calls, cannot be inlined. Although I know MSVC and CLR are actually able to unroll recursion somewhat (albeit MSVC requires a pragma for this), which should help, and GCC applies a different optimization, but I forget how useful it was in my tests. (Not DFS tests, just recursion tests.)

Oh, what did you mean when you mentioned DSU? I know what that is, but why did it come up and what were you comparing it to?

Yes, you're absolutely right that recursion is costly! Often it is nice, simple code, but it hurts performance, and you make a good point. Often in Haskell recursion can be very cheap, however, but I've never been able to use Haskell well in a competition.

Regarding DSU: if you are using a BFS/DFS to find connected components, then simply running union on each edge via DSU is what I am talking about.

(Regarding DSU:) huh, that’s interesting.

I think it's all about the nature of the scenario. If you are a competitive programmer, then chances are you need DFS to handle tree-dp (or retrieving information from children immediately). I think many people prefer dfs over bfs since more problems require dfs in specific than bfs. (Or at least on CF, I've been practicing a lot on CF and this is the case)

First of all, to decrease the number of lakes, you need to destroy an entire lake at a time. (If you try to destroy only a part of a lake and keep the rest of the lake, you’ll still have a lake! Or maybe even multiple lakes. Nothing good can come out of this.)

So you just need to greedily find and destroy the smallest lake until there are only

klakes remaining.You can find

alllakes first, then pick out the smallest ones (e. g. by sorting all lakes by their size) and destroy them.To find a lake, you start from a water cell and perform flood fill via a depth-first search or a breadth-first search (as the first two examples on Wikipedia show). To find all lakes, you can go through all cells on the grid and launch flood fill from each water cell that you’ve never visited before.

Make sure to ignore “lakes” that touch the edge of the grid, as they are no lakes! Instead, per the problem statement, they’re part of the ocean.

i am doing the same thing.

I'm not getting the logic used for Div2C . Could anyone please explain it in a simpler way?

Hi, I described my solution to problem Div2C as Comments in my Accepted Code

For problem E, I did the exact same thing as mentioned in editorial except that instead of adding vertices between odd-odd nodes, I created a pseudo-node(say 0), and added edges between this node and every odd node in the graph. Then I simply found the euler tour, and remove edges with 0 as one end-point. Here is the AC code with comments.

Can you give some place to read about euler tour?

Your code to find euler tour is quite short and simple.

I can't find the place from where I read about it. But it goes something like: If there's a Euler tour, then set your current vertex to any vertex with odd degree( otherwise any vertex will work.) Then do the following:

1. If current vertex has no neighbors, add it to the answer.

2. Otherwise push it to queue, and set the current vertex to one of its neighbor. Mark this edge so that you do not use it again in future.

3. Continue doing this(step 1 and 2) until the queue is empty and current vertex has no neighbours.

4. Your answer would contain the reverse euler tour you followed.

Since you add a vertex to the answer only after going to all of its neighbours, the simple recursive solution(or dfs) could work. Otherwise you can even easily implement the above steps using a queue.

Hey some basic doubts, The complexity of the algorithm is

O(V+E) right?And I have a little problem in proving it.

Hey guys,i recently got weirdest output for problem D which i cant explain..I passed all tests except 8th where my output brings out some really weird symbols..Can someone check it out ? Cheers LINK

`foo`

has only 260 elements, but there may be up tonm/ 2 = 1250 lakes initially (imagine a chequerboard pattern), and the test you’re failing on evidently comes close. You’re writing past the end of the`foo`

array and corrupting your memory.Thanks a bunch man! :)

What will be the solution to problem D if we were also allowed to change land cells to water cells?

Help, I don't undestand the problem C. Can someone explain it?

Hi, I described my solution to problem Div2C as Comments in my Accepted Code

Guys, is there any problem similar to "C — Polycarp at the Radio"?

I found Problem C very difficult to understand during the contest. I kept on messing around with bands, groups, songs and playlists.

For problem E, I see 'flows' in the tags. How can it be solved using flows?

This is a similar problem I solved using simple flows concept(Sum of incoming = Sum of outgoing).

Solution to div2E is just

elegant! Could someone please provide some problems that have similar topic to this one?547D

could you please explain me in div2E how to find euler cycles. and also i'd be grateful if you could give some source to read it.

In problem F. Problem says: 'There are no loops and no multiple edges in the graph'. In the first case,

Isn't a loop?

I was confused at first, but this is the correct definition from online:

"A loop in a graph is an edge of a node connecting to itself"

So the set you mentioned is a cycle, instead of a loop. (Actually all graphs with undirected edges have cycles... Or else they are classified as tree)

[wiki](https://en.wikipedia.org/wiki/Loop_(graph_theory)) Yeah, thanks so much.

How to solve E using flows ?

can someone tell me where i m wrong in my code

http://codeforces.com/contest/723/submission/21200797

You've done something wrong when counting the size of the lake during bfs.

Imagine that we have (1,1) and (2,2) in queue, both of them will push (1,2) and (2,1 in queue since it is not yet "visited" when issafe was queried, and gets counted.

ya got it. thanx alot for identifing my mistake

For problem E , its written in the editorial Let's choose how to connect them — with vertex s, with vertex t.... How can we connect the two spanning trees with s or t because s doesn't have any edge to other spanning tree and same goes for t ? can anyone please explain this ? Edit — Problem F

First, let's notice that problem is Div2F, not E. I guess it was meant, that at the end the graph is restored(!) by getting back s, t, and all the deleted edges if any. After step 2, vertices s and t will belong to the two spanning trees. Assume s and t in the same component; otherwise we are done. These two spanning trees should be linked to the remaining components as well as to each other either directly or indirectly.

In step 2, we are only adding edges from s to all components, which have no edges to t and edges from t to all components, which have no edges to s,hence there is no way they can be in same component after step 2.

Then we can only connect these two components either directly taking edge between s and t or by connecting s and t both to one of the remaining components which are not in these two spanning tree.

There is no way seem possible to me by which we can connect these two components with vertex s only or with vertex t only.

You are right. I was thinking of writing about this in a separate post tomorrow, but you were the first to bring it up! Consider a connected graph on 4 vertices: a,b,s,t. Edges: as, at, bs, bt. Using edges as, bs implies that either at or bt must be used. Thus the citation "or with both of them (only if we have in the graph an edge {s, t})" is not (!) valid meaning that the example above does not have an edge between s and t, yet both s and t must be used. I wonder whether this situation is covered in the system tests?

I think the very last part of the solution for F in the editorial is just poorly written. Personally, I don’t understand what it means, even after reading your comments. I actually posted a comment about this almost immediately after the editorial went up, but you haven’t seen because it’s in Russian, and for some reason, it stands there unanswered and with 0 rating to this moment.

Note that it’s literally impossible to restore only edges adjacent to

sand none adjacent tot, or vice versa, and get a connected graph, unless the graph also contains a (s,t) edge. You always need either (s,t) or a component that is simultaneously connected to bothsandt. You don’t need any special test case for this—this applies to every single test case!Here’s how I’d explain my solution instead:

So we have two trees and a (possibly empty) bunch of components each of which we know how to connect to

sand how to connect tot. Pick any one of these components and connect it to bothsandt; then connect each of the rest of the components to whichever side you like. The easiest way would be to greedily connect the remaining components tosuntil its degree reachesd_{s}and then connect the rest tot(or vice versa). If there are no such components at all and we only have two trees, then there must be an edge (s,t), because we know the original graph was connected; simply use that edge.****

~~~~~Привет[](http://)************[](http://)ф![ ](http://)- — — — — ______~~~~~****`````````mikl181`````````I have done a different approach to problem F: 1- first we remove t from the graph 2- then assign all edges coming from s the weight 1000. 3- then run prim's algorithm to calculate the MST. this will guarantee that all cycles are removed except cycles containing t, and the priority for the removed edges is given to the edges comming from s. 4- repeat steps 1, 2, 3 but in another version where s is removed instead of t. 5- now lets call first tree sTree and second tree tTree. 6- now combine sTree and tTree by adding any node from tTree which doesnt appear in sTree to sTree and its corresponding edges.

## note that any node which didnt appear in sTree is either t or a node that cant arrive from s without passing by t.

now we have a graph with no cycles except the ones that contain both s and t in the same cycle. 7- lets count the paths by simple DFS from each edges coming from s and if the DFS arrives to t then increament number of paths and record a pair of edges (the edge coming from s and the one arriving at t).

## note that paths cant overlap (two path can't have node or segment in common) because if this happens then there will be another cycle near to s OR near to t, but we already removed all cycles except ones containing both s and t (contradiction).

9- now to form the final tree, from x paths we got w should cut any x — 1 path and leave only one to make sure there is no cycles. FINALLY: using ds and dt and the pairs we recorded, u can determine which paths should be removes from s and which should be removed from t.

I think I have an alternative (greedy) solution for F. Let's call

Sthe resulting spanning tree. The "add" operation assumes that it doesn't create cycles inS.Sall bridges adjacent tosor tot.Sall edges not adjacent tosnor tot.sor tot. The only tricky case to handle is the (s,t) edge, which has to be processed at the end.Then there is a solution iff at the end of the algorithm,

Scontains all vertices fromG. In overall it looks correct to me, though it's too late now for me to prove it.Submission

For Problem

723C, I passed first 2 cases, but for 3rd test case I am getting runtime error and I have no idea why. infact I tried it on ideone, and if the elements in original array exceed 1000, I start getting runtime error. below is my code, please help me why is it so.