In this HackerEarth Bear and Chocolate problem solution, Limak is a little polar bear. Today he found something delicious in the snow. It's a square bar of chocolate with N x N pieces. Some pieces are special because there are cherries on them. You might be surprised by cherries on chocolate but you've never been on the Arctic Circle, have you?

Lima is going to use his claws and break the chocolate into two parts. He can make a cut between two rows or between two columns. It means that he can't break any piece!

Limak will eat one part right now, saving the second part for tomorrow. Cherries are very important to him so he wants to have an equal number of cherries today and tomorrow. Though parts don't have to have equal numbers of pieces of chocolate.

Given the description of chocolate, could you check if Limak can make a cut dividing chocolate into two parts with an equal number of cherries?


HackerEarth Bear and Chocolate problem solution


HackerEarth Bear and Chocolate problem solution.

#include<bits/stdc++.h>
using namespace std;
#define REP(i) for(int i = 0; i < n; ++i)
char sl[1005][1005];
int main() {
  int z;
  scanf("%d", &z);
  while(z--) {
    int n, total = 0, s = 0;
    scanf("%d", &n);
    REP(y) scanf("%s", sl[y]);
    REP(y)REP(x) total += sl[y][x] == '#';
    bool ans = false;
    REP(x) {
      REP(y) s += sl[y][x] == '#';
      if(s * 2 == total) ans = true;
    }
    s = 0;
    REP(y) {
      REP(x) s += sl[y][x] == '#';
      if(s * 2 == total) ans = true;
    }
    puts(ans ? "YES" : "NO");
  }
  return 0;
}


Second solution

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
char chocolate[MAXN][MAXN];
int column_cherries[MAXN],row_cherries[MAXN];
int main()
{
  int t;
  scanf("%d", &t);
  while(t--)
  {
    int n;
    scanf("%d", &n);
    memset(column_cherries, 0, sizeof column_cherries);
    memset(row_cherries, 0, sizeof row_cherries);
    int total_cherries = 0;
    for (int i = 0; i < n; ++i)
    {
      scanf("%s", chocolate[i]);
    }
    for (int i = 0; i < n; ++i)
    {
      for (int j = 0; j < n; ++j)
      {
        if(chocolate[i][j] == '#')
        {
          column_cherries[j]++;
          row_cherries[i]++;
          total_cherries++;
        }
      }
    }
    bool ans = false;
    int cherries_above = 0;
    for (int i = 0; i < n; ++i)
    {
      cherries_above+=row_cherries[i];
      if(2*cherries_above == total_cherries)
        ans = true;
    }
    int cherries_left = 0;
    for (int i = 0; i < n; ++i)
    {
      cherries_left+=column_cherries[i];
      if(2*cherries_left == total_cherries)
        ans = true;
    }
    if(ans)
      printf("YES\n");
    else
      printf("NO\n");
  }
  return 0;
}