Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Retroactive Integers problem solution

YASH PAL, 31 July 2024
In this HackerEarth Retroactive Integers problem solution You’re maintaining 20 variables: a,b,c,…,r,s,t. At any moment of the time value of any variable is an integer between 0 and 1,000,000,006, inclusive. All arithmetic operations with variables are modulo 1,000,000,007. Initially (at moment 0) all variables are set to 0. At some moments of time, you get queries. Queries have 5 different types:
  1. “? x” print value of variable x.
  2. ” = x y” write value of variable y to variable x.
  3. “! x c” set variable x to c.
  4. ” + x c” add c to variable x.
  5. “* x c” multiply variable x by c.
Also with each query, you are given a positive integer — time when you need to apply this query to variables. Times can go in arbitrary order. See sample for further clarification.
HackerEarth Retroactive Integers problem solution

HackerEarth Retroactive Integers problem solution.

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const int M = 200100;
const int N = 6;
const int mod = 1e9 + 7;

int add(int x, int y) {
x += y;
if (x >= mod)
x -= mod;
return x;
}

int udd(int &x, int y) {
return x = add(x, y);
}

int mul(ll x, ll y) {
return x * y % mod;
}

struct Matrix {
int a[N][N];

Matrix() {
for (int i = 0; i < N; ++i)
fill(a[i], a[i] + N, 0);
}

int* operator[](int x) {
return a[x];
}

Matrix operator*(Matrix to) {
Matrix ans;
for (int i = 0; i < N; ++i)
for (int k = 0; k < N; ++k)
for (int j = 0; j < N; ++j)
udd(ans[i][j], mul(a[i][k], to[k][j]));
return ans;
}
} I;


int q, x[M], xs[M];
char type[M];
int from[M], to[M], by[M];
Matrix t[4 * M];

void ini() {
for (int i = 0; i < N; ++i)
I[i][i] = 1;
fill(t, t + (4 * M), I);
}

int readVariable() {
char c;
cin >> c;
return c - 'a' + 1;
}

void read() {
cin >> q;
for (int i = 0; i < q; ++i) {
cin >> x[i];
xs[i] = x[i];

cin >> type[i];
if (type[i] == '?') {
from[i] = readVariable();
} else if (type[i] == '=') {
to[i] = readVariable();
from[i] = readVariable();
by[i] = 1;
} else if (type[i] == '!') {
to[i] = readVariable();
from[i] = 0;
cin >> by[i];
} else if (type[i] == '+') {
to[i] = readVariable();
from[i] = 0;
cin >> by[i];
} else if (type[i] == '*') {
to[i] = readVariable();
from[i] = to[i];
cin >> by[i];
} else {
cerr << "i = " << i << endl;
cerr << "type = " << type[i] << endl;
assert(false);
}
}
}

void comp() {
sort(xs, xs + q);
for (int i = 0; i < q; ++i)
x[i] = lower_bound(xs, xs + q, x[i]) - xs;
}


Matrix get(int v, int l, int r, int at) {
assert(l <= at && at < r);
if (l + 1 == r) {
return t[v];
}
int m = (l + r) / 2;
if (at < m)
return get(2 * v, l, m, at);
else {
return t[2 * v] * get(2 * v + 1, m, r, at);
}
}

void upd(int v, int l, int r, int at, Matrix &A) {
assert(l <= at && at < r);
if (l + 1 == r) {
t[v] = A;
return;
}
int m = (l + r) / 2;
if (at < m)
upd(2 * v, l, m, at, A);
else
upd(2 * v + 1, m, r, at, A);
t[v] = t[2 * v] * t[2 * v + 1];
}

void kill() {
for (int i = 0; i < q; ++i) {
int at = x[i];
if (type[i] == '?') {
Matrix A = get(1, 0, q, at);
cout << A[0][from[i]] << "n";
} else {
Matrix A = I;
if (type[i] != '+' && type[i] != '*') {
A[to[i]][to[i]] = 0;
}
A[from[i]][to[i]] = by[i];
upd(1, 0, q, at, A);
}
}
}

int main() {
#ifdef LOCAL
assert(freopen("a.in", "r", stdin));
#endif

ios_base::sync_with_stdio(false);

ini();
read();
comp();
kill();
}

Second solution

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
RetroactiveIntegers solver = new RetroactiveIntegers();
solver.solve(1, in, out);
out.close();
}

