fcspartakm's blog

Codeforces Round #375 (Div. 2)
By fcspartakm, history, 8 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #375 (Div. 2). It'll be held on Monday, October 3 at 14:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by me and Mike Mirzayanov (MikeMirzayanov).

Great thanks to Gleb Evstropov (GlebsHP) for helping me preparing the contest and for the idea of the most tricky problem, which was specially made for this round, to Tatiana Semenova (Tatiana_S) for translating the statements into English and to Nikolay Kalinin (KAN) for writing solutions and very helpful advices.

It will be a little unusual round — you will be given six problems and two and half hours to solve them.

Score distribution 500-1000-1500-2000-2500-3000. Good luck everyone!

UPD Editorial

  • Vote: I like it
  • +182
  • Vote: I do not like it

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

An unusual round with tricky problem. Programmers be like "Brace yourself, storm is coming!"

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

i wonder which question is going to be tricky :D

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

    If problem C or D are tricky then you won't be able to solve them.

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

      if you are speaking about me then speak for yourself, you are not even rated.

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

Tfw CF rounds are getting earlier and earlier, from starting at mid-night (00:35) to starting at supper's time (19:35).

Poker face

Good luck for everyone that's joining.

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

hope the translation is good enough to understand clearly, unlike last round.

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

    I couldn't understand what Problem C was :( although I solved D. I should have attacked D earlier :(

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

What is the reason behind setting contest time so early?

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

    Maybe because the unusual early time is becoming usual, lol.

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

    Maybe because of this
    This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov.

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

you only needed one more problem to make contest for both divisions. poor div.1

