Task 296 Tree Value
Back to General discussions forum
Don't know if it is allowed to ask for a hint, but I am stuck with this problem. Test data from example gives the right answer, but test data for which I need to find the answer gives a wrong one. I've tried using 1024-bit integer (from boost), taking modulo of all node values, but nothing has worked. My algorithm is straightforward -- it recursively traverses through all nodes calculating their values, and I can't understand what I am getting wrong here. Any advice will be appreciated.
Okay, seems like using integers with unlimited precision (thanks for tommath library) solves the problem, but I don't feel like it's a viable approach (the program used 10 MB of memory and took about half a minute to finish with full optimisation).
Don't know if it is allowed to ask for a hint
I believe it's quite ok, just the matter whether someone could and want provide a hint :)
My algorithm is straightforward
generally problems created by Clive (aka CSFPython) may need some cunning, also they (unless I have forgotten something)
never require using long arithmetics :)
take this for the first hint as I see with some surprise I solved it myself after some struggle, but can't remember the idea at once.
Code provided by Clive for data generator in this problem works in Python (which is 10-20 times slower compared to natively compiled C/C++) and seemingly does the trick in about a second.
Well, if using built-in 64-bit integer, my code gives the answer in a second too, though a wrong one. But having looked through other people's solutions I got the idea. I somehow missed that min and max elements sholud be searched among values of nodes and not their modulo (as far as I think)
A small hint is that there are other ways to compare large numbers without storing their entire value. Think about certain mathematical properties and transformations
I see you have already solved it. You can check my solution to see how to solve this without big numb in C++.
Thank you, guys, I understood the idea with logarithms. It's a bit shame for me that I didn't figure it out in the first place.