11451 - Water restrictions

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

11451 - Water restrictions

Post by andmej » Wed May 21, 2008 4:01 pm

What's the output for this input:

Code: Select all

1
10
1
5
0
0
Thanks.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

nicolai
New poster
Posts: 5
Joined: Fri May 16, 2008 10:38 pm
Location: Ukraine / Germany

Re: 11451 - Water restrictions

Post by nicolai » Wed May 21, 2008 10:20 pm

The answer is:

Code: Select all

0

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11451 - Water restrictions

Post by andmej » Thu May 22, 2008 4:48 pm

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

I believe the answer is 1.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

nicolai
New poster
Posts: 5
Joined: Fri May 16, 2008 10:38 pm
Location: Ukraine / Germany

Re: 11451 - Water restrictions

Post by nicolai » Thu May 22, 2008 9:42 pm

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.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11451 - Water restrictions

Post by andmej » Thu May 22, 2008 9:46 pm

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

nicolai
New poster
Posts: 5
Joined: Fri May 16, 2008 10:38 pm
Location: Ukraine / Germany

Re: 11451 - Water restrictions

Post by nicolai » Thu May 22, 2008 9:59 pm

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.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11451 - Water restrictions

Post by andmej » Thu May 22, 2008 10:17 pm

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

nicolai
New poster
Posts: 5
Joined: Fri May 16, 2008 10:38 pm
Location: Ukraine / Germany

Re: 11451 - Water restrictions

Post by nicolai » Thu May 22, 2008 11:41 pm

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

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 11451 - Water restrictions

Post by jurajz » Thu May 22, 2008 11:49 pm

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 :D

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Re: 11451 - Water restrictions

Post by ardiankp » Fri May 23, 2008 5:21 am

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.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11451 - Water restrictions

Post by andmej » Sat May 24, 2008 10:39 pm

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?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Re: 11451 - Water restrictions

Post by rio » Sun May 25, 2008 4:50 am

andmej wrote: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

User avatar
Rupak
New poster
Posts: 8
Joined: Mon Jan 15, 2007 6:53 am
Location: Bangladesh

Re: 11451 - Water restrictions

Post by Rupak » Sun Jun 15, 2008 8:21 am

:( plz .. send more I/O :(
_______________________________________
http://acm.uva.es/problemset/usersnew.php?user=6114

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 11451 - Water restrictions

Post by jurajz » Sun Jun 15, 2008 1:24 pm

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
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11451 - Water restrictions

Post by mmonish » Sun Jun 15, 2008 7:36 pm

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

Post Reply

Return to “Volume 114 (11400-11499)”