You are not logged in. Please login at www.codechef.com to post your questions!

×

How to optimise solution for PRITREE ?

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.

asked 16 Nov '18, 12:16

rsampaths16's gravatar image

5★rsampaths16
11
accept rate: 0%


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.

link

answered 16 Nov '18, 13:53

euler1's gravatar image

5★euler1
111
accept rate: 0%

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.

link

answered 16 Nov '18, 23:20

gkashish's gravatar image

6★gkashish
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,424
×858
×154
×1

question asked: 16 Nov '18, 12:16

question was seen: 457 times

last updated: 16 Nov '18, 23:20