REMADJ-Editorial

editorial
, , , ,
21

I was also stuck on 1st test case . By using your given test case ,i got right answer . Thanks for your help.

3 Likes
22

Thanks for this corner case my code is failing.

1 Like
23

Cā€™mon! How can you do 8? The max no. of operations you can do is n-1

1 Like
24

Solution I solved it without using prefix sumsā€¦ Basic idea is iterate through factors of sum in increasing orderā€¦ Answer is the least factor which we can make array equal toā€¦ Remember thereā€™s a special case if sum is zero

1 Like
25

Thanks a lot for pointing out the fault

2 Likes
26

One thing which I have changed in my solution to make it little bit optimized is to iterate over y not x as x.y=S so y is also a factor and but y has one other bound which is it must be <=n as it is the size of final array which must be <= size of initial array(n).
In my Solution, First I have find out all the factors which are <=n of S then in other for loop for all those number I have checked whether they are valid or not in O(N).
Here is the link for my solution:
https://www.codechef.com/viewsolution/57952211

27

i am also getting WA on only test case 1.
i tried 45 time but still get WA on test case first .

1 Like
28

Hey @robinsingh301
I think you got the input wrong it is
1
7
1 1 1 3 -2 2 -4

29 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pd;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<pd> vpd;
typedef vector<string> vs;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORb(i, a, b) for (int i = (a); i >= (b); i--)
#define trav(x, a) for (auto &x : a)
#define travc(x, a) for (auto const &x : a)

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

const int int_max = numeric_limits<int>::max();
const int int_min = numeric_limits<int>::min();
const ll ll_max = numeric_limits<ll>::max();
const ll ll_min = numeric_limits<ll>::min();
const int MOD = 1000000007;
const double PIE = 3.14;
const char nl = '\n';

void setIO(string name = "")
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (name.size())
    {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

void factors(int sum, vi &fac)
{
    for (int i = 1; i * i <= abs(sum); i++)
    {
        if (abs(sum) % i == 0)
        {
            fac.push_back((sum < 0 ? -i : i));
            if (i * i != abs(sum))
                fac.push_back(sum / i);
        }
    }
}

int main()
{
    setIO();

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi v(n + 1);
        v[0] = 0;
        FOR(i, 1, n + 1)
        {
            cin >> v[i];
            v[i] += v[i - 1];
        }
        vi fac;
        factors(v[n], fac);
        if (v[n] == 0)
            fac.push_back(0);
        int ans = 0;
        FOR(i, 0, sz(fac))
        {
            int lastInd = 0, tempAns = 0;
            FOR(j, 1, n + 1)
            {
                if (fac[i] != 0 && tempAns == abs(v[n] / fac[i]))
                    break;
                if (v[j] - v[lastInd] == fac[i])
                {
                    tempAns++;
                    lastInd = j;
                }
            }
            ans = max(ans, max(1, tempAns));
        }
        cout << n - ans << nl;
    }

    return 0;
}

/***Author: Vishwajeet Prasad***/

Can someone point out, whatā€™s wrong in my code? Itā€™s failing on the testcases 1 and 10.

30

I am also unable to find any error in my code, giving WA on 1st test case onlyā€¦
https://www.codechef.com/viewsolution/57954193

31

Is there is some issue in first test case as my code works for each and every test case accept first one.
code attached below
solution

32

for those codes which are failing at testcase 1 only
try these testcases
1 1 1 -1 ans: 2
1 1 1 1 -2 ans: 3
1 1 1 1 1 -3 ans: 4

33

working fine all the these test cases

34 
import java.io.*;
import java.util.*;

class REMADJ{


	public static void main(String args[]) throws IOException,NumberFormatException{
		
		BufferedReader reader  = new BufferedReader(new InputStreamReader(System.in));

		int t =  Integer.parseInt(reader.readLine().replaceAll(" ",""));
		
		
		while(t>0)
		{
			int n = Integer.parseInt(reader.readLine().replaceAll(" ",""));
			int num=0;
			int isEqual=1;
			int prev=Integer.parseInt(reader.readLine().replaceAll(" ",""));
			int sum=prev;
			int max=prev;

			
			for(int i=0; i<n-1; i++){
				
				int input= Integer.parseInt(reader.readLine().replaceAll(" ",""));
				//
				sum = sum + input;
				if(input>max)
					max=input;
				if(input!=prev)
					isEqual=0;
				
				prev=input;		
			

			}
			
			
			if(n==2)
			{
				System.out.println("1");
				return;
			}
		
			sum = sum - max;
			
			if(isEqual==1){
				// means all elements are equal;

				System.out.println(0);
			}
			else{

				System.out.println(sum/max);

			}

			t--;		
		}	
			
	
	}
}

https://www.codechef.com/viewsolution/57843892

Can someone tell me why am I getting run time for this solution :frowning:

36

@vishwajeet7381
your code gives ans 5 on this testcase but i coudnā€™t find any way to do it in 5 steps
1
7
1 1 2 3 5 7 -1

1 Like
37

@jagdish_t19
Bro, you r really a saviour. Thanks a lot man.

1 Like
38

mine works for these 3 but still fails for testcase 1. solution

39

sir can you explain why my code is giving SIGSEGV for only one test case but running completely normal on my machine with g++ 9.4.0
this is my solution
https://www.codechef.com/viewsolution/57940893

40

Thanks you @akshitm16 for the testcase. After some modification it passed the test case 1.

1 Like
41

thanks now i got my mistake

1 Like