Блог пользователя ammar_hammoud

Kolya and Tanya Problem
Автор ammar_hammoud, история, 16 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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$$$

        → Ответить
        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить