Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Importance of Mathematical intuition!
def main():
n,m=map(int,raw_input().rstrip().split(' '))
a=map(int,raw_input().rstrip().split(' ')) # a[i] -> song number i+1
# make the array b where b[j] -> number of songs grp j is performing
b=[]
for i in xrange(m+1):
b.append(0)
changes = 0 # minimum number of changes
# KEY IDEA : at the end, all songs to be played by 1 to m
# Question : How to keep track of the changed list
# idea : ? - make a dictionary of bands 1->m, and songs from 1->n as dictionary for each!
bands_dict={}
for i in xrange(m+1):
bands_dict[i]={}
for i in xrange(n):
if a[i]<=m:
bands_dict[ a[i] ][ i+1 ] = 1
b[ a[i] ] +=1
else:
bands_dict[0][i+1]=1
b[0]+=1
# debug
# print b
# print bands_dict
# empty b[0]
min_index=1 # min_index -> band
min_value=b[1] # min_value -> number of songs played by the band
prev_min_index=-1
prev_min_value=-1
prev_replaced_song=-1
print b
flag=0
while b[0]>0:
'''
not working for the edge case
5 4
3 1 49598 52227 762868
'''
# we don't need to empty b[0], use prev min here too to break the loop!
# find minimum from b[1] to b[m]
for i in xrange(1,m+1):
if b[i]<=min_value:
min_index=i
min_value=b[i]
# stopping condition, to reverse the stuff
if flag==1:
if min_value<=prev_min_value and min_value!=0:
bands_dict[0][ prev_replaced_song ]=1 # to_replace song added in the band min_index
bands_dict[prev_min_index].pop(prev_replaced_song) # to_replace song deleted from the band 0 (others)
b[0]+=1
b[prev_min_index]-=1
changes-=1
break
# place 1 value from b[0] to b[min_index]
# ? - which song?!
replaced_song = bands_dict[0].keys()[0] # song to be replaced
bands_dict[min_index][ replaced_song ]=1 # to_replace song added in the band min_index
bands_dict[0].pop(replaced_song) # to_replace song deleted from the band 0 (others)
b[min_index]+=1
b[0]-=1
changes += 1
flag=1
prev_replaced_song=replaced_song
prev_min_index=min_index
prev_min_value=min_value
# keep on finding max & min, doing the replacements
# until we reach the stable state
# looping on till we find the stable state!
flag=0 # first time
prev_replaced_song = -1 # first time
prev_min_index=-1
prev_max_index=-1
prev_min_value=-1
prev_max_value=-1
print b
while b[0]==0:
min_index=1
max_index=1
min_value=b[1]
max_value=b[1]
for i in xrange(1,m+1):
if min_value>=b[i]:
min_index=i
min_value=b[i]
if max_value<=b[i]:
max_index=i
max_value=b[i]
# stopping condition, to reverse the stuff
if flag==1:
if min_value<=prev_min_value:
bands_dict[prev_max_index][ prev_replaced_song ]=1 # to_replace song added in the band min_index
bands_dict[prev_min_index].pop(prev_replaced_song) # to_replace song deleted from the band 0 (others)
b[max_index]+=1
b[min_index]-=1
changes-=1
break
if min_index==max_index:
prev_min_index=min_index
prev_max_index=max_index
prev_min_value=min_value
prev_max_value=max_value
break
replaced_song = bands_dict[max_index].keys()[0] # song to be replaced
bands_dict[min_index][ replaced_song ]=1 # to_replace song added in the band min_index
bands_dict[max_index].pop(replaced_song) # to_replace song deleted from the band 0 (others)
b[min_index]+=1
b[max_index]-=1
changes+=1
prev_replaced_song = replaced_song
prev_min_index=min_index
prev_max_index=max_index
prev_min_value=min_value
prev_max_value=max_value
flag=1 # other times!
# maximum possible value of minimum -> prev_min_value
# minimum number of changes -> changes
print prev_min_value, changes
new_a=[]
for i in xrange(n+1):
new_a.append(0)
for key in bands_dict:
for elm in bands_dict[key]:
new_a[elm]=key
for i in xrange(0,n+1):
print new_a[i],
print
if __name__=='__main__':
main()
def main():
n,m=map(int,raw_input().rstrip().split(' '))
a=map(int,raw_input().rstrip().split(' '))
ls=[]
for i in range(m+1):
ls.append([])
for i in range(n):
if a[i]>m:
ls[0].append(i+1)
else:
ls[ a[i] ].append(i+1)
for i in range(1,m+1):
while len(ls[i])>(n/m):
elm=ls[i].pop()
ls[0].append(elm)
changes=0
for i in range(1,m+1):
while len(ls[i])<(n/m):
elm=ls[0].pop()
ls[i].append(elm)
a[elm-1]=i
changes+=1
print n/m, changes
for elm in a:
print elm,
print
if __name__=='__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment