Не понял последнюю часть решения F:

Переберем через какую вершину будем связывать два дерева-остова — через s, через t или через обе (через обе возможно, только в случае, если есть в графе есть ребро {s, t}). Для каждого варианта осталось жадно соединить оставшиеся компоненты, если это возможно. Если нам это удалось для какого-то варианта, через какую вершину соединять, остается просто вывести ответ.

Напомню, что мы имеем два дерева, содержащих s и t соответственно, и набор отдельных компонент, каждую из которых возможно соединить с s и возможно соединить с t. Достаточно взять одну — любую — из этих компонент и соединить её и с s, и с t. Либо, если ни одной компоненты не осталось, соединить s и t напрямую (ребро {s, t} в такой ситуации обязательно существует). Затем все оставшиеся компоненты можно подсоединять хоть к s, хоть к t — это совершенно не важно. Главное, чтобы мы не превысили d_s и d_t. Проще всего жадно присоединять их к s, пока можно, а потом к t.

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

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

Holy molly the solution for div2E is very elegant.

div2E:

Известно, что между каждой парой городов существует не более одной дороги, а также никакая дорога не соединяет город сам с собой

Разве из этого не следует, что каждая компонента связности — дерево?

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?

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

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

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

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.

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

vector<string> inp;
vector<string> outp;

int main() {
    int len;
    string str;
    cin >> len >> str;
    str += "_";
    bool flag = true;
    char buf[512];
    int idx = -1;
    for (int i = 0; i < str.size(); i++) {
        char c = str[i];
        if (c == '(') {
            if (idx >= 0) {
                outp.pb(string(buf));
                memset(buf, 0, sizeof(buf));
                idx = -1;
            }
            flag = false;
        } else if (c == ')') {
            if (idx >= 0) {
                inp.pb(string(buf));
                memset(buf, 0, sizeof(buf));
                idx = -1;
            }
            flag = true;
        } else if (c == '_') {
            if (idx >= 0) {
                if (flag) outp.pb(string(buf));
                else inp.pb(string(buf));
                memset(buf, 0, sizeof(buf));
            }
            idx = -1;
        } else {
            buf[++idx] = c;
        }
    }
    int a = 0;
    for (int i = 0; i < outp.size(); i++) {
        a = max(a, (int)outp[i].size());
        //cout << a << endl;
    }
    cout << a << " " << inp.size() << endl;

}

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!

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.:(

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

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

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

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.

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

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?

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

Solution to div2E is just elegant! Could someone please provide some problems that have similar topic to this one?

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

1 2
2 3
3 1

Isn't a loop?

How to solve E using flows ?

can someone tell me where i m wrong in my code

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

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

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 S the resulting spanning tree. The "add" operation assumes that it doesn't create cycles in S.

• First, put in S all bridges adjacent to s or to t.
• Then, put in S all edges not adjacent to s nor to t.
• Finally, greedily add all edges adjacent to s or to t. 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, S contains all vertices from G. In overall it looks correct to me, though it's too late now for me to prove it.

Submission

can somebody tell me why this solution does not work? https://codeforces.com/contest/723/submission/51326586

In Div. 2 Problem A, I am getting Wrong Answer as follows.

Input 7 1 4 Output 4 Answer 6

But, $$$|7-4|+|1-4|+|4-4|=6$$$ and $$$|7-6|+|1-6|+|4-6|=8$$$ and $$$6<8$$$, so why is it showing WA when it is infact correct?