What type of tree
hey, i gotta write a program that reads from a file the length of the necklaces. they are made with beads that are almost the same and i gotta make the two necklaces the same by changing the beads. then from the text file we read the number M - the possible couple of beads we can change, then we read the colors of the first necklace and then the second necklace, the colors are coded with ASCII symbols. then we read M lines - every line is with 2 symbols and a number - the first symbol is the initial color and the second one is the new color, the number is the time that it takes to make it in the new color.
so i gotta find the fastest way i can make the twp necklaces the same by changing the color.
we gotta use trees for this task, but how to implement the most suitable tree?
so i gotta find the fastest way i can make the twp necklaces the same by changing the color.
we gotta use trees for this task, but how to implement the most suitable tree?
Last edited on
Is this from one of the contest sites like https://www.codechef.com/ or https://codeforces.com/problemset ?
It's certainly got the smell of a CF problem.
> we gotta use trees for this task, but how to implement the most suitable tree?
So you already know how to solve this on paper?
That is, you've drawn lots of trees on paper, filled them with example necklaces in the way the problem describes them, and know how to make the necessary transformations to arrive at the answer.
If you haven't done this yet, then you're worrying about the solution before you're ready.
It's certainly got the smell of a CF problem.
> we gotta use trees for this task, but how to implement the most suitable tree?
So you already know how to solve this on paper?
That is, you've drawn lots of trees on paper, filled them with example necklaces in the way the problem describes them, and know how to make the necessary transformations to arrive at the answer.
If you haven't done this yet, then you're worrying about the solution before you're ready.
As salam suggests above, the first thing to do is to know how to solve this using pen & paper. Once you know that, then you know the required algorithm which can then be translated into a program design and hence into code. Until you know the algorithm from solving this using pen/paper, don't even think about code.
Mechanically, a tree is just like a linked list with 2 pointers instead of one.
solving the problem is unrelated to the data structure. In general most problems can be solved with any sort of data structure, the difference is how clean that makes the code or how efficiently it runs or both (eg doing something in a vector where you have to move the whole vector every few iterations is slow, but it will WORK). So, as already said, you must figure out how to solve the problem in steps you can translate to a computer ... then how you store your data as you resolve it is normally a decision you get to make but they made it for you here, so you use a tree and like it :P
from what little I know so far (feels like you paraphrased a portion of a bigger question) the answer feels like 'degenerate' tree (a linked list!).
|
|
solving the problem is unrelated to the data structure. In general most problems can be solved with any sort of data structure, the difference is how clean that makes the code or how efficiently it runs or both (eg doing something in a vector where you have to move the whole vector every few iterations is slow, but it will WORK). So, as already said, you must figure out how to solve the problem in steps you can translate to a computer ... then how you store your data as you resolve it is normally a decision you get to make but they made it for you here, so you use a tree and like it :P
from what little I know so far (feels like you paraphrased a portion of a bigger question) the answer feels like 'degenerate' tree (a linked list!).
Last edited on
Topic archived. No new replies allowed.