fork download
copy 
  1. #include <stdio.h>
  2. float arr2[5000][5000];//saves the min cost values of all the elements
  3. float arr3[5000][5000];
  4. float arr1[5000];//contains the func values
  5. int arr4[5000]; //used for final bucket elements
  6. float arr5[5000];//contais the elements that were first taken into consideration for buckets
  7. float arr6[5000]; //calculating final mean
  8. int arr7[5000];//to keep all the values of elements for all cases
  9. float arr8[5000];//to keep final mean bucketss
  10. int i,x,l;
  11. int t,n,k;
  12. float min=10000000000000;
  13.  
  14. float u();
  15. float v();
  16. int main()
  17. {
  18.   scanf("%d",&t);
  19.   int l;
  20.   int abcde;
  21.   int element_counter=0;
  22.   int mean_counter=0;
  23.   while(t>0 && t<=100) //run for every test case
  24.   {
  25.     float elements_sub[5000];
  26.     float elements_sq[5000];
  27.     float sum=0;
  28.     float mean=0;
  29.     float sq_sum=0;
  30.     float cost=0;
  31.     scanf("%d",&n);
  32.     scanf("%d",&k);
  33.    if(n>0 && n<=2500 && k>0 && k<=n)//checking for values of n and k
  34.   {
  35.     for(i=0;i<n;i++)
  36.     {
  37.       scanf("%f",&arr1[i]); //takes the functional values
  38.     }
  39.     int k_main=k;//finally putting values
  40.     int n_main=n;
  41.     {
  42.       for(i=0;i<n;i++) //calculation only for the first row
  43.       {
  44.         //printf("value of i : %d\n",i);
  45.         sum=0;
  46.         for(l=0;l<=i;l++)//to add the elements cost from arr1
  47.         {
  48.           sum= sum + arr1[l];
  49.           //printf("checking sum after %d element is added : %f \n",l,sum);
  50.         }
  51.         //printf("value of sum : %f\n",sum);
  52.         mean= sum/(i+1); //calc the mean
  53.         //printf("value of mean : %f\n",mean);
  54.         sq_sum=0;
  55.         for(l=0;l<=i;l++)
  56.         {
  57.           elements_sub[l]= arr1[l]-mean;
  58.           //printf("checking element sub after %d element is subtracted : %f \n",l,elements_sub[l]);
  59.           elements_sq[l]= elements_sub[l] * elements_sub[l];
  60.           //printf("checking element sq after %d element is squared : %f \n",l,elements_sq[l]);
  61.           sq_sum= sq_sum + elements_sq[l];
  62.           //printf("checking current sum after %d element is added : %f \n",l,sq_sum);
  63.         }
  64.         //printf("value of square sum : %f\n",sq_sum);
  65.         cost= sq_sum;//mean sq calculated
  66.         //printf("value of cost : %f\n",cost);
  67.         arr2[0][i]=cost;
  68.         //printf("%f\n",arr2[0][i]);
  69.       }
  70.     }
  71.     //need to calculate for subsequent rows - values of k
  72.    int y; //varies for k values- different buckets
  73.    for(y=1;y<k;y++)
  74.     {
  75.       for(i=0;i<n;i++)
  76.       {
  77.         for(x=0;x<=i;x++)
  78.         {
  79.           //printf("value of x : %d\n",x);
  80.           cost = u(y-1,x) + v(x+1,i); //only called the functions here
  81.           //printf("value of cost_mainf : %f\n",cost);
  82.           if(cost<min)
  83.           {
  84.             min=cost;
  85.             arr3[y][i]=x+2;
  86.           }
  87.           if(cost==0)
  88.           {
  89.             min=0;
  90.             arr3[y][i]=x+2;
  91.             break;
  92.           }
  93.         }
  94.         arr2[y][i]=min;
  95.         min=10000000000000;
  96.       }
  97.     }
  98.     //printing the min cost array
  99.     //printf("min cost values array\n");
  100.     /*for(i=0;i<k;i++)
  101.     {
  102.       for(l=0;l<n;l++)
  103.       {
  104.         printf("%f ",arr2[i][l]);
  105.         if(l== n-1)
  106.         {
  107.           printf("\n");
  108.         }
  109.       }
  110.     }*/
  111.     //printf("values of x+2 stored\n");
  112.     /*for(i=1;i<k;i++)
  113.     {
  114.       for(l=0;l<n;l++)
  115.       {
  116.         //printf("%f ",arr3[i][l]);
  117.         if(l== n-1)
  118.         {
  119.           //printf("\n");
  120.         }
  121.       }
  122.     }*/
  123.   //creating another array with final k bucket element Values
  124.   arr5[0]=arr3[k_main-1][n_main-1];
  125.   //printf("value of [k-2][n-1] is %f\n",arr5[0]);
  126.   int p;
  127.   int r;
  128.   p=arr5[0];
  129.   //printf("value of p is %d \n",p);
  130.   int q=1;
  131.   r=k-2;
  132.   //printf("value of r is %d\n",r);
  133.   while((k-2)>0)
  134.   {
  135.     //printf("Inside the loop %d\n",k-2);
  136.     arr5[q]=arr3[k_main-1-q][p-1];
  137.     //printf("value of p-1 is %d\n",p-1);
  138.     //printf("value of arr5[%d] is %f\n",q,arr5[q]);
  139.     p=arr5[q];
  140.     //printf("value of p is %d\n",p);
  141.     q++;
  142.     //printf("value of q is %d\n",q);
  143.     k--;
  144.     //printf("value of k is %d\n",k);
  145.   }
  146.   //printing bucket Values
  147.   int z;
  148.   //printf("final k bucket values\n");
  149.   arr5[k_main-1]=1;
  150.   int counter=0;
  151.   int bucket=arr5[k_main-1];
  152.   for(z=k_main-1;z>=0;z--)
  153.   {
  154.     if(z==k_main-1)
  155.     {
  156.     arr4[0]=(int)arr5[z];
  157.     //printf("%d\n",arr4[0]);
  158.     counter++;
  159.     }
  160.     else
  161.     {
  162.       if(bucket!=arr5[z])
  163.       {
  164.         bucket=arr5[z];
  165.         arr4[counter]=(int)arr5[z];
  166.         //printf("%d\n",arr4[counter]);
  167.         counter++;
  168.       }
  169.     }
  170.   }
  171.   //calculating final means
  172.   //printf("calculating final element means-step fucn\n");
  173.   int elem1,elem2;
  174.   for(i=0;i<counter;i++)
  175.   {
  176.   //  printf("value of i is %d\n",i);
  177.     sum=0;
  178.     elem1=arr4[i]-1;
  179.     //printf("value of elem1 is %d\n",elem1);
  180.     if((i+1)==counter)
  181.     {
  182.       elem2=n_main;
  183.     }
  184.     else
  185.       elem2=arr4[i+1]-1;
  186.     //printf("value of elem2 is %d\n",elem2);
  187.     for(l=elem1;l<elem2;l++)
  188.     {
  189.       sum= sum + arr1[l];
  190.     }
  191.     arr6[i]=sum/(elem2-elem1);
  192.     //printf("value of arr6[%d] is %f\n",i,arr6[i]);
  193.   }
  194.   //printf("printing bucket elements\n");
  195.   //printf("%d %f\n",counter,arr2[k_main-1][n_main-1]);
  196.   arr7[element_counter]=counter;
  197.   arr8[element_counter]=arr2[k_main-1][n_main-1];
  198.   element_counter++;
  199.   for(x=0;x<counter;x++)
  200.     {
  201.       //printf("%d %f\n",arr4[x],arr6[x]);
  202.       arr7[element_counter]=arr4[x];
  203.       arr8[element_counter]=arr6[x];
  204.       element_counter++;
  205.     }
  206.  
  207.     for(i=0;i<n;i++)
  208.     {
  209.       arr4[i]=0;
  210.       arr5[i]=0;
  211.       arr6[i]=0;
  212.     }
  213.     for(i=0;i<k;i++)
  214.     {
  215.       for(l=0;l<n;l++)
  216.       {
  217.        arr2[i][l]=0;
  218.        arr3[i][l]=0;
  219.      }
  220.     }
  221.     counter=0;
  222.     sum=0;
  223.   }
  224.   /*else
  225.       printf("Values don't fall under the boundaries");*/
  226.     t--;
  227.   }//end of while loop
  228.  
  229.   for(x=0;x<element_counter;x++)
  230.   {
  231.    printf("%d %f\n",arr7[x],arr8[x]);
  232.  }
  233. }
  234.  
  235. float u(a,b)
  236. {
  237.   //printf("array value is : %f \n", arr2[a][b]);
  238.   return arr2[a][b];
  239. }
  240.  
  241. float v(p,q)
  242. {
  243.   float sum=0;
  244.   float sq_sum=0;
  245.   int count=0;
  246.   float mean=0;
  247.   float elements_sub[5000];
  248.   float elements_sq[5000];
  249.   float cost=0;
  250.   int z;
  251.   //printf("value of p : %d\n",p);
  252.   //printf("value of q : %d\n",q);
  253.   if(p>=q)
  254.     return 0;
  255.   else
  256.     {
  257.       for(z=p;z<=q;z++)
  258.       {
  259.         sum=arr1[z] + sum;
  260.         count++;
  261.       }
  262.       //printf("value of sum_v : %f\n",sum);
  263.       mean= sum/count;
  264.       //printf("value of mean_v : %f\n",mean);
  265.       for(z=p;z<=q;z++)
  266.       {
  267.         elements_sub[z]=arr1[z]-mean;
  268.         elements_sq[z]= elements_sub[z] * elements_sub[z];
  269.         sq_sum= sq_sum + elements_sq[z];
  270.       }
  271.       cost= sq_sum;
  272.       //printf("value of cost_v : %f\n",cost);
  273.     }
  274.     return cost;
  275. }
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
1
3 3
3 3 3
stdout
copy 
2 0.000000
1 3.000000
2 3.000000
https://ideone.com/UFlrda
language:
C (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!