Author: Akshay Padte
Tester: Rushang Gajjal
Editorialist: Rushang Gajjal
Given a music sequence and malicious sequence, the integral multiples of the malicious sequence present in the music sequence have to be removed and the number of such sequences removed has to be printed.
Note : An Integral Multiple of a malicious sequence is obtained by multiplying the amplitudes of each tone by the same integer leaving the frequencies i.e. letters are left unchanged.
We can separate the music and the malicious sequences into amplitudes and frequencies arrays.
n : Length of music sequence
m : Length of malicious sequence
freq : Frequency Array for music sequence
amp : Amplitude Array for music sequence
freqm : Frequency Array for malicious sequence
ampm : Amplitude Array for malicious sequence
The amplitudes are present at odd positions and the frequecies are present at even positions.We iterate from 1 to 2n to input the entire sequence because there are n tones and each tone has a frequency and amplitude.
for i from 1 to 2*n: if i%2=0: amp.append(input()) else: freq.append(input())
Similarly input the malicious sequence in freqm and ampm.
We have to perform an algorithm similar to string matching.
First Iterate over the entire music sequence and maliciuos sequence and find the part of the music sequence which has the same frequencies in the same order as malicious sequence.
for i from 1 to len(amps)-m: for j from 1 to m: if(freq[i+j]!=freqm[j]): break
We iterate till len(amps)-m because we have to match sequence of size m.Now if the for loop runs without break for a certain pair of i and j we have to check whether the amplitudes of the matched sequences are same or integral multiples of each other. If all conditions are satisfied count is incremented.
ratio = 0 for j from 1 to m: if amp[i+j]%ampm[j]!=0: break if j==0: ratio = amp[i+j]/ampm[j] else: if(amp[i+j]/ampm[j]!=ratio): break else: count++
In the above code first we initialize the value of ratio to the ratio of amplitudes of the i-th tone of music sequence and 1-st tone of malicious sequence.Then check whether the ratios of the following amplitudes of the tones are same as ratio.If the entire malicious sequence is iterated satisfying the ratios of amplitudes, increment the count variable.
O(n*m) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.