Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя Utkarsh.25dec

Invitation to CodeChef January Starters 25(Rated for Div 2 & 3) — 9th Februaury
Автор Utkarsh.25dec, 3 года назад, По-английски

We invite you to participate in CodeChef’s Starters 25, this Wednesday, 9th February, rated for Div 2 & 3 Coders.

Time: 8 PM — 11:00 PM IST

Joining me on the problem setting panel are:

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

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

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

please tell about how to solve COUNT ARRAYS problem? is it dp(guessing that becuase of small m ) or is it some data structure problem?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Try to solve a subproblem. Suppose you have a simple cycle of length x. What are the number of ways to assign the values of each node such that no two adjacent nodes have same value. If you need any further help you can refer to the editorial published

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

For count arrays, is it possible to find out the answer for the cycle using inclusion-exculsion? I tried but kept on getting WA.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    Yes, It can be solved using inclusion-exclusion. Let us label the edges as $$$\{1,2,...,n\}$$$ in the order. Also, let $$$ R \subseteq \{1,2,...,n\} \text{ and } S_R$$$ denote the number of ways of assigning values to the nodes such that values across the edges in $$$R$$$ are equal. Total number of ways $$$(f_n)$$$ of assigning values to n nodes in a cycle such that adjacent values are different can be computed as —

    $$$ f_n = \sum_{|R|=0} S_R - \sum_{|R|=1} S_R + \sum_{|R|=2} S_R - ... + (-1)^n\sum_{|R|=n} S_R$$$

    and,

    $$$\begin{equation} S_R=\begin{cases} m, & |R| = n.\\ m^{n-|R|}, & \text{else} \end{cases} \end{equation}$$$

    where, m is the number of possible distinct values to label each node.

    $$$\begin{equation} \begin{split} f_n & = m^n - \binom{n}{1}m^{n-1} + ... + (-1)^{n-1}\binom{n}{n-1}m + (-1)^nm \\ & = (m-1)^n + (-1)^n(m-1) \end{split} \end{equation}$$$
    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

i dont understand editorial of k distinct array....anyone pls explain ?

→ Ответить