Flood

"people are able to travel between any two non flooded cells."

If there are 4 islands, do they need to form a connected graph (6 bridges) or only be connected to one another (4 bridges)?

Testing shows the second input line to be blank. Is the data corrupted, or the problem statement incorrect?

There is a chance that I'm wrong, but I've done numerous tests to prove this before complaining.

How are the test cases generated, if I may ask?  The problem also doesn't specify a bound on water depth.

Verified that 2nd line is blank.

Hi,

There should be a blank line after the number of test cases. The sample input should read:

1

3 3
-1 10 -1
10  2 10
-1 10 -1

It will be updated by the admins soon. I'm sorry for the inconvenient.

I would like to know how the input is generated as well.

Will ask the writer to reply as soon as I get in touch with him :)

Hi Stephen,

The test cases are generated randomly, with a few handmade special cases. That's all I can say.

As you may guess by submitting a naive solution, there are 22 test cases.

My algo is working absolutely fine on test cases containing 200*200 cells.....still getting runtime error sigsegv!

I don't know why...

ok...now it worked

but it's showing 1pts in submission list while in the rank list it's only 0.595 pts....why??

admin plzz reply

The 1pts is incorrect. I believe your point is 18.919801/ 22 (max points). Admins will look at the issue.

We still need more info on how the input is generated; that is a vital bit of information in challenge problems (as discussed many times in the past, until Codechef started providing it every time).

Randomly how? Do you use a fixed proportion of -1 squares, and then choose random numbers between 1 and x for the remainder? If so, what proportions are used, and what is x?

Without input generation information, challenge problems become a matter of randomly guessing what the author had in mind, which isn't good. (Hand picked cases aren't normally a good idea for the same reason - if they aren't random, someone can guess how you picked them and hardcode that case into their code).

Here's some information on how the test case is generated:

- For each map, a distance P is handpicked. Then we generated some islands with minimum distance between each other at least P.

- The remaining flooded cells have depth randomly generated between (1,R) where R is a handpicked range varied for test cases.

I think that the info of how the test cases generated may help, but shouldn't help much, at least in this problem, a good program than can cover many cases can score well.

I'm not sure that this information is necessary, but watch out for special cases in which there is an exact algorithm, for example when there are no more than two islands.

"each island consists of the cells that can move around one another but cannot move to cells in different islands" - what does this mean? cells move around means?

Basically it means each island is a connected component of cells, if you like graph terminology.

Writer , I understood that this is what implied but still the choice of words confused me. thanks

You're right, the wording is a bit confusing. Apologize for that!

wirter, i have doubt

Do our program output should exactly matching with actual output

as point depend on score

and score is T/H

please clear my doubt

@writer

please reply

Of course your program needs not to output exactly with actual output. In fact, there's no "actual output".

Your program only needs to output any correct answer.

@writer

can u plz clarify the output format i m not getting it

do we have to leave one blank line after every test case output

So is there something wrong with the scoring system?

My naive program got 1pt.

And I also want to know , can there be some change of DATAs?(Is this the final data?)

Technically you need to leave one blank line after each case's output, but those which forgot should be still fine as the judge program won't take blank lines into account.

The test data is final.

we need to use the minimum number of clay units, right? so the value of T has to be minimum. but the score is given by T/H which means, the more the value of T the higher the score. am i missing something?

i know i'll feel stupid when i read the answer!

No, you don't need to use the minimum number of clay unit. You just need to print a solution which makes all islands connected (the fewer number of clay units you use, the better).

... And the word score in this problem is confusing. A lower score is better in this problem; you will get best_score / your_score points.

Hi, Adrian. But doesn't T/H indicate that my score will be higher for a higher value of T? Then how is it better to use fewer clay units? In the given test case, for instance, if I were to fill all cells with a water depth of 10, the value of T would be 40 and my score would be 40/42 which is greater than 1/21.

OK, understood. Thanks a lot!

can second line of output become 0.

Can i know the maximum value that depth can have ?

@ Writer ,Stephen Merriman

can u please tell what is output format becoz i m getting wrong answer

as it is commented by Writer that

"Of course your program needs not to output exactly with actual output. In fact, there's no "actual output".

Your program only needs to output any correct answer."

please reply

The output format is clearly described in the problem. If you are getting wrong answer that means your answer is incorrect; ie you haven't connected all the islands.

can we output the index of the cells in any order?

Yes.

@Admins

Why is one of my recent submissions in which is score 0.019 doesnt show in the list on the main page?

The whole thing itself is crapped up. I got 0.86 .. but it shows 0.838 in the Rank sheet !

The score on the my submissions page is incorrect (and has been for several contests). The one on the main contest scoreboard is correct.