static class RetroactiveIntegers {
public static int mod = 1000000007;
public static int w = 15;

public static int[][] getIdentity(int n) {
int[][] res = new int[w][3];
for (int i = 0; i < w; i++) {
res[i][0] = i;
res[i][1] = 1;
}
return res;
}

public void solve(int testNumber, InputReader in, OutputWriter out) {
int q = in.nextInt();
RetroactiveIntegers.Query[] qs = new RetroactiveIntegers.Query[q];
int[] times = new int[q];
for (int i = 0; i < q; i++) {
qs[i] = new RetroactiveIntegers.Query(in, i);
times[i] = qs[i].time;
}
Arrays.sort(times);
for (int i = 0; i < q; i++) {
qs[i].time = Arrays.binarySearch(times, qs[i].time);
}
RetroactiveIntegers.SegmentTree os = new RetroactiveIntegers.SegmentTree(q);
for (int i = 0; i < q; i++) {
if (qs[i].which != -1) {
int[][] x = os.query(0, qs[i].time);
out.println(x[qs[i].which][2]);
} else {
os.modify(qs[i].time, qs[i].vv);
}
}
}

public static int[][] combine(int[][] a, int[][] b) {
int[][] ret = new int[w][3];
for (int i = 0; i < w; i++) {
int tt = b[i][0];
ret[i][0] = a[tt][0];
ret[i][1] = (int) ((1L * a[tt][1] * b[i][1]) % mod);
ret[i][2] = (int) ((1L * a[tt][2] * b[i][1] + b[i][2]) % mod);
}
return ret;
}

static class Query {
public int time;
public int idx;
public int[][] vv;
public int which;

public Query(InputReader in, int idx) {
this.idx = idx;
time = in.nextInt();
char c = in.next().charAt(0);
vv = new int[w][3];
for (int i = 0; i < w; i++) {
vv[i][0] = i;
vv[i][1] = 1;
}
which = -1;
switch (c) {
case '?': {
which = in.next().charAt(0) - 'a';
break;
}
case '=': {
int a1 = in.next().charAt(0) - 'a';
int a2 = in.next().charAt(0) - 'a';
vv[a1][0] = a2;
break;
}
case '*': {
int a = in.next().charAt(0) - 'a';
int m = in.nextInt();
vv[a][1] = m;
break;
}
case '!': {
int a = in.next().charAt(0) - 'a';
int m = in.nextInt();
vv[a][1] = 0;
vv[a][2] = m;
break;
}
case '+': {
int a = in.next().charAt(0) - 'a';
int m = in.nextInt();
vv[a][2] = m;
break;
}
}
}

}

static class SegmentTree {
int n;
int[][][] value;

public SegmentTree(int n) {
this.n = n;
value = new int[4 * n][][];
init(0, 0, n - 1);
}

void init(int root, int left, int right) {
value[root] = getIdentity(w);
if (left != right) {
init(2 * root + 1, left, (left + right) / 2);
init(2 * root + 2, (left + right) / 2 + 1, right);
}
}

public int[][] query(int from, int to) {
return query(from, to, 0, 0, n - 1);
}

int[][] query(int from, int to, int root, int left, int right) {
if (from == left && to == right)
return value[root];
int mid = (left + right) >> 1;
if (from <= mid && to > mid)
return combine(
query(from, Math.min(to, mid), root * 2 + 1, left, mid),
query(Math.max(from, mid + 1), to, root * 2 + 2, mid + 1, right));
else if (from <= mid)
return query(from, Math.min(to, mid), root * 2 + 1, left, mid);
else if (to > mid)
return query(Math.max(from, mid + 1), to, root * 2 + 2, mid + 1, right);
else
throw new RuntimeException("Incorrect query from " + from + " to " + to);
}

public void modify(int pos, int[][] nv) {
modify(pos, nv, 0, 0, n - 1);
}

void modify(int pos, int[][] nv, int root, int left, int right) {
if (pos == left && pos == right) {
value[root] = nv;
return;
}
int mid = (left + right) >> 1;
if (pos <= mid)
modify(pos, nv, 2 * root + 1, left, mid);
if (pos > mid)
modify(pos, nv, 2 * root + 2, mid + 1, right);
value[root] = combine(value[2 * root + 1], value[2 * root + 2]);
}

}

}

static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;

try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}

if (this.numChars <= 0) {
return -1;
}
}

return this.buf[this.curChar++];
}
}

public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}

byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}

int res = 0;

while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}

throw new InputMismatchException();
}

public String next() {
int c;
while (isSpaceChar(c = this.read())) {
;
}

StringBuilder result = new StringBuilder();
result.appendCodePoint(c);

while (!isSpaceChar(c = this.read())) {
result.appendCodePoint(c);
}

return result.toString();
}

public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}

}

static class OutputWriter {
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}

public void close() {
writer.close();
}

public void println(int i) {
writer.println(i);
}

}
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes