Can anyone pls tell me how to optimise this code : CodeChef: Practical coding for everyone
I am using Merge Sort AFAIK its the best sorting algorithm for time complexity but still Code Chef compiler says time limit exceeded. Kindly help me out in optimising it !
in the given test case
3
1 2 3
can i can do it in 2 steps?
by stopping 3 for the first
2 3 3
and now stopping 2 and 3 we get
3 3 3@Vartult: You can’t stop 2 numbers at a time according to the question,“choose some worker and increase by 1 salary of each worker, except the salary of the chosen worker”.Here it is given as worker and not as workers. So 2 3 3 >>> 3 4 3 >>> 4 4 4
#include
#include<stdio.h>
#include<conio.h>
using namespace std;
int main()
{
int t,n,a[100],small=10001,sum=0,tot_sum=0;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n;
for(int j=0;j<n;j++)
{
cin>>a[j];
if(small>a[j])
{
small=a[j];
}
}
for(int k=0;k<n;k++)
{
sum=a[k]-small;
tot_sum+=sum;
}
cout<<tot_sum;
}
}
…
Its output is correct …why it is not getting accepted
here is my approach using binary_search!
def main():
#codechef question SALARY
t = input()
t = int(t)
while t > 0:
n = input()
n = int(n)
val = list(map(int, input().split(" ")))
initial_sum = sum(val)
min_value = min(val)
left = 0
right = 10000000000
while left <= right:
mid = (left + right) // 2
may_be = initial_sum + (mid * (n-1))
mean = may_be / n
diff = mean - min_value
if diff == mid:
break
elif diff < mid:
right = mid - 1
else:
left = mid + 1
print(mid)
t -= 1
if name == ‘main’:
main()
Can anyone please tell me the derivation of that formula?
I am getting correct ans for my test case. But codechef compiler is giving time sigtstp error.
int T,N,moves,minW;
long sum = 0;
cin >> T;
for(int t=0; t<T; t++)
{
cin >> N;
vector<int> W(N);
for(int i=0; i<N; i++)
{
cin >> W[i];
sum += W[i];
}
minW = *min_element(W.begin(),W.end());
moves= sum -N*minW;
cout <<moves << endl;
}
return 0;
}
Actually you get TLE and it is expected for your solution.
The test case where your program works too slow is described in the editorial. But I repeat here:
T = 100
N = 100 for each test
salaries are {0, 10000, 10000, …, 10000} for each test
Consider test case:
3
0 2 2
The answer is 4 but your answer is 2 if I understand all properly.
I have added DRGNBOOL and LECANDY. Yours both seems too straightforward like just do what is written in the problem statement. But thanks for your effort.
Actually, the only your mistake is that you did not print the newline after the answer for each test. Fixing this give AC:
http://www.codechef.com/viewsolution/1724864
I was noticed this during the contest but, of course, I could not pointed out this to you.
Oh Dear Lord!!! Thanks anton_lunyov for answering. I was baffled whether there is something wrong with my approach because this is such an easy problem. Thanks again.
hi anton_lunyov, I am getting a wrong answer despite putting a new line character.
http://www.codechef.com/viewsolution/1724887
Can you please guide.
hi… don’t bother. I got my mistake 
let 7,8,12 then to make all the numbers equal, we’ll have to keep 12 as it is and increase the others ,otherwise if we’ll increase all the numbers then, they never gonna be equal .
7,8,12 increase first and second number
8,9,12 increase first and second number
9,10,12 increase first and second number
10,11,12 increase first and second number
11,12,12 increase only first number
12,12,12 all are equal.
so keep the max constant and increase all the other numbers or
in other words we can say decrease the max by 1 and then increase all the numbers by 1. max-1+1=max
You are wrong.
We can’t get 12,12,12 from 11,12,12.
Next we should increase 11 and 12 to get 12,13,12
and then we increase 12 and 12 to get 13,13,13.
yup…thnx a lot.
yup!
thank you
this one is a lot simple and better explanation than the above