ammar_hammoud's blog

Kolya and Tanya Problem
By ammar_hammoud, history, 16 months ago, In English

Hello CF community, I was trying to solve this problem 584B - Kolya and Tanya , I saw that my logic gives wrong answers but I don't know why, my friends' solutions was like find the total cases, subtract the invalid cases but I was thinking of finding the valid cases immediately, here's how I think:
Let's take $$$n=2$$$ for example:
I can either make $$$a_0, a_2, a_4$$$ valid or $$$a_1, a_3, a_5$$$ valid, I know that for every $$$3$$$ vertexes (which are to be valid) I have $$$3^3 - 7 = 20$$$ valid cases, as the invalid cases are:
1. ($$$1, 2, 3$$$)
2. ($$$1, 3, 2$$$)
3. ($$$2, 1, 3$$$)
4. ($$$2, 3, 4$$$)
5. ($$$3, 1, 2$$$)
6. ($$$3, 2, 1$$$)
7. ($$$2, 2, 2$$$)
and for the rest of the vertexes the values I can take are either $$$1, 2,$$$ or $$$3$$$, which means $$$3^{3n-3}$$$ options, so I have $$$n$$$ options ($$$a_0$$$, $$$a_1$$$ in case $$$n=2$$$) with $$$20$$$ valid cases, and for every options of this I have $$$3^{3n-3}$$$ options $$$ \rightarrow $$$ $$$(20\times 3^{3n-3})\cdot n$$$.
Can anyone tell me what's wrong?

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

But you also need to consider case when both triplets are valid, not only one. So in general case you will need to sum all possible variants where number of valid triplets are 1...n. Therefore find the total cases, subtract the invalid cases is much simpler

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you show me math expression please?, or the formula to correct my solution

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Something like $$$\sum_{k=1}^nC_k^n\cdot20^k\cdot7^{n-k}$$$, as there is 20 valid and 7 invalid cases for one triplet

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you!
        but won't the case of both triples are valid be contained in my solution as it's greater?
        I mean if we consider $$$a_0$$$ for example then the other triple will $$$3^3$$$ which contains $$$20$$$

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, but those are counted multiple times. That's why your solution is incorrect.

          Consider $$$n = 2$$$ and the array $$$a = [1, 1, 1, 1, 1, 1]$$$. Both triples are good. When you're counting arrays with the triple $$$a_0, a_2, a_4$$$ being good, you will count the array $$$[1, 1, 1, 1, 1, 1]$$$. When you're counting arrays with the triple $$$a_1, a_3, a_5$$$ being good, you will also count the array $$$[1, 1, 1, 1, 1, 1]$$$. So this array gets counted twice instead of once.

          → Reply