I was wondering how best to optimize the solution for PRITREE. The way I approached was I generated random trees and permuted the values among their nodes and kept saving the best one. I even kept partitioning the primes to the leaves with some probability.
I was wondering how better to solve this (I couldn’t find the editorial link for this).
Link to my solution
P.S: This is my first attempt at a Challenge problem.
I developed a solution, where I was only developing a linear tree ( a three node tree will be like 1-2-3). I found out the next node to join in the current tree by finding if the current tree node sum or the remaining node sum becomes prime after joining the node. I kept doing this through a greedy approach.
The major constraint was that trees could only be linear but I still managed 88.6 points. Link to the solution.
In my solution, I inserted elements into a heap such that if the node is not prime and (totalSum - sumOfNodeSubtree) is not prime it appears at the front of the heap and if node is prime and (totalSum - sumOfNodeSubtree) is prime, it goes at the end. I took the first element of the heap, made it a parent (no point in making it a leaf) and chose its child such that the sum of the two nodes is of latter type (if possible), and child should preferably be at the lower end of the heap. Inserted parent back into the heap with updated sum.
It was quite greedy, still got 91 points. Here is my solution.