fcspartakm's blog

Codeforces Round #375 (Div.2) Editorial
By fcspartakm, history, 8 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +85
  • Vote: I do not like it

Comments Comments (96)
| Write comment?
»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    and we have been told that, we can change land to water and water to land !! any !! then how can we solve?

    → Reply
»
8 years ago, # |
  Vote: I like it -177 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +199 Vote: I do not like it

    I can!

    Also you have really bad karma:

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

      Codeforces police arrived

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -62 Vote: I do not like it

      apologies for my rating_greed

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      the great cheater detector (:

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

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

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    shame on you

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Shame on you !

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it -16 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Maybe he is 3 hour late for the karma train.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Holy molly the solution for div2E is very elegant.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    Participant's output No

    Jury's answer Yes 5 1 3 2 4 2 1 3

    Your output is No

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 called undefined behaviour, so literally anything can happen from there on. Fixing this gets your solution accepted.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Your solution, as described, fails this test:

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

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

    Or as you implemented it (with a weight of 1 for t and 2 for s), this equivalent test:

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

    (should be Yes; your code gives No)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        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:

        7 8
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 7
1 2 3 3

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but why it is giving WA..

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it +7 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +2 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 3   Vote: I like it +3 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 k lakes remaining.

    You can find all lakes 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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you give some place to read about euler tour?

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Hey some basic doubts, The complexity of the algorithm is O(V + E) right?

        And I have a little problem in proving it.

        → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like 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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    foo has only 260 elements, but there may be up to nm / 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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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)

    → Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve E using flows ?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone tell me where i m wrong in my code

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +4 Vote: I do not like it

          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 s and none adjacent to t, 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 both s and t. 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 s and how to connect to t. Pick any one of these components and connect it to both s and t; 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 to s until its degree reaches ds and then connect the rest to t (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.

          → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply