REMADJ-Editorial

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

3 Likes

Thanks for this corner case my code is failing.

1 Like

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

1 Like

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

Thanks a lot for pointing out the fault

2 Likes

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

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

1 Like

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

#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.

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

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

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

working fine all the these test cases

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:

@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

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

1 Like

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

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

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

1 Like

thanks now i got my mistake

1 Like