Hd7's blog

By Hd7, history, 5 years ago, In English

This is the link of problem: D. White Line.
For the best i understand up to now, let's focus on row.
I will base on the range [l;r] each row of black to determine whether which cells that we click will erase this row or not. These cells are in the rectangle from $$$(l1, l2)$$$ (top left) to $$$(r1-1, r2-1)$$$ (bottom right), $$$l1, l2, r1, r2$$$ is defined in the code i extracted from @kcm1770's solution.

         for(int i=0; i<n; ++i) {
		int l=0;
		while(l<n&&s[i][l]=='W')
			++l;
		if(l>=n) {
			++b[0][0];
			continue;
		}
		int r=n-1;
		while(~r&&s[i][r]=='W')
			--r;
		if(r-l+1>k)
			continue;
		//i-k+1, i
		//r-k+1, l
		int l1=max(i-k+1, 0), r1=i+1;
		int l2=max(r-k+1, 0), r2=l+1;
		++b[l1][l2];
		--b[l1][r2];
		--b[r1][l2];
		++b[r1][r2];
	}

I see a lot of people do the same approach. I don't know how they come up with the way set ++ & -- like that. This is all of magic for me. Could you tell me about some similar problems using that or some concepts involve.

  • Vote: I like it
  • -8
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved the problem using the approach that was given in the editorial. Here is my code: 58682265 I added comments for clarity. I hope this will help you.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you very much. Your code looks so easy to read.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    Not really related, but as a trick to avoid typos / reduce coding, you can write a helper function to compute the answer for only the rows, then call it on the transposed array to get the answer for columns. (Example: 58636000)

    It's really easy to make mistakes when rewriting a whole block of code switching rows & columns, otherwise.