JavaProgramming/HackerRank/FourtyThree.java at patch-2 · subham500071430/JavaProgramming · GitHub

History

223 lines (179 loc) · 5.99 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

package HackerRank;

import java.util.ArrayList;

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

import java.util.ArrayList;

import java.util.Scanner;

enum Color {

RED, GREEN

}

abstract class Tree {

private int value;

private Color color;

private int depth;

public Tree(int value, Color color, int depth) {

this.value = value;

this.color = color;

this.depth = depth;

}

public int getValue() {

return value;

}

public Color getColor() {

return color;

}

public int getDepth() {

return depth;

}

public abstract void accept(TreeVis visitor);

}

class TreeNode extends Tree {

private ArrayList<Tree> children = new ArrayList<>();

public TreeNode(int value, Color color, int depth) {

super(value, color, depth);

}

public void accept(TreeVis visitor) {

visitor.visitNode(this);

for (Tree child : children) {

child.accept(visitor);

}

public void addChild(Tree child) {

children.add(child);

}

class TreeLeaf extends Tree {

public TreeLeaf(int value, Color color, int depth) {

super(value, color, depth);

}

public void accept(TreeVis visitor) {

visitor.visitLeaf(this);

}

abstract class TreeVis

{

public abstract int getResult();

public abstract void visitNode(TreeNode node);

public abstract void visitLeaf(TreeLeaf leaf);

}

class SumInLeavesVisitor extends TreeVis {

private int sum = 0;

public int getResult() {

//implement this

return sum;

}

public void visitNode(TreeNode node) {

//implement this

}

public void visitLeaf(TreeLeaf leaf) {

//implement this

sum += leaf.getValue();

}

class ProductOfRedNodesVisitor extends TreeVis {

private long product = 1;

private final int MOD = 1000000007;

public int getResult() {

//implement this

return (int) product;

}

public void visitNode(TreeNode node) {

//implement this

if(node.getColor() == Color.RED){

product = (product * node.getValue()) % MOD;

}

public void visitLeaf(TreeLeaf leaf) {

//implement this

if(leaf.getColor() == Color.RED){

product = (product * leaf.getValue()) % MOD;

}

class FancyVisitor extends TreeVis {

private int evenDepthNonLeafSum = 0;

private int greenLeafSum = 0;

public int getResult() {

//implement this

return Math.abs(evenDepthNonLeafSum - greenLeafSum);

}

public void visitNode(TreeNode node) {

//implement this

if(node.getDepth()%2 == 0){

evenDepthNonLeafSum += node.getValue();

}

public void visitLeaf(TreeLeaf leaf) {

//implement this

if(leaf.getColor() == Color.GREEN){

greenLeafSum += leaf.getValue();

}

public class FourtyThree {

static int[] values;

static Color[] colors;

static Map<Integer, Set<Integer>> treeMap = new HashMap<>();

public static Tree solve() {

//read the tree from STDIN and return its root as a return value of this function

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

values = new int[n + 1];

colors = new Color[n + 1];

for (int i = 1; i <= n; i++) {

values[i] = scanner.nextInt();

}

for (int i = 1; i <= n; i++) {

int c = scanner.nextInt();

colors[i] = (c == 0) ? Color.RED : Color.GREEN;

}

for (int i = 0; i < n - 1; i++) {

int u = scanner.nextInt();

int v = scanner.nextInt();

if (!treeMap.containsKey(u)) {

treeMap.put(u, new HashSet<Integer>());

}

treeMap.get(u).add(v);

if (!treeMap.containsKey(v)) {

treeMap.put(v, new HashSet<Integer>());

}

treeMap.get(v).add(u);

}

scanner.close();

return buildTree(1, 0);

}

private static Tree buildTree(int nodeNum, int depth){

Set<Integer> neighbors = treeMap.get(nodeNum);

if (neighbors == null) {

neighbors = new HashSet<Integer>();

}

if (neighbors.isEmpty()) {

return new TreeLeaf(values[nodeNum], colors[nodeNum], depth);

} else {

TreeNode node = new TreeNode(values[nodeNum], colors[nodeNum], depth);

for (int neighbor : neighbors) {

treeMap.get(neighbor).remove(nodeNum); // remove backward edge

node.addChild(buildTree(neighbor, depth + 1));

}

return node;

}

public static void main(String[] args) {

Tree root = solve();

SumInLeavesVisitor vis1 = new SumInLeavesVisitor();

ProductOfRedNodesVisitor vis2 = new ProductOfRedNodesVisitor();

FancyVisitor vis3 = new FancyVisitor();

root.accept(vis1);

root.accept(vis2);

root.accept(vis3);

int res1 = vis1.getResult();

int res2 = vis2.getResult();

int res3 = vis3.getResult();

System.out.println(res1);

System.out.println(res2);

System.out.println(res3);

}

JavaProgramming/HackerRank/FourtyThree.java at patch-2 · subham500071430/JavaProgramming · GitHub

Expand file tree

Breadcrumbs

FourtyThree.java

Latest commit

History

Breadcrumbs

FourtyThree.java

File metadata and controls