11451 - Water restrictions

[jurajz]

>>>>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]

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.

[jurajz]

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]

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

[andmej]

I tried brute force but got Time Limit Exceeded. How did you do it?

[nymo]

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...

[andmej]

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]--;
    }
  }
}

[nymo]

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

[jurajz]

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).