Header Ad

HackerEarth Find the Array problem solution

In this HackerEarth Find the Array problem solution You have two positive integer arrays A and B of same length N. But elements of array A are hidden from you. And you know A is lexicographically greater than B. You’ll be given M information about A. Each of the M information will be given in this format “i > j” or “i < j”, which means A[i] is greater or smaller than A[j] respectively (depending on the sign). You have to find the integers of A, or determine no such array exists. In case of multiple possible answers, find the lexicographically smallest one among them.


HackerEarth Find the Array problem solution


HackerEarth Find the Array problem solution.

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class FindTheArray {
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
PrintWriter pw = new PrintWriter(System.out);
solver(in, pw);
pw.close();
}

static void solver(InputReader in, PrintWriter pw) throws Exception {
int test = in.nextInt();
for (int t = 1; t <= test; t++) {
int n = in.nextInt(), m = in.nextInt();
CHECK(1, (int) 1e5, n);
CHECK(0, (int) 1e5, m);

List<Integer> g[] = genList(n);
List<Integer> r[] = genList(n);
int b[] = new int[n];
for (int i = 0; i < n; i++) {
b[i] = in.nextInt();
CHECK(1, (int)1e9, b[i]);
}
for (int i = 0; i < m; i++) {
int u = in.nextInt();
char sign = in.next().charAt(0);
int v = in.nextInt();

CHECK(1, n, u);
CHECK(1, n, v);
if (u == v) throw new RuntimeException("i = j");

u--;
v--;
if (sign == '>') { //swap
int tmp = u;
u = v;
v = tmp;
}
g[u].add(v);
r[v].add(u);
}
int order[] = topologicalSort(g);
if (order == null) {
pw.println("NO");
} else {
int a[] = new int[n];
for (int u : order) {
int max = 1;
for (int v : r[u]) {
max = max(max, a[v] + 1);
}
a[u] = max;
}
int k = binarySearch(n, a, b, order, r);
boolean ok = check(k, n, a, b, order, r);
if (!ok || !isCorrectSolution(n, a, b, g)) {
throw new RuntimeException("WRONG ANSWER");
}

pw.println("YES");
for (int i = 0; i < n; i++) {
pw.print(a[i]);
if (i < n - 1) pw.print(" ");
else pw.println();
}
}
}

pw.close();
}

static void CHECK(int l, int r, int val) {
if (val < l || val > r) throw new RuntimeException("Value out of bound");
}

static void reverseArray(int a[]){
for(int i = 0, j = a.length-1; i < j; i++, j--){
int temp = a[i]; a[i] = a[j]; a[j] = temp;
}
}

static boolean check_2(int k, int n, int b[], int order[], List<Integer> g[]) {
long [] l = new long[n], r = new long[n];
for(int i = 0; i < n; i++) {
if (i < k) {
l[i] = r[i] = b[i];
}
else {
l[i] = 1;
r[i] = (long)1e15;
}
}
for (int u : order) {
for (int v : g[u]) {
l[u] = max(l[u], l[v] + 1);
}
}
reverseArray(order);
for (int u : order) {
for (int v : g[u]) {
r[v] = min(r[v], r[u] - 1);
}
}
reverseArray(order);

for(int u = 0; u < n; u++) {
if (l[u] > r[u]) {
return false;
}
}

for(int u = 0; u < n; u++) {
if (r[u] > b[u]) {
return true;
}
if (r[u] < b[u]) {
return false;
}
}
return false;
}

static boolean check(int k, int n, int a[], int b[], int order[], List<Integer> r[]) {
a[k] = max(a[k], b[k] + 1);
for (int i = 0; i < k; i++) {
a[i] = max(a[i], b[i]);
if (a[i] > b[i]) return false;
}
//debug("K", k, a);
for (int u : order) {
int max = 1;
for (int v : r[u]) {
max = max(max, a[v] + 1);
}
a[u] = max(a[u], max);
}
for (int i = 0; i < k; i++) {
if (a[i] > b[i]) return true;
if(a[i] < b[i]) return false;
}
return true;
}

static int binarySearch(int n, int a[], int b[], int order[], List<Integer> r[]) {
int lo = 0, hi = n - 1, mid;
while (lo < hi) {
mid = (lo + hi) / 2;
if (!check_2(mid, n, b, order, r)) hi = mid;
else lo = mid + 1;
}
if (lo > 0 && !check_2(lo, n, b, order, r)) {
lo--;
}
return lo;
}

