I wrote this code for solving the Chef and Mover Problem. I tested it against all the inputs along with some other inputs, I tried submitting my code using Brute force method which showed TLE, so I again tried implementing it another way, which worked for inputs but the code chef compiler showed 2 AC and 4 WA, can somebody please help me to understand where did I go wrong…
Here is the code
#include<stdio.h>
#include<stdlib.h>
struct num{
int pos;
int data;
};
int compare(const void *s1, const void *s2)
{
struct num *e1 = (struct num *)s1;
struct num *e2 = (struct num *)s2;
return e1->data - e2->data;
}
void process(struct num data[],int D,int N) {
int i;
int swaps=0;
for(;;){
qsort(data, N, sizeof(struct num), compare);
if((data[N-1].data==data[0].data)){
printf("%d\n",swaps);
return;
}
if(abs(data[N-1].pos-data[0].pos)==D){
data[N-1].data-=1;
data[0].data+=1;
swaps++;
}
else{
printf("-1\n");
return;
}
}
}
int main(void){
int x;
scanf("%d",&x);
while (x-- > 0) {
int n,i,d;
scanf("%d",&n);
scanf("%d",&d);
struct num numbers[n];
for (i = 0; i < n; i++) {
scanf("%d",&numbers[i].data);
numbers[i].pos=i;
}
process(numbers,d,n);
}
}
I think you misunderstood the question and over complicated it. Check out the editorial first, if that doesnt help, comment here.
oh haha Did I? xD okay I’ll check editorial it was my first challenge ever didn’t know we had editorials too 
1 Like
I didn’t really understood the editorial, can somebody help me?
Take this test case-
Input
1
5 1
1 1 1 1 6
Your Output
-1
Correct Output
10 (4+3+2+1)
First of all find the average of all the numbers in the array, which will tell you how much you have to decrease/increase a specific no. to get all the digits same in the array.
Now if the average Comes out to be floating, print -1 and break , i.e not possible for array to have all the digits same.
else:
use a for loop till n-d and for each element not equal to average, increase/decrease it to the shift required and consecutively decrease/increase the no. at index (i+d).
In the end check whether if only one element remains in the set of array which should be equal to the average we calculated.
Check my solution Here.
but in this the size of mover is 1. so how can we move from 6 to other elements, it should satisfy the i+d = j condition right??
Can you help with this code then, this is the one I wrote first, but this one Gave TLE, in this one I found the average first
#include<stdio.h>
void process(int arr[], int D,int N) {
int sum = 0;
int swaps = 0;
int i,j,k;
int len = N;
for (k = 0; k < len; k++) {
sum += arr[k];
}
int req = sum / len;
if (sum % len != 0) {
printf("-1\n");
return;
}
for (i = 0; i < len; i++) {
for (j = i + 1; j < len; j++) {
if (i + D == j) {
if (arr[i] < arr[j] && arr[j] > req && arr[i] != req) {
do {
arr[i] += 1;
arr[j] -= 1;
swaps++;
} while (arr[i] != req);
} else if (arr[i] > arr[j] && arr[i] > req && arr[j] != req) {
do {
arr[j] += 1;
arr[i] -= 1;
swaps++;
} while (arr[j] != req);
}
}
}
}
printf("%d\n",swaps);
}
int main(void){
int x;
scanf("%d",&x);
while (x-- > 0) {
int n,i,d;
scanf("%d",&n);
scanf("%d",&d);
int num[n];
for (i = 0; i < n; i++) {
scanf("%d",&num[i]);
}
process(num,d,n);
}
}
You can move from index 5 to index 4, then index 4 to index 3 and then index 3 to index 2 and so on.
BUT you will get TLE if you do it step by step. Compute how much you need to transfer to the index at once. You can see my code for clarity, look it up from the profile.
Instead of increasing your arr[i] by 1 until it reaches req, why dont you increase it directly to the req value. you can skip your unnecessary loop time waste here. I hope it helps.
but then, if I would increase it directly, then how to keep track of no. of moves then?
Number of moves= (new value -old value). OR, we know that we only need to keep value=avg on that index. So ultimately no. of moves done is “a[i] - avg”