You are not logged in. Please login at www.codechef.com to post your questions!

×

Help with my Chef and Mover code?

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);
                }
}

asked 18 Aug '17, 15:39

shubham0812's gravatar image

1★shubham0812
9218
accept rate: 10%

edited 18 Aug '17, 19:46


I think you misunderstood the question and over complicated it. Check out the editorial first, if that doesnt help, comment here.

link

answered 18 Aug '17, 15:42

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

1

oh haha Did I? xD okay I'll check editorial it was my first challenge ever didn't know we had editorials too :)

(18 Aug '17, 15:44) shubham08121★

I didn't really understood the editorial, can somebody help me?

(18 Aug '17, 19:04) shubham08121★

Take this test case-

Input
1
5 1
1 1 1 1 6
Your Output
-1
Correct Output
10 (4+3+2+1)
link

answered 18 Aug '17, 19:51

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

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??

(18 Aug '17, 21:08) shubham08121★

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.

(18 Aug '17, 21:15) vijju123 ♦♦5★

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.

link

answered 18 Aug '17, 20:26

slugger's gravatar image

1★slugger
5414
accept rate: 25%

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);

                }
}
(18 Aug '17, 21:14) shubham08121★

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.

(18 Aug '17, 21:21) slugger1★

but then, if I would increase it directly, then how to keep track of no. of moves then?

(18 Aug '17, 22:09) shubham08121★

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"

(18 Aug '17, 22:10) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,491
×856
×427
×193

question asked: 18 Aug '17, 15:39

question was seen: 374 times

last updated: 18 Aug '17, 22:11