CodeChef October Challenge 2013 Editorial [Little Elephant and Bamboo]

Problem: Little Elephant and Bamboo

You are given N bamboo of different height H_i. this is the current height of the bamboos. Next you will be given N bamboo of required height D_i. 

A single operation means decreasing height of a bamboo by 1 and increasing all others by 1. your task to minimize the operation to make all current height to required height. If it's impossible, print -1.

Solution Idea: Brute Force.
first of all, make another array, diff[] to calculate differences of required and current array.

diff[i]=d[i]-h[i];

now operation reversed, an operation means increasing height of a bamboo by 1, and decreasing all other by 1. your target is to make all diff[] to 0.
note that, you are increasing only one height and decreasing all other. so after each operation summation of diff[] array will decrease.
so, if somehow summation of diff array goes to negative there is no solution exists.
what element you will increase to balance? simple, the minimum one. make a function for an operation. if sum of diff[] become to 0 you have to check whether all diff[] are 0 or not. if all are 0 the number of operation you made is the answer.

Note: Special check for N=1 & N=2.

Code:

1. #include<bits/stdc++.h>
2. using namespace std;
3.  
4. #define SET(a) memset(a,-1,sizeof(a))
5. #define CLR(a) memset(a,0,sizeof(a))
6. #define PI acos(-1.0)
7. #define MOD 1000000007
8. #define MX 100010
9. 
   
10. int diff[55], n;
11. void mov(int idx)
12. {
13. for(int i=0; i<n; i++)
14. if(i==idx) diff[i]++;
15. else diff[i]--;
16. return;
17. }
18.  
19. bool allZero()
20. {
21. for(int i=0; i<n; i++)
22. if(diff[i]!=0) return false;
23. return true;
24. }
25.  
26. int main()
27. {
28. int tc,kk=1, h[55], d[55], cnt;
29. cin>>tc;
30. while(tc--)
31. {
32. cin>>n;
33. for(int i=0; i<n; i++) cin>>h[i];
34. for(int i=0; i<n; i++) cin>>d[i];
35. for(int i=0; i<n; i++) diff[i]=d[i]-h[i];
36. cnt=0;
37. bool chk=false;
38. if(n==1)
39. {
40. if(diff[0]>0) cout<<-1<<endl;
41. else cout<<abs(diff[0])<<endl;
42. }
43. else if(n==2)
44. {
45. if(diff[0]+diff[1]==0) cout<<abs(diff[0])<<endl;
46. else cout<<-1<<endl;
47. }
48. else
49. {
50. while(1)
51. {
52. int sum=0, mn=1e9, idx;
53. for(int i=0; i<n; i++)
54. {
55. sum+=diff[i];
56. if(diff[i]<mn)
57. {
58. mn=diff[i];
59. idx=i;
60. }
61. }
62. if(sum<0)
63. {
64. chk=true;
65. break;
66. }
67. if(sum==0)
68. {
69. if(allZero())
70. break;
71. }
72. cnt++;
73. mov(idx);
74. }
75. if(chk) cout<<-1<<endl;
76. else cout<<cnt<<endl;
77. }
78. }
79. return 0;
80. }