11451 - Water restrictions

[andmej]

What's the output for this input:

Code: Select all

1
10
1
5
0
0

Thanks.

[nicolai]

The answer is:

Code: Select all

0

[andmej]

Are you completely sure? That's what your accepted program output?

I believe the answer is 1.

[nicolai]

Well, i'm pretty sure.

In this testcase you have a garden of length 10 and a single sprinkler at position 5 with maximum flow 0. Your total water restriction is also 0.
In that situation you can obviously irrigate only 0 positions.

[andmej]

From the problem statement:

If the current flow is set to c, then the sprinkler will irrigate between c positions to its left and c positions to its right.

The flow of the unique sprinkler is set to 0, which means it will irrigate between 0 positions to its left and 0 positions to its right, included. That is, it will irrigate between [5-0, 5-0] = [5, 5]. And that interval has exactly one piece of land.

Try to build a solution for the last case in the sample input.

[nicolai]

In my accepted program i have assumed, that sprinkler with current flow set to 0 irrigates 0 pieces of land.
So i guess the problem's description is not formally correct.

[andmej]

According to your accepted program, what would be a solution for the last input case?

Code: Select all

1
20
6
2 6 10 11 13 17
7
1 4 3 2 4 3

I know the output should be 19, but how should I distribute the allowed flow of 7 between the sprinklers?

I think a possible solution is d = [1, 2, 0, 1, 0, 3] where d is the flow allowed for the i'th sprinkler, but it assumes that a sprinkler with flow 0 irrigates its own position.

[nicolai]

According to my program, the solution is 19 with d = [ 1, 2, 1, 0, 1, 2 ].

[jurajz]

Another WA during contest because of not so correct problem statement I agree with andmej, from problem statement, if unique sprinkler is on position X, and c=0, then it will irrigate positions from X-0 to X+0, that means one position (position X), not nothing. I fixed my WA program from the contest - I only changed, that if c=0, that no positions is irrigate. And have AC... So thanks to andmej and nicolai for this discussion

[ardiankp]

And also there're testcases with maximum capacity > 10...

I got tons of WA because of that, and then several TLE for checking which input constraint is violated.

[andmej]

I've tried backtracking to solve this problem but I'm getting time limit exceeded.

Should I prune the search or is there a more efficient way to solve this problem?

[rio]

I've tried backtracking to solve this problem but I'm getting time limit exceeded.

Should I prune the search or is there a more efficient way to solve this problem?

How about DP?
-----
Rio

[Rupak]

plz .. send more I/O

[jurajz]

Hi Rupak, there are thirty test cases, randomly generated (restrictions from problem description are hold).

Code: Select all

30
10
5
3 4 5 7 9
6
2 1 4 1 1
17
6
3 4 9 11 14 15
2
2 3 2 1 2 1
20
16
2 3 4 5 6 8 9 10 11 12 14 15 16 17 18 19
7
1 2 2 1 1 4 1 5 5 3 1 5 2 1 2 1
11
1
9
5
1
5
3
2 3 4
5
1 1 1
15
11
3 4 5 6 7 8 9 10 11 12 13
7
2 2 4 1 3 2 4 3 4 2 2
7
2
3 6
7
1 1
19
16
2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18
8
1 1 1 2 5 5 4 3 1 1 5 3 3 1 2 1
8
4
2 3 4 5
6
1 1 3 3
8
1
2
8
1
10
1
8
9
1
19
16
2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
9
1 1 4 5 5 1 2 1 4 1 5 5 2 3 1 1
12
4
6 8 9 10
6
3 4 2 1
11
5
2 4 6 8 10
7
1 2 4 3 1
17
5
2 6 7 12 15
6
1 4 2 1 2
12
2
5 8
8
2 3
14
3
5 9 12
9
4 3 1
10
7
2 3 5 6 7 8 9
6
1 2 1 4 1 1 1
7
2
3 6
4
2 1
14
2
4 8
8
3 2
7
3
3 4 5
5
1 1 2
9
1
6
6
3
20
1
5
10
3
5
1
3
7
2
6
4
2 3 4 5
3
1 2 1 1
10
7
2 4 5 6 7 8 9
1
1 1 4 1 1 1 1
6
1
4
5
2
17
6
4 6 11 13 14 15
5
3 5 4 3 3 2
7
1
2
2
1
19
15
2 4 5 6 7 8 10 11 12 13 14 15 16 17 18
9
1 2 2 2 4 2 2 3 3 1 3 1 2 1 1

My AC program gives:

Code: Select all

10
6
20
3
5
15
6
19
8
3
3
19
9
11
15
9
13
10
7
10
6
7
7
5
6
3
5
13
3
19

Hope it helps.

[mmonish]

>>>>jurajz
some of ur testcases are not valid.
Here maximum number of sprinklers is 10.