### alex.alex's blog

By alex.alex, 8 years ago, translation, , Hi to everybody....

Today will be another round of COCI.
Those wishing to participate can enter/register here
To LogIn choose COCI 2011/2012 - Contest #2.

Good luck to all in advance...

UPD: Here are results. coci, Comments (8)
 How to solve the 5th problem?
•  8 years ago, # ^ | ← Rev. 2 →   First, notice that the graph of dependencies between variables is a forest. We call b a "left child" of a if a is the Xi of b. Similarly, b is a "right child" if a is the Yi of b.Now consider variable a, value i, and the subtree rooted in a. We want counter[a][i] contain the number of all possible value assignments of the variables in the subtree such that a=i and that each of them respects the constraints (given by Xi and Yi).We notice that this value can be computed easily based on the values of the children of a. It's the product of sum(c,i) for each child c of a, where sum(c,i) is the sum of counter[c][1..i] if c is a right child or the sum of counter[c][i..100000] if c is a left child.So, through recursion (well, actually dynamic programming), we can compute counter[a][i] for all a and for all i. To get the final result we multiply, for all roots r of the trees, the sum of counter[r][i] for all values of i.Don't worry, it sounds more complicated than it actually is!The complexity should be O(N) (with a factor of 100000 :) and it actually runs really fast: my implementation has an execution time of max. 0.04s.
•  I forgot to mention that, obviously, counter[a][i] is zero when iYa.
•  The Node may have more than one left-child or right-child .. How to solve it ..?
•  To compute the value of counter[a][i] you iterate over all children of a (regardless of their type) and for each of them you compute the value of sum(c,i) (where c is the child you're currently iterating on). As I said, sum(c,i) is:counter[c] + ... + counter[c][i] if c is a right child of acounter[c][i] + ... + counter[c] if c is a left child of a (this hardcoded constant is the maximum value of Xi and Yi)When you have the values of sum(c,i) for all children, you multiply them all to get the value of counter[a][i].I hope it's more clear now!
•  8 years ago, # ^ | ← Rev. 2 →   Thanks a lot ..I'll have a try ..-----------How about this input: 32 31 ab aYou can't get a fix count[r][i] for some node ..
•  The input is invalid: at most one of Xi and Yi is a reference to another variable!
 These problems are easy. But since I write a function to output long long, and it doesn't work with negative number, I lost a lot of points. TAT...