In this HackerRank Candles Counting problem solution, Tim is visiting his grandma for two days and is bored due to the lack of the electricity over there. That's why he starts to play with grandma's colorful candle collection.
He aligned the N candles from left to right. The ith candle from the left has the height Hi and the color Ci, an integer ranged from 1 to a given K, the number of colors.
Now he stares at the sequence of candles and wonders, how many strictly increasing ( in height ) colorful subsequences are there? A subsequence is considered colorful if every of the K colors appears at least one time in the subsequence.
Problem solution in Java.
import java.util.Scanner;
public class HackerRankCandleCountingFenwick {
private static final Scanner scanner = new Scanner(System.in);
private static final long PLONG = (long) Math.pow(10, 9) + 7;
private static final int PINT = (int) Math.pow(10, 9) + 7;
public static class FenwickCandles {
private final int[] array;
public FenwickCandles(int size) {
array = new int[size + 1];
}
public int treeSum() {
return sumUpToIdx(this.size() - 1);
}
public int sumUpToIdx(int idx) {
idx++; // translate from 0-indexed input to 1-indexed array
assert idx > 0;
long sum = 0;
while (idx > 0) {
sum += array[idx];
idx -= idx & (-idx);
}
return (int) (sum % PLONG);
}
public void update(int idx, int value) {
idx++; // translate from 0-indexed input to 1-indexed array
assert idx > 0;
while (idx < array.length) {
array[idx] = (array[idx] + value) % PINT;
idx += idx & (-idx);
}
}
public int size() {
return array.length - 1;
}
}
static int candlesCounting(int k, int n, int[][] candles, int maxHeight) {
int bLen = (int) Math.pow(2, k);
FenwickCandles[] allBSTs = new FenwickCandles[bLen];
int[] newCount = new int[bLen];
for (int tree = 1; tree < bLen; tree++) {
allBSTs[tree] = new FenwickCandles(maxHeight + 1);
}
for (int i = 0; i < n; i++) {
int height = candles[i][0];
int candleColor = candles[i][1] - 1;
newCount[1 << candleColor] = 1;
for (int tree = 1; tree < bLen; tree++) {
int count = allBSTs[tree].sumUpToIdx(height - 1);
if (count > 0) {
// nth bit represents color n
int newJ = tree | (1 << candleColor);
newCount[newJ] = (newCount[newJ] + count) % PINT;
}
if (newCount[tree] > 0) {
allBSTs[tree].update(height, newCount[tree]);
newCount[tree] = 0;
}
}
}
return allBSTs[bLen - 1].treeSum();
}
public static void main(String[] args) {
String[] nk = scanner.nextLine().split(" ");
int n = Integer.parseInt(nk[0]);
int k = Integer.parseInt(nk[1]);
int[][] candles = new int[n][2];
int maxH = 0;
for (int row = 0; row < n; row++) {
String[] s = scanner.nextLine().split(" ");
for (int col = 0; col < 2; col++) {
int i = Integer.parseInt(s[col]);
if (col == 0 && i > maxH) {
maxH = i;
}
candles[row][col] = i;
}
}
int result = candlesCounting(k, n, candles, maxH);
System.out.println(result);
scanner.close();
}
}
Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 50050;
struct FenwickTree {
long long tree[MAXN];
FenwickTree() {
memset(tree, 0, sizeof(tree));
}
void update(int idx, long long val) {
while (idx <= MAXN) {
tree[idx] = (tree[idx] + val) % MOD;
idx += (idx & -idx);
}
}
long long query(int idx) {
long long sum = 0;
while (idx > 0) {
sum = (sum + tree[idx]) % MOD;
idx -= (idx & -idx);
}
return sum;
}
} ft[128];
int h[MAXN];
int c[MAXN];
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n, k; cin >> n >> k;
ft[0].update(1, 1);
for (int i = 0; i < n; i++) {
cin >> h[i] >> c[i];
h[i]++, c[i]--;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < (1 << k); j++) {
if ((j & (1 << c[i])) != 0) {
int color = (j & ((1 << c[i]) - 1)) | (j & ((~((1 << c[i]) - 1)) << 1));
long long temp = (ft[color].query(h[i] - 1) + ft[j].query(h[i] - 1)) % MOD;
if (temp > 0) {
ft[j].update(h[i], temp);
}
}
}
}
cout << ft[(1 << k) - 1].query(MAXN) << endl;
return 0;
}
Problem solution in C.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
#define HEIGHT 50001
#define LNHT 16
char* readline();
char** split_string(char*);
/*
* Complete the candlesCounting function below.
*/
int candlesCounting(int k, int n, int** candles) {
int *seqsegtree[1<<k][LNHT + 1];
for(int i = 0; i < 1<<k; i++){
for(int j = 0; j <= LNHT; j++){
seqsegtree[i][j] = malloc(sizeof(int)<<(LNHT - j));
for(int a = 0; a < 1<<(LNHT - j); a++){
seqsegtree[i][j][a] = 0;
}
}
}
for(int j = 0; j <= LNHT; j++){
seqsegtree[0][j][0] = 1;
}
for(int i = 0; i < n; i++){
int ht = candles[i][0];
int color = candles[i][1] - 1;
for(int dig = LNHT; dig >= 0; dig--){
if(((ht>>dig)&1) == 1){
for(int j = 0; j < 1<<k; j++){
seqsegtree[j | 1<<color][0][ht] = (seqsegtree[j | 1<<color][0][ht] + seqsegtree[j][dig][(ht>>dig) - 1])%MOD;
}
}
}
for(int dig = 0; dig < LNHT; dig++){
int nextpos = ht>>(dig + 1);
for(int j = 0; j < 1<<k; j++){
seqsegtree[j][dig + 1][nextpos] = (seqsegtree[j][dig][2*nextpos] + seqsegtree[j][dig][2*nextpos + 1])%MOD;
}
}
}
return seqsegtree[(1<<k) - 1][LNHT][0];
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char** nk = split_string(readline());
char* n_endptr;
char* n_str = nk[0];
int n = strtol(n_str, &n_endptr, 10);
if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }
char* k_endptr;
char* k_str = nk[1];
int k = strtol(k_str, &k_endptr, 10);
if (k_endptr == k_str || *k_endptr != '\0') { exit(EXIT_FAILURE); }
int** candles = malloc(n * sizeof(int*));
for (int candles_row_itr = 0; candles_row_itr < n; candles_row_itr++) {
*(candles + candles_row_itr) = malloc(2 * (sizeof(int)));
char** candles_item_temp = split_string(readline());
for (int candles_column_itr = 0; candles_column_itr < 2; candles_column_itr++) {
char* candles_item_endptr;
char* candles_item_str = *(candles_item_temp + candles_column_itr);
int candles_item = strtol(candles_item_str, &candles_item_endptr, 10);
if (candles_item_endptr == candles_item_str || *candles_item_endptr != '\0') { exit(EXIT_FAILURE); }
*(*(candles + candles_row_itr) + candles_column_itr) = candles_item;
}
}
int result = candlesCounting(k, n, candles);
fprintf(fptr, "%d\n", result);
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
0 Comments