EDIT : It seems downvotes are coming :(

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

    this contest is prepared and rated for div-2 only

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

      What you said is exactly the point! I think you misunderstood. Sorry of my bad English.

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

game time is good for china

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

salam

what does tricky means?

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

"Tricky problems" --> Hacks contest xD

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

Finally CodeForces loaded for me :( But alas around 40 minutes are gone :(

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

I cant even understand the problem statement for C!

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

What is the problem for D? I keep getting WA on test 7.

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

    Woah, I almost told you the answer, thinking that this is a 2hr round and it had already ended.

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

    when i sorted my vector in increasing order i got wa and sorting in decreasing order got pretest passed

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

Only a few numbers of hack wow!!!

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

Poor English #C..

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

Problem statement for C was too difficult to understand

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

    I spent some time on solving C, then decided to solve D first, and then returned back to C. What do you do if you do not have full understanding of a problem?

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

It was an AMAZING AND WONDERFUL contest! Problems were really interesting and pretests were strong enough.

Thank you fcspartakm

EDIT : according to zscoder pretests were strong enough for A to D!

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

    "Pretests were strong enough"

    I don't think this is the case for E and F......

    My random greedy solution passed E and F on pretests. (Luckily system tests were indeed strong enough)

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

    I agree!! The best contest!! (even though i didnt do too well...:( )

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

I see someone has used -1 index to access array. And he passed the test. Is it possible?

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

    What language did he use?

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

    Yes! I tried it before in c++ and it worked!

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

      c++

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

        well, in C++ array is represented as pointer to begin of it. All operations with arrays are actually operations with pointers and arithmetic of pointers.

        So, if you get access to p[i], you actually get access to p+i. If i==-1, you just get access to p-1 segment of memory. Yes, it will be not working when p+i points to address with too low or too hight values — for example, -1000 or even 0.

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

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

    RTE on 13 ... But I'm not sure in what situation I'll acess invalid position since everytime I get to a border cell in the first floodfill I'll stop it and wont't get to any neighboor and my second floodfill never access border cells since I only call it on lakes.

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

      If you insert an extra border of water(`.'), presenting an ocean, around 4 sides of the area, there will be no runtime errors as "i" can go from 0 to n+1, and j from 0 to m+1. First of all, visit the (0,0) which is the ocean, then proceed with the main area. http://codeforces.net/contest/723/submission/21156099

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

.

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

how to solve C?

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

    answer is n / m

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

    Alternate solution to O(N2) brute. Binary search on answer, let us say current value to test is X, it is possible to get this value if there are elements that are either  ≤ M and have occurrences more than X. Elements  > M are always replaceable. Once you know the answer, simply change the minimum number of values in array. NibNalin has implemented this and got AC: 21146185

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

    (Some comment mentioned this solution before me) You can solve it using binary search to get the maximum minimum element,

    if band > m or if totalsongs of band > MID , you can take from it .

    else you must give songs , if taken >= given , return 1;

    next step is to just swap elements in the array until all bands from 1 to m reach MID;

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

Once again, very nice problemset! I really enjoyed the contest, although I couldn't do D — my approach was with DSU, however there's some tiny mistake in my code that I didn't find...

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

When you submit in the last couple seconds of the contest only to get WA because you put "YES" rather than "Yes"... sad times.

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

Is div2E a flow-related question? The small (n,m) constraints looks suspicious to me.

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

    it should be impossible,because people who passed just used 15ms with less than 10kb

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

pls help me with D

I got into many dfs but failed...

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

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

misread D as transforming land to water to reduce the lake number, and struggleed for 90 min to write a complicated solution and found I was so stupid...

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

quick editorial .

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

    But we can't open it yet. :/

    (or at least I can't. It says "not allowed")

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

      aaaand editorial removed. ¯_(ツ)_/¯

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

Maybe my English is too poor. Can't understand problem C at all.

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

    I spent 30 min understanding it too.

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

      You can see the examples first which can help understand better.

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

Will system test start right away? Or With some delay? Thanks in advance

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

The quick editorial makes this contest best ever

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

It's the second time that I come up with a solution to a problem several minutes after contest ends... sad :(

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

    Look at the bright side you did come up with a solution!

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

in problem D: "and it's impossible to add one more water cell to the set such that it will be connected with any other cell"

Before clarification, I overthink that statement and after complicated process implying that the river can't have hole, can't fork, and can't turn, LOL. Thanks for fast clarification btw, save me much time :)

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

It took lot of time to understand problem statement for C. Because of this I could not implement problem D :(
The contest has nice set of questions. Hope to see more rounds from fcspartakm
EDIT Now problem C fails System Test. I think I should have given time to problem D

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

It costs me much time to understand the mean of the Announcement,and i just realized that it is no use to me after passing the PTs...I think the most difficult part for me to solve the problem C is the EN. (:P)

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

I know that it isnt related to this contest, but I am wondering my rating is 1318 pupil even though i got specialist at my first game i am 14 years old and i honestly wonder if i am doing good of i should improve my skills to meet standards?

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

Problems are very interesting, hope more rounds from fcspartakm!

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

Is anyone read statement of D and think statement require replace land by water instead of replace water by land like me ?? f*** my very bad E !! PS : Can anyone solve problem D like my mistakes =))

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

How to prove greedy works for E?

Randomly taking edge and orienting all edges to satisfy nodes with even degree gets AC. How to prove this is correct? Also, if this is indeed correct why is constraint on N so low? I got misled into thinking solution is something via MCMF. Example: 21156793

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

    Maybe the low constraint is just to distract us from thinking about a greedy approach lol

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

    Why do you have a separate account for commenting ?

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

Pls help me, problem D

I got WA on test 7:

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

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

IS all python solution for D get RTE because of recursion depth limit reach ?

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

Very hard to understand problem C. I wasted about 30 mins after it. Then let it go, solved D. Now I regret why I did not read problem D without wasting time after problem C. -__-

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

Why aren't editorials written before the contest and published as it ends?

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

I just changed an array's size from 1000 to 2000 in problem D and got AC after the contest :((

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

    Why do you need an array of that size ? Can I see your submission please ??

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

      To see someone's submissions, go to user's profile Dabagh, and click the SUBMISSIONS menu item.

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

Nice problemset ... Specially C & E ... overall Nice contest waiting for rating change !!!!

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

the idea of the most tricky problem which one was the tricky one ?

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

i'm so hungry when i programed

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

The pretests for F may be too weak. With a wrong character in my program, it got pretest passed and pass 47 tests. So to me, it's a little bit surprising to see so few hacks on F after finding such a silly mistake in a pp program.

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

    Indeed, I also did a silly mistake, I was using two variables ct and dt. ct was the counter of how many edges I have used thus far, and dt the upper bound given in the problem. I accidentally increased dt by one when adding an edge in one case and it still got to test 48.

    After the contest I was able to fix the bug, it would've meant a good rating increase in my case. But to a certain extend it's our fault, Even if we get Pretest Passed we are all aware that there may be bugs in our code. I think the reason why you and me didn't get hacked is that not many people solved it, and a vast majority of the ones that did were red/yellow coders that got in for fun and not rating.

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

I found problem C's writing quite poor.

What was the purpose of writing "Polycarp likes bands with the numbers from 1 to m, but he doesn't really like others."? Was it to confuse people???? Why, if Polycarp does not like numbers greater than m, are there playlists with such numbers (test case 7)?

This is totally ambiguous and this should have been made explicit.

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

    Same argument! If he did not like others then why should they be included in the playlist?

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

My solution for C got one line in wrong ordered which should give wrong answer to many of the tests but somehow passed the pretest then system test got me. :( Now I cannot tell whether I'm extremely unlucky or extremely lucky. Xp

//wrong one which pass the pretest
a[i]=*needer.rbegin();
needer.pop_back();
give[a[i]]--;
//right one that i figured out after the contest
give[a[i]]--;
a[i]=*needer.rbegin();
needer.pop_back();

FEELSBADMAN

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

My fortune is that I didn't read D statement. It was clear from input/output and clar.

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

Problem C's statement is so silly and confusing i couldn't even understand it till the end of the contest .

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

This is a very, very, very exciting and thrilling round!

C is failed for...typo?(confirmed, "m" should be "per")

E is failed for missing a if statement in dfs process to judge the starting point of circle.

UPD: F is only one statement away to get Accepted (I missed a statement like "a--").

The rating, certainty, will drop. But I have got so much fun.

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

    My problem F was one submission away to get Accepted ! In final minutes I tried to submit it but Internet connection failed !! After system test I submitted my code and I just wanted my solution to get a wrong answer and guess what, it is an Accepted :(

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

Horrible problem statement for C. Why are bands numbered more than m included in the play list if he doesn't like numbers > m?! I solved the question in 1h10m then got a test case for which my solution printed values greater than m.

so I tried to fix that for the rest of the contest without even trying D question.

Had the question been clear I could've used the remaining time to try D. Just pathetic problem statements.

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

    Yes,he doesn't like numbers>m.This is why he want to change the playlist.

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

    Same Argument!

    Why does he even include bands with > m if he doesn't like them? :(

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

      Your first goal is to make every band you like appear at least k times (k is the maximum min-value of bi, and should be ceil(n/m)).

      You should assure the first goal, and then get the minimal times of operations.

      In some cases, you can let go some music from the band you don't like to make your times of operations smaller.

      Take this example:

      n = 5, m = 2, k = 2, original list: 998, 1, 1, 2, 2.

      You have already assured the first goal. Then you need to get minimal times of operations. And clearly you can just let go 998.

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

547D has the same idea with problem E.(But 547D have very different statement.) Everybody can try it. XD

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

That's an extremely exciting party!

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +2 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.

Please take a look at these submissions: my submission1 my submission2 my submission3

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 +3 Vote: I do not like it

I first misunderstood problem D and thought that I'm allowed to change " * " sign to ".". I found this problem interesting but couldn't come up with any solution.

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

    My thoughts: calculate the minimal distance between each pair of lakes, and we get a complete graph with O(n2) vertices and O(n4) edges. Then the task will be to connect the vertices into k parts with these edges, with minimal cost. We apply a Kruskal's algorithm but stop after initial_lakes - k operations, thus we get a spanning forest with k trees. The overall complexity will be but with a rather small constant factor since the number of initial lakes can be at most n2 / 4.

    590C - Три государства This problem uses a similar idea FYI.

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

      Maybe there are some details in it. For instance,here is a graph.

      - *****
- *.*.*
- *.*.*
- **.**
- *****

      There are 3 lakes now,but if k=1,then the best answer is to change the block in the middle. However,the distances between the lakes are all 2.

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

        My fault - -||… The approach for handling this in 590C is doing a BFS from each cell but it doesn't seem to work with tens of lakes here, so the algorithm above doesn't work for all cases… I feel this is somehow linked to the rectilinear Steiner tree problem so will it be NP-hard?? I have to think it over, thanks for pointing out.

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

          Yes I also think that it's similar to rectilinear Steiner tree problem. So yes, may be it's NP-hard.

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

It's a perfect time,especially for the Chinese! It's the first time that there's even no hacks in my room!How tricky!

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

Hi! I tried to attempt 375D, and this is my solution: http://ideone.com/VtXhW5

I've tried really hard to debug it and gives strange outputs on ideone and something very different(and coloured) on another online IDE. Could someone please help me out?

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

    The bug that’s causing memory corruption is probably in line 59: you meant to compare a[i][j]=='.', but you’re actually assigning a[i][j]='.'. This probably leads your program to see parts of the ocean as lakes (because it hits previously visited cells before it has a chance of hitting the edge of the grid) and then write past the end of the a and mark arrays in ffill.

    Also, why are you iterating and searching through coordinates 0 to n inclusive and 0 to m inclusive? You visit coordinates that simply do not exist. This does not cause memory corruption, because your arrays are large and fully initialized; but a[i][m] and a[n][j] are always equal to '\0', which means you’ll never call checklake on these coordinates (except in line 61 until you fix the assignment bug in line 59), which means you’ll never hit the x==n||y==m condition in line 14, and so your program will think that any piece of ocean that touches the bottom and right edges of the grid but not the top and left edges is actually a lake and therefore produce a wrong answer. Change this condition to x==n-1 || y==m-1 and change all inclusive loop ranges to exclusive.

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

      Thankyou so much! The assignment operation was a very silly mistake. I've changed that, and I'm getting a wrong answer now. http://codeforces.net/contest/723/submission/21189917 I've realised that there's two . connected to the ocean that my code is still covering and considering that as a lake which is giving me a wrong answer. When scanning through the second row, the code should return lake as false when the call for checklake(x,y-1) would give false but the visited array already has it filled, and it doesn't check for that. What would be the best way to handle this?

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

        Ah. You shouldn’t return immediately after setting lake=false. By doing so, you miss the rest of the lake. Instead, you’ll need to add an extra check to make sure you don’t go past the edge of the grid, i. e. if (x<0 || y<0 || x>=n || y>=m) return; at the very top of checklake.

        In this test, when you’re scanning the second row, you don’t call checklake(x,y-1) at all! visited[x][y-1] is already true, as you made it so when you scanned the first row.

        → Reply