Help Needed in Number of steps (Hackerearth)

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	170
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	154
7	Dominater069	154
9	awoo	153
10	luogu_official	152

Intuition

Code

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n,maxi=INT_MIN;
    cin>>n;
    vector<int> a(n,0),b(n,0);
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
        maxi=max(maxi,a[i]);
    }
    vector<int> freq_map(maxi+1,0);
    for (int i = 0; i < n; i++)
    {
        cin>>b[i];
        int temp = a[i];
        freq_map[a[i]]++;
        while (a[i]>b[i])
        {
            freq_map[a[i]-b[i]]++;
            a[i]-=b[i];
        }
        a[i]=temp;
    }
    int ans=0,fin=-1;
    for (int i=maxi;i>=0;i--)
    {
        if(freq_map[i]==n){
            fin=i;
        }
    }
    if(fin==-1){
        cout<<-1<<endl;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        ans+= (a[i]-fin)/b[i];
    }
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);   
    // freopen ("text_file.txt", "r", stdin);
    int t=1;
    // cin>>t;
    for (int i = 0; i < t; i++)
    {
        solve();
    }

    return 0;
}

It is giving me WA on Input #4 and TLE on Input #5 and Input #6. I tried for hours but was unable to find a problem with my solution. And even in the worst-case scenario where

n = 5000
every ai=5000
every bi = 1

It has an O(n*max(ai)) solution which should be feasible for these constraints. A hint or Advice is appreciated.

Comments (3)

Write comment?

CodingKnight

3 years ago, # |

← Rev. 6 →

There is an issue with the test data of this problem.

In input #5, $$$a_{4914} = b_{4914} = 0$$$.

In input #6, $$$b_{1153} = b_{4400} = 0$$$ while $$$a_{1153} = a_{4400} = 500$$$.

This implies that the correct constraints should be

$$$1 \leq n \leq 5000$$$ and $$$0 \leq a_{i}, b_{i} \leq 5000$$$

A simple brute force solution for the problem should be as follows. Let the final value of all elements in the array be equal to $$$c$$$, and the minimum value of $$$a_{i}$$$ for $$$1 \leq i \leq n$$$ be equal to $$$m$$$. Since the only operation allowed is to decrease $$$a_i$$$ by $$$b_i$$$, the maximum value of $$$c$$$ can never be larger than $$$m$$$. Hence, it is sufficient to iterate over all possible values of $$$c$$$, where $$$0 \leq c \leq m$$$, and find for each value of $$$c$$$ the summation of the number of steps $$$x_i$$$, where $$$x_i \geq 0$$$, such that the final value of $$$a_{i}$$$ is equal to $$$c$$$. By definition, $$$c = a_i - x_i \times b_i$$$, which means that $$$x_i = \frac{a_i-c}{b_i}$$$. Since $$$x_{i}$$$ has to be an non-negative integer number, a necessary condition that the final value of the array elements is equal to $$$c$$$ is that $$$a_i-c$$$ has to be divisible by $$$b_i$$$ for all $$$1 \leq i \leq n$$$, where $$$b_i \neq 0$$$. Finally, if $$$b_{i} = 0$$$ for some $$$1 \leq i \leq n$$$, then it is not possible to decrement $$$a_{i}$$$, and the final value of the array elements has to be equal to $$$a_{i}$$$. If $$$a_i = 5000, b_i = 1$$$ for all $$$1 \leq i \leq n$$$, then this brute force solution should run for $$$5000\times5000$$$ iterations, where each iteration requires $$$O(1)$$$ operation.

→ Reply

Sourabh-Choudhary

3 years ago, # ^ |

Thanks a lot.

With pleasure.

Sourabh-Choudhary's blog