static boolean isCorrectSolution(int n, int a[], int b[], List<Integer> g[]) {
for (int u = 0; u < n; u++) {
for (int v : g[u]) {
if (a[u] >= a[v]) return false;
}
}
for (int i = 0; i < n; i++) {
if (a[i] < b[i]) return false;
if (a[i] > b[i]) return true;
}
return false;
}

static <T> List<T>[] genList(int n) {
List<T> list[] = new List[n];
for (int i = 0; i < n; i++) list[i] = new ArrayList<T>();
return list;
}

public static int[] topologicalSort(List<Integer> g[]) {
int n = g.length;
int[] ec = new int[n];
for (int i = 0; i < n; i++) {
for (int to : g[i]) ec[to]++;
}
int[] ret = new int[n];
int q = 0;

// sources
for (int i = 0; i < n; i++) {
if (ec[i] == 0) ret[q++] = i;
}

for (int p = 0; p < q; p++) {
for (int to : g[ret[p]]) {
if (--ec[to] == 0) ret[q++] = to;
}
}
// loop
for (int i = 0; i < n; i++) {
if (ec[i] > 0) return null;
}
return ret;
}

static void debug(Object... obj) {
System.err.println(Arrays.deepToString(obj));
}

static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;

public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}

public String next() throws Exception {
while (tokenizer == null || !tokenizer.hasMoreTokens())
tokenizer = new StringTokenizer(reader.readLine());
return tokenizer.nextToken();
}

public int nextInt() throws Exception {
return Integer.parseInt(next());
}
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() {return abs((int) mt());}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

const int maxn = 1e5 + 5;
int n, m;
int a[maxn];
int b[maxn];
vi adj[maxn];
vi radj[maxn];

vi ver;
int vis[maxn];
int f[maxn];
void dfs(int u) {
vis[u] = 1;
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v);
}
}
f[u] = sz(ver);
ver.pb(u);
}

int check(int mi) {
reverse(all(ver));
for (int u : ver) {
int mx = INF + INF;
for (int v : radj[u]) {
chkmin(mx, a[v] - 1);
}
if (u < mi) {
if (b[u] > mx) {
reverse(all(ver));
return 0;
}
a[u] = b[u];
}
else {
a[u] = mx;
}
if (a[u] <= 0) {
reverse(all(ver));
return 0;
}
}
reverse(all(ver));

FOR(u, 0, n) {
if (a[u] > b[u]) {
return 1;
}
if (a[u] < b[u]) {
return 0;
}
}
return 0;
}

int finish(int mi) {
for (int u : ver) {
int mx = 1;
for (int v : adj[u]) {
chkmax(mx, a[v] + 1);
}
if (u < mi) {
if (b[u] < mx) {
return 0;
}
a[u] = b[u];
}
else if (u == mi) {
a[u] = max(b[u] + 1, mx);
}
else {
a[u] = mx;
}
}
return 1;
}

void eof() {
string s; assert(!(cin >> s));
}

void chemthan() {
int test; assert(cin >> test);
assert(1 <= test && test <= 5);
while (test--) {
assert(cin >> n >> m);
assert(1 <= n && n <= 1e5);
assert(0 <= m && m <= 1e5);
FOR(i, 0, n) adj[i].clear(), radj[i].clear(), vis[i] = 0;
FOR(i, 0, n) {
assert(cin >> b[i]);
assert(1 <= b[i] && b[i] <= 1e9);
}
FOR(i, 0, m) {
int u, v; string sign; assert(cin >> u >> sign >> v); u--, v--;
assert(0 <= u && u < n);
assert(0 <= v && v < n);
assert(sign == "<" || sign == ">");
if (sign == "<") swap(u, v);
adj[u].pb(v), radj[v].pb(u);
}
ver.clear();
FOR(u, 0, n) if (!vis[u]) {
dfs(u);
}
int found = 0;
FOR(u, 0, n) {
for (int v : adj[u]) {
if (f[u] < f[v]) {
found = 1;
}
}
}
if (found) {
cout << "NO\n";
continue;
}
int lo = 0, hi = n - 1;
while (lo < hi) {
int mi = lo + hi + 1 >> 1;
if (check(mi)) {
lo = mi;
}
else {
hi = mi - 1;
}
}
assert(check(lo + hi >> 1));
assert(finish(lo + hi >> 1));
cout << "YES\n";
FOR(i, 0, n) cout << a[i] << " \n"[i == n - 1];
}
eof();
}

int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0), cin.tie(0);
if (argc > 1) {
assert(freopen(argv[1], "r", stdin));
}
if (argc > 2) {
assert(freopen(argv[2], "wb", stdout));
}
chemthan();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}

Post a Comment

0 Comments