In this post, we will solve 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 H and the color Câ‚‚, 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 as colorful if every of the K colors appears at least one times in the subsequence.
As the number of subsequences fulfilling the requirement can be large, print the result modulo 10 power 9 +7.
Input Format
On the first line you will be given N and K. then N lines will follow. On the ith line you will be given two integers H, and C.
Output Format
Print the number of strictly increasing colorful subsequences modulo 10 power 9 +7.
Sample Input
4 3
1 1
3 2
2 2
4 3
Sample Output
2
Explanation
In the first sample the only two valid subsequences are (1, 2, 4) and (1, 3, 4).
Candles Counting C Solution
#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;
}Candles Counting C++ Solution
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXK = 15;
const int MAXN = 5e4+54;
const long long int MOD = 1e9+7;
struct Candle{
int height, colour, index;
Candle( int height_=0, int colour_=0, int index_=0 ){
height = height_;
colour = colour_;
index = index_;
}
friend bool operator < ( const Candle &a, const Candle &b ){
if( a.height == b.height )
return a.index > b.index;
return a.height < b.height;
}
};
struct Fenwick{
int N;
long long int *bit;
void init( int N_ ){
N = N_;
bit = new long long int[N+1];
}
void add( int index, long long int value ){
for( int i=index ; i<=N ; i += i&-i )
bit[i] = (bit[i] + value) % MOD;
}
long long int sum( int l, int r ){
if( l > r )
return 0;
long long int rev = 0LL;
for( int i=r ; i ; i -= i&-i )
rev = (rev + bit[i]) % MOD;
for( int i=l-1 ; i ; i -= i&-i )
rev = (rev - bit[i] + MOD) % MOD;
return rev;
}
~Fenwick(){
delete [] bit;
}
};
int N, K;
Candle ar[MAXN];
Fenwick dn[1 << MAXK];
int main(){
scanf("%d%d", &N, &K);
for( int i=0 ; i < (1 << K) ; i++ )
dn[i].init(N);
for( int i=1 ; i<=N ; i++ ){
scanf("%d%d", &ar[i].height, &ar[i].colour);
ar[i].colour--;
ar[i].index = i;
}
sort(ar+1, ar+N+1);
for( int i=N ; i ; i-- ){
for( int mask = 0 ; mask < (1 << K) ; mask++ )
dn[mask | (1 << ar[i].colour)].add(ar[i].index, dn[mask].sum(ar[i].index+1, N));
dn[1 << ar[i].colour].add(ar[i].index, 1LL);
}
printf("%lld\n", dn[(1 << K) - 1].sum(1, N));
return 0;
}Candles Counting C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{
/*
* Complete the 'candlesCounting' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER k
* 2. 2D_INTEGER_ARRAY candles
*/
private static long Mod = 1000000007;
public class Candles
{
public long[] array;
public Candles(int size)
{
array = new long[size +1];
}
public long cal(int idx)
{
long sum = 0;
while (idx > 0)
{
sum += array[idx];
idx -= idx & -idx;
}
return sum % Mod;
}
public void update(int idx, long value)
{
while (idx < array.Length)
{
array[idx] = (array[idx] + value) % Mod;
idx += idx & -idx;
}
}
}
public static int candlesCounting(int k, List<List<int>> candles)
{
int maxHeight = candles.Max(q => q[0]);
int n = candles.Count;
int per = (int)Math.Pow(2, k);
Candles[] dp = new Candles[per];
for (int tree = 0; tree < per; tree++)
{
dp[tree] = new Candles(maxHeight + 2);
}
dp[0].update(1, 1);
for (int i = 0; i < n; i++)
{
int height = candles[i][0]+1;
int color = candles[i][1] - 1;
for (int j = 1; j < per; j++)
{
if ((j & (1 << color)) != 0)
{
int newcol = (j & ((1 << color) - 1)) | (j & ((~((1 << color) - 1)) << 1));
long count = (dp[newcol].cal(height - 1) + dp[j].cal(height - 1)) % Mod;
if (count > 0)
{
dp[j].update(height, count);
}
}
}
}
return (int)dp[per - 1].cal(maxHeight + 1);
}
}
class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');
int n = Convert.ToInt32(firstMultipleInput[0]);
int k = Convert.ToInt32(firstMultipleInput[1]);
List<List<int>> candles = new List<List<int>>();
for (int i = 0; i < n; i++)
{
candles.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(candlesTemp => Convert.ToInt32(candlesTemp)).ToList());
}
int result = Result.candlesCounting(k, candles);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}Candles Counting Java Solution
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();
}
}Candles Counting JavaScript Solution
const fs = require("fs");
// Read all lines from STDIN
const buffer = fs.readFileSync(0);
const lines = buffer.toString().split("\n");
// Used for parsing each line
const parse = (line) => line.trim().split(" ").map(Number);
const MOD = 10 ** 9 + 7;
// Binary Indexed Tree for representing an array A of size n
class BIT {
constructor(n) {
this.nodes = new Array(n + 1).fill(0);
}
get size() {
return this.nodes.length;
}
// Get sum of elements of A in range [0, index]
query(index) {
let sum = 0;
for (; index > 0; index -= index & -index) {
sum += this.nodes[index];
}
return sum;
}
// Update BIT when 'value' is added to A[index]
update(index, value) {
for (; index < this.size; index += index & -index) {
this.nodes[index] += value;
this.nodes[index] %= MOD;
}
}
}
const [n, k] = parse(lines[0]);
const H = [];
const C = [];
for (let i = 1; i <= n; i++) {
const [h, c] = parse(lines[i]);
H.push(h);
C.push(c);
}
let count = 0;
// Maximum size of BIT
const max = Math.max(...H);
// colors is a k-bit mask where the i-th bit is set if a color i is to be included in the subsequence
for (let colors = 1; colors < 1 << k; colors++) {
/* A BIT for representing an imaginary 1-indexed array A, where A[value] contains the number of subsequences
ending with 'value' */
const bit = new BIT(max);
for (let i = 0; i < n; i++) {
// Consider candle i only if its color is included in the mask 'colors'
if ((colors >> (C[i] - 1)) & 1) {
// Number of subsequences ending with A[[H[i]]] = 1 + Sum of number of subsequences ending with [1,2,3,..., H[i] - 1]
// Update the BIT since A[[H[i]]] is updated.
bit.update(H[i], 1 + bit.query(H[i] - 1));
}
}
// Find number of increasing subsequences that contain candles of any number of colors
if (colors.toString(2).match(/1/g).length % 2 == k % 2) {
count += bit.query(bit.size - 1);
count %= MOD;
} else {
// Remove the increasing subsequences that do not contain candles of k colors
count -= bit.query(bit.size - 1);
count %= MOD;
}
}
console.log(count);Candles Counting Python Solution
#!/bin/python
import math
import os
import random
import re
import sys
#
# Complete the 'candlesCounting' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
# 1. INTEGER k
# 2. 2D_INTEGER_ARRAY candles
#
MOD = pow(10, 9) + 7
def update(bit, index, delta):
while index < len(bit):
bit[index] = (bit[index] + delta) % MOD
index += index & (-index)
def query(bit, index):
range_sum = 0
while index > 0:
range_sum = (range_sum + bit[index]) % MOD
index -= index & (-index)
return range_sum
def candlesCounting(k, candles):
heights = sorted([candle[0] for candle in candles])
ranks = {}
for index, height in enumerate(heights):
ranks[height] = index + 1
for candle_index in range(len(candles)):
candles[candle_index][0] = ranks[candles[candle_index][0]]
max_color = max(candle[1] for candle in candles)
color_states = 1 << max_color
dp = [[0] * (len(candles) + 1) for _ in range(color_states)]
for candle_index in range(len(candles)):
height_rank = candles[candle_index][0]
curr_color_state = 1 << (candles[candle_index][1] - 1)
for color_state in range(color_states):
if ((color_state & curr_color_state) == 0):
continue
curr_color_bit_removed_state = color_state ^ curr_color_state
curr_color_bit_removed_count = query(dp[curr_color_bit_removed_state], height_rank - 1)
color_state_count = query(dp[color_state], height_rank - 1)
if color_state == curr_color_state:
color_state_count += 1
update(dp[color_state], height_rank, curr_color_bit_removed_count + color_state_count)
return query(dp[-1], len(candles))
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
first_multiple_input = raw_input().rstrip().split()
n = int(first_multiple_input[0])
k = int(first_multiple_input[1])
candles = []
for _ in xrange(n):
candles.append(map(int, raw_input().rstrip().split()))
result = candlesCounting(k, candles)
fptr.write(str(result) + '\n')
fptr.close()
