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

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 8:15 pm

mmonish wrote:>>>>jurajz
some of ur testcases are not valid.
Here maximum number of sprinklers is 10.
Hi mmonish,

you are right. I overlooked this restriction. I fixed this mistake. Here are another 30 random-generated test cases.

Input:

Code: Select all

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

Code: Select all

5
10
9
3
15
14
3
11
5
16
6
13
13
3
6
10
7
10
3
15
3
3
11
9
10
12
8
4
16
3
Hope it helps.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 11451 - Water restrictions

Post by nymo » Sun Jun 22, 2008 5:16 pm

nicolai wrote:According to my program, the solution is 19 with d = [ 1, 2, 1, 0, 1, 2 ].
With these, positions that are irrigated are: 1, 3, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18 and 19. total: 14 locations. Why the answer is 19?

I 've misunderstood the problem... Can you please tell me what the problem wants and how above solution produces the desired answer 19? Thanks in advance.
regards,
nymo

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

Re: 11451 - Water restrictions

Post by jurajz » Sun Jun 22, 2008 9:26 pm

nymo wrote:
nicolai wrote:According to my program, the solution is 19 with d = [ 1, 2, 1, 0, 1, 2 ].
With these, positions that are irrigated are: 1, 3, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18 and 19. total: 14 locations. Why the answer is 19?

I 've misunderstood the problem... Can you please tell me what the problem wants and how above solution produces the desired answer 19? Thanks in advance.
According the problem description, one sprinkler on position x with current flow c will irrigate positions between x-c and x+c. For example, if sprinkler is in position 5 and his flow is 3, that sprinkler will irrigate positions between 5-3=2 and 5+3=8, that means positions 2,3,4,5,6,7 and 8. It seems, that you don't assume, that sprinkler irrigate his own position. The fact is, that sprinkler will irrigate it's own position too.

One exception - as was discussed above, if current flow of sprinkler is zero, no position are irrigate.

In example, number of locations is 20. Sprinklers are on positions 2,6,10,11,13,17 and the flows of sprinklers are 1,2,1,0,1,2 respectively.

First sprinkler on position 2 will irrigate positions between 2-1 and 2+1, i.e. 1,2 and 3.
Second sprinkler on position 6 will irrigate positions between 6-2 and 6+2, i.e. 4.5.6.7 and 8.
Third sprinkler on position 10 will irrigate positions between 10-1 and 10+1, i.e. 9,10 and 11.
Fourth sprinkler on position 11 will irrigate nothing.
Fifth sprinkler on position 13 will irrigate positions between 13-1 and 13+1, i.e. 12,13 and 14.
Sixth sprinkler on position 17 will irrigate positions between 17-2 and 17+2, i.e. 15,16,17,18 and 19.

Total 19 locations are irrigate, 1-3 from sprinkler 1, 4-8 from sprinkler 2, 9-11 from sprinkler 3, 12-14 from sprinkler 5, 15-19 from sprinkler 6. Only position 20 is not irrigate.

Hope after this explanation it is clear ;)

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 11451 - Water restrictions

Post by nymo » Mon Jun 23, 2008 5:21 pm

Thanks. got ACC. but my dp idea was not correct, ACC with bruteforce...
regards,
nymo

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 » Mon Jun 23, 2008 5:26 pm

I tried brute force but got Time Limit Exceeded. How did you do it?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 11451 - Water restrictions

Post by nymo » Mon Jun 23, 2008 7:08 pm

I 've precalculated the cover of the sprinklers using bits. bits denote positions covered by the sprinkler. int is enough as total position is at most 20.

Code: Select all

void Cover(int S)
{
	int i, j, temp;
	memset(cov, 0, sizeof(cov));
	
	for (i=0; i<S; i++)
	{
		for (j=1; j<=m[i]; j++)
		{
			temp = cov[i][j-1];
			temp |= 1<<pos[i];
			temp |= 1<<(pos[i] + j);
			temp |= 1<<(pos[i] - j);
			cov[i][j] = temp;
		}
	}
}
Then I can easily find the cover using bitwise OR. then check how many bits are set :) to find the positions covered by the sprinklers. Hope you will find this helpful...
regards,
nymo

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 » Tue Jun 24, 2008 1:59 am

I'm using bitwise operations too.

Here's my backtracking code:

Code: Select all

void backtrack(){

  for (int i=0, sum = 0; i<S; ++i){
    sum += n[i];
    if (sum > C) return;
  }

  int mask = 0;
  for (int i=0; i<S; ++i){
    if (n[i] > 0){
      for (int j=pos[i]-n[i]; j<= pos[i]+n[i]; ++j){
        mask = mask | (1<<j);
      }
    }
  }
  
  best >?= __builtin_popcount(mask);

  for (int i=0; i<S; ++i){
    if (n[i]+1 <= m[i]){
      n[i]++;
      backtrack();
      n[i]--;
    }
  }
}
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 11451 - Water restrictions

Post by nymo » Tue Jun 24, 2008 7:50 am

andmej, I 've sent you a pm...
regards,
nymo

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

Re: 11451 - Water restrictions

Post by jurajz » Tue Jun 24, 2008 11:24 pm

I solved it with bruteforce too ;) For my solution are important small values for number of sprinklers (10) and maximum total flow (10). Although I am 37th of 37 solvers, my time is not horrible (2.470 seconds, time limit for this problem is 5.000 seconds).

Post Reply

Return to “Volume 114 (11400-11499)”