July CookOff Contest Problem Editorials |
1) Head Office Building (written by AnhDQ)
This problem will be easier to solve if the square needed has edges paralleled to the axes. So the task now is transforming this problem to that. To do it, we do “rotate” the axes by an angel of 45°, calculate the new co-ordinates and solve the problem like doing with the squares having edges paralleled to the new axes. All the converting formula are simple!
Complexity: O(w×h).
2) Ripple-Carry Adder (written by Zac Friggstad)
First, let f(i) denote the number of flipped bits to count from 0 to 2^i. This can be easily shown to be 2^{i+1}-1. Now, the number of bits flipped to count from 0 to n is simply the sum of f(i) over those i for which the i'th bit is 1. Finally, the number of bits flipped when counting from a to b is just the number of bits flipped couting from 0 to b minus the number flipped when counting from 0 to a. This is all standard fare and seems easier than most "easy" problems on CodeChef.
The interesting part of the question that takes some minor insight is in how to actually compute the sum of the f(i) values. The numbers are up to 100,000 bits long and each f(i) is about i bits long as well. Doing this naively results in a time limit error. The trick is that f(i) is simply represented by a string of i+1 1 bits (e.g. f(2) = 111 in binary). We can add all of the f(i) "at the same time" in one linear time algorithm in the following manner.
Say the number we are counting to is B. Let K be the number of 1-bits in the binary representation of B = b_{n-1}b_{n-2}...b_1b_0. Then, we know that the least significant bit of the answer will just be the parity of K since K bits are added to this position. The carry of the K bits is just floor(K/2). If b_0 was originally 1, then subtract 1 from K since f(0) will not contribute to future positions in the answer. The number of 1-bits to be added to the second least significant bit of the answer is then the carry plus this new value K. Continue this process of adding the carry plus the current K value to the next bit position and update the carry to be the floor of half of this value. Subtract 1 from K if the position i had b_i = 1 since f(i) will not contribute to higher-order bits.
For illustration, say B = 110101 so the answer is f(0) + f(2) + f(4) + f(5) = 1 + 111 + 11111 + 111111. The final answer is 1100110.
Writing these f(i) values in binary on top of each other we see:
111111
011111
000111
000001
The least significant bit has 4 1s contributing to it. The carry from adding these 4 is 2 so the second least significant bit has 3 1s plus the carry of 2 contributing to it. Since the total contribution to this position is 5 (which is odd), then the second bit of the answer is 1. The carry from this is floor(5/2) = 2. Carrying this to the third position yields an answer of 1 with a carry of 2 again...
3) The Black and White Knights (written by Varun Jalan aka Syco)
In the general case, there are a couple of types of positions on the board : Positions from which a knight attacks two squares on the board, those from which it attacks three squares, and so on. So we just need to count the number of squares from which a knight would attack exactly X squares, and add 2*N*M*(N*M - X - 1) to the answer. We multiply by 2 because the knights are distinct. Cases with n = 1,2 and 3 might have to be handled seperately depending on how you prefer to think of the problem. Finally note that the answer for the larger test cases do not fit in a 64 bit integer, and hence simple big integer operations are needed.
Comments
Problem 3 has very simple
Problem 3 has very simple solution without any cases. The answer is calculated by the following formula
res=m*n*(m*n-1);
if(m>1 && n>2) res-=4*(m-1)*(n-2);
if(m>2 && n>1) res-=4*(m-2)*(n-1);
I didn't figure out completely solution of Problem 2 but I think I have a simpler solution
res = ( 2*b - S_2(b) ) - ( 2*a - S_2(a) )
where S_2(n) sum of binary digits of n.
In The Black & White Knight
In The Black & White Knight problem I solved this problem in java many times but I got wrong answer message.
After contest I saw some python solutions then I found that my program's logic is same which I written in Java. This java program was running properlly on my machine.
Then I written same program with same logic && variables in Python now I got correct answer but for Java I am getting wrong answer, So please tell me what is the problem for java code?
*comment edited by admin*
I got my mistake, due to
I got my mistake, due to integer range in Java i got wrong answer, sorry for posting problem.
For problem 3, I used the
For problem 3, I used the following formula:
if (m=1) res=n*(n-1)
else if (n=1) res=m*(m-1)
else res= (m*n*m*n) - (m*n) - 4*((m-2)*(n-1) + (m-1)*(n-2))
I got correct answer for all the given test cases (and also for few of my own) but I got wrong answer.
And I used BigInteger
And I used BigInteger class...
Can someone explain the
Can someone explain the solutions for Problem 3 and Problem 2 which Anton Lunyov posted above in a bit more detail? How do I arrive at them?
For Problem 3, notice that if
For Problem 3, notice that if two knights attack each other then they are placed at two opposite corner cells of some 2x3 or 3x2 rectangle. Now every placing of a 2x3 or 3x2 rectangle on the board gives 4 possible pairs of positions for the knights.
As for Problem 2, suppose you want to sum up the values of f(i) = 2*(2^i)-1 for all i such that the i-th least significant bit of N is 1. Notice that the sum of all 2^i is just N; now, adding all 2*(2^i)'s and -1's separately, it's easy to arrive at 2*N-bitCount(N).
@Gennady Korotkevich Thanks a
@Gennady Korotkevich
Thanks a lot.
@Gennady Korotkevich Thanks,
@Gennady Korotkevich
Thanks, now I understand it.
If they post an editorial
If they post an editorial like this for other contests also.. we will love codechef...
They've been posting
They've been posting editorials for all contests since April..
@Stephen Merriman:You said
@Stephen Merriman:You said they have been posting editorial every month .I was trying to find the JULY10 monthly contest's editorial but I could not find any.Would you kindly give the link to it.
It's under Discuss - Wiki -
It's under Discuss - Wiki - Editorials. (They're been linking to them from the blog posts).
@Anton Lunyov:I was trying to
@Anton Lunyov:I was trying to understand your code for problem1 .Would you clarify what you are precomputing in matrix d1 and d2?
@ishan dutta in my program
@ishan dutta
in my program variable k contain value of d from the statement of the problem
d1[i][j] is the sum of k elements starting from a[i][j] in first diagonal direction, i.e.
d1[i][j]=a[i][j]+a[i-1][j-1]+a[i-2][j-2]+...+a[i-k+1][j-k+1]
where a[i][j]=0 if cell (i,j) is outside the grid
d2[i][j] is the sum of k+1 elements starting from a[i][j] in second diagonal direction, i.e.
d2[i][j]=a[i][j]+a[i-1][j+1]+a[i-2][j+2]+...+a[i-k][j+k]
where again a[i][j]=0 if cell (i,j) is outside the grid
sq[i][j] is the sum of elements of diamond of size k with center in (i,j)
when we want to obtain the value of sq[i+1][j] (or sq[i][j+1]) from sq[i][j] it is easy to see that sums d1[][] and d2[][] take part there.
for problem2: For
for problem2:
For illustration, say B = 110101 so the answer is f(0) + f(2) + f(4) + f(5) = 1 + 111 + 11111 + 111111. The final answer is 1100110.
Writing these f(i) values in binary on top of each other we see:
111111
011111
000111
000001
we can do it more easy way. by left shift the number-number of set bit;. here is example
111111 = (1000000-1)
011111 = (0100000-1)
000111 = (0001000-1)
000001 = (0000010-1)
total
1100110 = (1101010 - 4) = left shift - number of set bit.