Thursday, October 27, 2016

Hacker Rank - Flipping the matrix

Problem:

Please find the problem here.

Analysis:

The key idea to the problem is the following dance.


  • Flip the ith row
  • Flip the jth column
  • Flip the ith row again
  • Flip the jth column again
Let see how that goes, suppose the matrix was something like:

.A.B.
CDEFG
.H.I.
JKLMN
.O.P.

Flipping the ith row gives


.A.B.
GFEDC
.H.I.
JKLMN
.O.P.


Flipping the jth column gives

.O.B.
GKEDC
.H.I.
JFLMN
.A.P.



Flipping the ith row again gives


.O.B.
CDEKG
.H.I.
JFLMN
.A.P.

Flipping the jth column again gives

.A.B.
CFEKG
.H.I.
JDLMN
.O.P.

Solution:

Notice we successfully only rotated a few elements while keeping all the rest unchanged. Which means we can simply pick the maximum of the three (in fact, with some more moves, we can also pick the fourth), and all these maneuver leave the rest unchanged, which means we can simply do that for all the cells - and this is obvious the best possible.

Code:
#include "stdafx.h"

// https://www.hackerrank.com/challenges/flipping-the-matrix

#include "HACKER_RANK_FLIPPING_THE_MATRIX.h"

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int HACKER_RANK_FLIPPING_THE_MATRIX()
{
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        int n;
        cin >> n;
        int matrix[256][256];
        for (int p = 0; p < 2 * n; p++)
        {
            for (int q = 0; q < 2 * n; q++)
            {
                cin >> matrix[p][q];
            }
        }
        int sum = 0;
        for (int p = 0; p < n; p++)
        {
            for (int q = 0; q < n; q++)
            {
                sum += max(max(max(matrix[p][q], matrix[2 * n - 1 - p][q]), matrix[p][2 * n - 1 - q]), matrix[2 * n - 1 - p][2 * n - 1 - q]);
            }
        }
        cout << sum << endl;
    }
    return 0;
}

No comments :

Post a Comment