Codeforces wet shark and bishop

Question

I have done this question and i was reading some of the other's codes on it. Here is the question link : http://codeforces.com/contest/621/problem/B I am trying to understand how this code was accepted:

#include <cstdio>
#include <iostream>
using namespace std;

int a[3000];
int b[3000];
int x , y;
long long sum;

main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
   {
        cin >> x >> y;
        sum += a[x+y]++;
        sum += b[1000+x-y]++;
    }
   cout<<sum;
}

I have been thinking a lot but I did not understand the algorithm. Does anyone understand it? Also what is the cstdio for? (I am not that familiar with c++ and I am a beginner in programming)

For this simple program, `` is probably not needed. It gives C++ access to classic "C" functions such as `printf`. It's nearly equivalent as `` — selbie, Aug 28 '18 at 17:37
Competition sites seem to give extra points for writing brittle and unreadable code. I recommend using other materials to learn C++. The Internet's not even much help until you understand the terminology, so [you're better off starting with a good book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — user4581301, Aug 28 '18 at 17:45
If I'm not mistaken, I think `a` and `b` should only need to be `1999` in size (because that's the number of diagonals), but that's also only if you account for 1-based indexes properly — kmdreko, Aug 28 '18 at 17:47
The arrays are initialized to zero since they are globals. The loop increments particular array elements after adding to the `sum`. Have you tried compiling and running the program using the example data provided in the problem statement? You could also add a statement at the end of the loop to print out the values of `a` and `b` as well, something like `cout << " a [" << x + y << "] = " << a[x+y] << ", b [" << 1000 + x - y << "] = " << b[1000 + x - y] << endl;` — Richard Chambers, Aug 28 '18 at 17:58

interfect · Accepted Answer · 2018-08-28T18:32:20.257

The problem is that you are given the positions of bishops on a big chessboard, and you are to count the number of pairs of bishops that share a diagonal (i.e. could attack each other, if no other bishops were in the way).

The insight that makes this code work is that you can start with an empty board, and account for all the possible bishop pairs by saying that each pair is between a bishop already on the board and a new bishop being added.

The basic algorithm here is that a counts the number of bishops on each diagonal running in one direction (upper-left to lower-right, if x counts across and y counts down), and b counts the number of bishops on each diagonal running in the other, perpendicular direction (upper-right to lower-left).

You can use x+y to get which upper-left-to-lower-right diagonal the current bishop lands on. It will form a pair with each other bishop already placed on the diagonal, so you add in a[x+y] to your sum. Then you increment a[x+y], because you just put a new bishop on that diagonal.

Similarly with the other diagonal: work out which diagonal you are going to with x-y, add the number of bishops already on the diagonal (and thus the number of new pairs formed) into the sum, and then increment the diagonal's bishop count.

The 1000+ is there to prevent the array index from becoming negative, because x-y can be negative when x is 0. The arrays are made excessively big because the programmer didn't bother working out how small they could safely be. The program exploits rule 3.6.2 of the C++ standard which guarantees that static-storage-duration variables (like all those globals) will be 0-initialized.

Working Draft, Standard for Programming Language C++ N4296 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf see section 3.6.2 Initialization of non-local variables (page 62) as well as section 8.5 Initializers (page 210). — Richard Chambers, Aug 28 '18 at 18:23

Codeforces wet shark and bishop

1 Answers1