Problem : Find a nonempty subset of the given multiset with the sum of elements divisible by the size of the original multiset or state that the required subset doesn’t exist.
Explanation :
Claim:
There is always such a subset. Moreover, there is always a consecutive subsegment of any sequence of numbers that corresponds to the multiset’s elements with the sum divisible by the multiset’s size.
Proof:
Let’s denote a1 + a2 + … + ak by bk. So, we obtain:
b0 = 0
b1 = a1
b2 = a1 + a2
…
bN = a1 + a2 + … + aN
It is easy to see that aL + aL+1 + … + aR (L <= R) equals to bR - bL-1. Therefore, if there are two values with equal residues modulo N among b0, b1, …, bN then we take the first one for L-1 and the second one for R and the required subsegment is found.
There are N+1 values of bi and N possible residues for N. So, according to the pigeonhole principle the required subsegment will always exist.
Some implementation details:
While calculating the value of bi you should use that bi equals to bi-1 + ai, that allows you to precompute all bs in O(N) time. Practically, only bi modulo N are important. Then you can just sort the numbers along with their indices in order to find the duplicates among the residues.
from __future__ import division
def read_mapped(func=lambda x:x):
return map(func, raw_input().strip().split(" "))
def read_int():
return int(raw_input().strip())
def read_str():
return raw_input().strip()
def read_float():
return float(raw_input().strip())
T = read_int()
def solve(a, n, s):
acc = 0
for elem in s:
acc += original_a[elem]
if acc%n==0 and acc!=0:
return s
if a==[]:
return False
return solve(a[:-1], n, s) or solve(a[:-1], n, s+[len(a)-1])
for case in xrange(T):
n = read_int()
a = read_mapped(int)
global original_a
original_a = a
res = solve(a, n, [])
if res is False:
print "-1"
else:
print len(res)
print " ".join(map(lambda a: str(a+1), res))
but what about “any number can be taken in the subset no more than once.”?
it is slightly misleading i thought that repetition of number is not allowed ,say, 2 can be used only once.
this was supposed to be a subset and the above solution seems to be for subsequence of the set??
subsequence is {a[i],a[i+1], … , a[j]} for 1<=i<=j<=n and subset is {a[i1], a[i2], a[i3], … , a[ik]} for 1<=k<=n…
You are given a string S and you have to count how many subsequence of this string does not have same character at adjacent positions. Subsequence of string S can be obtained from deleting zero or more characters from string S.
Example: let, S = “aba” then possible subsequences are “a”, “ab”, “aba”, “aa”, “b”, “ba”, “a” and “”(empty string). But among the subsequences all are valid except “aa”.
Input
First line of the input contains 1 ≤ T ≤ 100 number of test cases. Each of the following T lines contains a string which have positive and contains at most 1000 lowercase English letters.
Output
Output a single line containing case number and the number of subsequence. As the result can be large print it by modulo 100009.
While implementing the technique presented in the editorial, sorting is not required to find duplicates(though it will easily pass). First we create an array positions[] and fill it with -1’s. Then we loop through the array in which we stored our multi-set, calculating the corresponding b values at each step. When we’re at position i in the loop, let bi%n=j. Now if positions[j] is equal to -1, we set positions[j] = i. If it’s not equal to -1, then we’ve found our duplicate. That let’s us solve the problem in O(n) time.
If the problem were instead this: Given a multi-set of size n, find a subset of this which is divisible by a number m such that 0<m<n. The pigeon-hole principle still holds, and we could solve using the same method. (In fact we can say that there must exist atleast n+1-m distinct such subsets)
Amazing isn’t it?
Could someone discuss an efficient method to solve the problem if m>n. (when the pigeon-hole principle wont hold). More efficient than the obvious O(n^2) dynamic programming solution?
Learned a lot from this problem! It was very insightful Thanks!
@all i was not able to recognise the use of pegion hole principle when i first saw this problem and so i thought differently and came up with a new idea (new to me not neccesarily for all) which is not very efficient but can be used to get 61 points and can be optimised to get 100 points.
here is my approach
firstly i thought any sum consists of either (one element + some existing sum ) or one element. so i maintained two arrays one for the sum and other for index of the new element.if it consists of only one element then i marked sum as -1 for that value . now i need to mark the sum only once and as soon as i get zero mark field marked it means it is possible to form such a subset from the existing elements. here is the implementation of my approach.
it is quite easy to think and can be solved other problems too so have a look you will learn something new.
#include<bits/stdc++.h> #include
using namespace std;
vector< vector > mat; #define all(b) b.begin(),b.end()
vector arr,S,sum,idx;
int main(){
There is always such a subset. Moreover, there is always a consecutive subsegment (SUBSEQUENCE) of any sequence of numbers that corresponds to the multiset’s elements with the sum divisible by the multiset’s size
@kanansa, maybe I misunderstood the problem statement, as it was written: “If the required subset exists, output two lines. Output the size of the subset on the first line and output the list of indices of the multiset’s element that form the required subset. Of course, any number can be taken in the subset no more than once.”
I have difficulty in understanding the claim and its proof. Please can someone give a intuitive reasoning with an example ? An example will make things more clear. Thank you!
Thanks!