You are not logged in. Please login at www.codechef.com to post your questions!

×

RKABOL04 - Editorial

PROBLEM LINK:

Practice
Contest

Author: ravikiran0606
Editorialist: ravikiran0606

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

COMBINATORICS, MATH

PROBLEM:

Given an equation X1 + X2 + ... + XN = K and an array of N numbers a1,a2,...,aN. The task is to find the number of whole number solutions satisfying the given equation such that Xi >= ai for all i (1<=i<=N). Since the no of solutions can be large, print them modulo 109 + 7.

EXPLANATION:

In this question, we can easily find the case for no solution that if $\displaystyle\sum_{i=1}^{N} X_i$ > K, then no solution exist for that equation. In all other conditions, we can find at least one whole number solution. In order to find the number of whole number solutions for the given equation. Let p = $\displaystyle\sum_{i=1}^{N} X_i$ - K. Now our actual problem reduces to the problem of finding the no of whole number solutions in the new equation, Y1 + Y2 + ... + YN = p without any constraint. The no of solutions to the new equation is similar to the number of ways of distributing p chocolates to N children which can be done in $\binom{p+n-1}{n-1}$ ways.

AUTHOR'S SOLUTION:

Author's solution can be found here

This question is marked "community wiki".

asked 13 Mar, 23:03

ravikiran0606's gravatar image

4★ravikiran0606
41
accept rate: 0%

edited 15 Mar, 13:37

admin's gravatar image

0★admin ♦♦
19.6k349497539

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,198
×1,626
×854
×19
×19
×19

question asked: 13 Mar, 23:03

question was seen: 145 times

last updated: 15 Mar, 13:37