alex.alex's blog

COCI 2011/2012 Contest #2
By alex.alex, 12 years ago, translation, In English
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.
  • Vote: I like it
  • +37
  • Vote: I do not like it

12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve the 5th problem?
→ Reply
  • 12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • 12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      I forgot to mention that, obviously, counter[a][i] is zero when i<Xa or i>Ya.
      → Reply
      • 12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        The Node may have more than one left-child or right-child .. How to solve it ..?
        → Reply
        • 12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like 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][1] + ... + counter[c][i] if c is a right child of a
          • counter[c][i] + ... + counter[c][100000] 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!

          → Reply
          • 12 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Thanks a lot ..
            I'll have a try ..

            -----------

            How about this input:

            3
            2 3
            1 a
            b a

            You can't get a fix count[r][i] for some node ..

            → Reply
            • 12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              The input is invalid: at most one of Xi and Yi is a reference to another variable!
              → Reply
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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...
→ Reply