ADDSQURE - Editorial

editorial
, , ,
41

I don’t think this improvisation would be enough to bring down the TC.

42

Check the following code, where the counter is not used to bound the loops in lines 11 and 12.

https://www.codechef.com/viewsolution/38916115

43

Check the following code where the counter is not used to bound the loops in lines 11 and 12.

https://www.codechef.com/viewsolution/38916115

Note that the number of times the statement in the inner loop of the exhaustive search is executed is O(N^2). Suppose that N = 4, and a =[1~2~3~4]. Then, a_{\max} = 4, a_{\min} = 1, and the number of possible distinct distances is 3. The three distinct distance 1, 2 and 3 are found during the first iteration of the our loop, and the bounded search using the distinct distances counter stops without checking more pairs.

44

Could you explain what you did?

46

Thanks for such a great problem and this detailed Editorial!

47

Let us consider case for any 1 set of lines(horizontal or vertical)
The first problem that we are facing is calculating all possible differences that can be obtained by a set of lines.

But here is a small thing, N \leq W+1, so the larger the value of N, the more cramped the lines will be in the space. Hence we start removing differences by consecutive values at a time(a_i-a_{i-1}), and quite a few of all possible differences will be removed beforehand.

However let us think about the worst case, where W=N=10^5, here all differences are possible, so we can just find ( a_i-a_0) and mark those differences. So we get all differences in a meagre O(n) for the worst scenarios. And finally, for the differences we missed, we can check them out by a simple nested loop.

We do this for both sets of lines and then find out the differences that can be made for a but cannot be made for b, our task is to find a line so that we can make the maximum number of these differences for b. Let’s call this set of differences D.
Now we have cannot place lines everywhere, so we can do 2 things-

  1. choose the line from H which can form the maximum number of differences from D.
  2. pick all lines in b and see where our optimal line can be placed. Then will will select the line which can make maximum differences with lines of b

Our answer = (number of differences common in both a and b) + (value obtained from 1 or 2)
Choosing 1 or 2 depends on number of iterations that we have to face if we perform each procedure, and since its O(n^2), the maximum number of iterations can be computed easily.
You can look at my code here.

This isn’t a very perfect approach and so I asked the editorialist if the TC were weak, but then again, who cares about procedure anyway? The target in a contest is to get that green tick.
PS-It would be great if anyone could find a TC where this apparently incorrect code would TLE out.

2 Likes
48

I didn’t find any good resource regarding FFT can u pls suggest some good resource!

49

For the first snippet we are going to replace the inner for loop with bitwise operations. First we can replace the assignment of true by an or operation with the condition of if(vertical[x2]) , so we will get verDiff[x2-x1] |= vertical[x2] . Next we will increase both indices to get verDiff[x2] |= vertical[x2+x1] . And finally turn the for-loop into a bitwise operations using, where you replace the +x1 in the index with a left-shift. We then turned the snippet into the

Can you explain this with an example, how come this

verDiff |= (vertical >> i)

stands for the inner loop, this my first encounter with bitsets couldn’t get my head around it.

50

Let’s do it step by step, so we start with

for (int j = i; j <= width; j++) if (vertical[j]) {
	verDiff[j-i] = true;
}

Now if(b) a = true is similar to a = a or b, because when b is true then a becomes true and when b is false a keeps it’s value. So making this substitution we get

for (int j = i; j <= width; j++) {
    verDiff[j-i] |= vertical[j];
}

Now we substitute j=k+i into the code, which gives the (invalid) code below

for (int k+i = i; k+i <= width; (k+i)++) {
    verDiff[k+i-i] |= vertical[k+i];
}

Now simplifying this we get the (now valid again) code

for (int k = 0; k <= width - i; k++) {
    verDiff[k] |= vertical[k+i];
}

Now we replace the +i in the index with bitshifts

for (int k = 0; k <= width - i; k++) {
    verDiff[k] |= (vertical >> i)[k];
}

And this expression can be replaced with a completely bitwise expression

verDiff |= (vertical >> i)
5 Likes
51

Can you share some good resource for bitset use because it’s all about syntax I think…

52

So in some array number of distinct differences will not exceed amax -amin??

53

i am not able to understand how did the complexity get divided by 64.

54

I understood the method used but how is it optimizing the search .

55

Maybe Bit array - Wikipedia also helps understanding bitsets
As for the bitwise operators in C++: & is and, | is or, ^ is xor and ~ is not, << is leftshift and >> is rightshift. Because the way we index the bits rightshift moves bit k to bit k-s where s is the amount shifted.

56

The first half of my editorial explains the method. In this method we perform operations bit by bit (i.e. a singe boolean at a time). However processors have instructions to perform these operations on 64 bits at a time, that’s where the speedup comes from.

So instead of

instruction 1: true  and false = false
instruction 2: true  and true  = true
instruction 3: true  and true  = true
instruction 4: false and true  = false
instruction 5: true  and true  = true
instruction 6: false and true  = false
instruction 7: true  and false = false
instruction 8: true  and false = false

We do

instruction 1: 11101011 & 01111100 = 01101000

But then for 64 bits (instead of the 8 in this example) at a time

2 Likes
57

Well,the number of distinct differences in any array will not exceed the difference between the maximum value and the minimum value in this array. In the worst case, the upper limit for this number is W and H for a and b, respectively. In other words, this value never reaches O(N^2) even though the exhaustive unbounded search loop that checks all possible pairs would require O(W^2) and O(H^2) sequential execution time, respectively.

58

So how you optimizing that?? In which we have to check for all horizontal line added??

59

I check for each distinct horizonal distance d which does not exist in the set of distinct vertical distances whether adding it to or subtracting it from an existing position b[i] leads to a vertical coordinate y in which no horizontal line exists. If so, a counter for an extra distinct square at y is incremented. The answer to the problem is the number of distinct squares that already exists plus the maximum value in the array of extra distinct squares over all values of y.

60

Thanks for the editorial, it was an interesting problem, really liked the idea and it’s implementation used in it.

61

This was indeed a wonderful question. I didn’t know anything about this bitset thingie until now. It is a really powerful technique I must say and can be used in many places to reduce the time complexity from N^2 to something like N^2/(constant). Thanks a lot for putting up this question.