Bit-by-Bit: Nice Array

Contest Page | CodeChef

Problem Code: NICAR

Here is the approach that can be used to solve the Nice Array problem from Bit-by -it contest:-

Approach-

By the problem statement it is clear that we have to target Nice constant N[i] first, since a[i] = c[i] +n[i].

So let’s start restoring Initial Array from left to right a1,a2,……..,a[i] .

Initially a[1] = c[1] , since N[1] will be zero for i=1;

Now for all i>1, N[i] = max(a1,a2,….,a[i-1], so by this we can maintain the maximum of previous elements and get the value of N[i], then using this nice constant we can restore a[i] as c[i]+N[i] .

Solution:-

#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector <int> a(n);
  int x = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i] += x;
    x = max(x, a[i]);
    cout << a[i] << ' ';
  }
}