Malicious Music-Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest

Author: Akshay Padte

Tester: Rushang Gajjal

Editorialist: Rushang Gajjal

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

String manipulation

PROBLEM:

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.

EXPLANATION:

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.

Time Complexity:

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.

4 Likes