Utkarsh.25dec's blog

Invitation to CodeChef January Starters 25(Rated for Div 2 & 3) — 9th Februaury
By Utkarsh.25dec, 3 years ago, In English

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!

  • Vote: I like it
  • +35
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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}$$$
    → Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply