Can anyone please explain me how pigeonhole principle is used in this question: https://www.spoj.com/SZTE11T1/problems/HALLOW/
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Can anyone please explain me how pigeonhole principle is used in this question: https://www.spoj.com/SZTE11T1/problems/HALLOW/
Название |
---|
We have
n
numbers, from which we should choose a subset of numbers such that there sum moduloc
is 0.Let's compute cumulative sums of these
n
numbers and store in arrays
, hences[i] = (a[0] + a[1] + .. a[i])
.The first observation is that
n >= c
and we have onlyc
distinct possible values of remainders upon dividing by c ([0, c-1]
). This means that if we consider moduloc
values for alln
numbers of arrays
, 2 possibilities are there-There is some
s[i]
for whichs[i]%c = 0
.If the above condition does not hold then, we are left with only
c - 1
distinct possibilities of remainders and greater than or equal toc
numbers (sincen >= c
). With pigeon-hole analogy, we havec-1
holes and at leastc
pigeons. So there will be at least one hole with 2 or more pigeons, that is at least one remainder will be repeated.In the first case, the answer is trivial, just return the first
i
indexes such thats[i] % c = 0
.For the second case, let's say
i, j, (i < j)
are the two indexes such thats[i] % c = s[j] % c
. Now consider all indexes fromi + 1
toj
. Sum of all numbers fromi + 1
toj
is given bys[j] - s[i]
. We can see that(s[j] - s[i]) % c = 0
.thanks! got it.
Can you please explain the line "consider all the numbers between 2 numbers which have same modulo c (both numbers inclusive). Sum of all these numbers modulo c will be 0"?I can not understand how we reach to this and how to prove it.
I missed a very important part in the previous comment, please see the updated comment. :)
Whenever a number is divided by c there are only c possible remainders,
0 , 1 , 2 , 3 , .... , c-2 , c-1
.Let array of n numbers be
a1, a2, a3 .... an
, simply make a cumulative sum array S ,S[i] = (a[i] + S[i - 1]) % c
.Given condition
n >= c
, Now there aren ( >= c)
sum elements(S.length)
and c possible values so by pigeonhole principle ....there will be at least a 0 present, in that case answer is all the elements till that index (when cumulative sum is 0).
Or there will be two sum elements Si and Sj such that
Si == Sj
, in that case answer will be the subarray from i+1 to j (since(Sj - Si + c) % c = 0
) .Hence whenever
n >= c
answer is always possible else we will have to use dp to calculate it (for which the constraint is too large).thanks that was a great help!