STICKS - Cannot determine what went wrong

general
, ,
1

I am solving a problem called Sticks in C. Here is the link https://www.codechef.com/problems/STICKS
. I am unable to determine what went wrong. I even included the SQUARE TEST CASE. Here is my code, Any help would be appreciated:

#include<stdio.h>
#include<math.h>
// using quicksort to sort the elements
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);

for(int j = low; j <= high -1; j++)
{
    if(arr[j] <= pivot)
    {
        i++;
        swap(&arr[i], &arr[j]);
    }
}
swap(&arr[i+1], &arr[high]);
return (i+1);
}

void quicksort(int arr[], int low, int high)
{
if(low < high)
{
    int pi = partition(arr, low, high);

    quicksort(arr, low, pi -1);
    quicksort(arr, pi + 1, high);
}
}

int main()
{   
int test_case, j;
scanf("%d", &test_case);
for(j = 1; j<=test_case; j++)
{

int arr[1000], duparr[1000], n=0, i=0, max1 = 0, max2 = 0, count = 0; // duparr is duplicate array used for storing duplicate values

scanf("%d", &n);

for(i = 0; i < 1000; i++)
{ arr[i] = 0; duparr[i] = 0; }

for(i = 0; i < n; i++)
  {  scanf(" %d", &arr[i]); }

quicksort(arr, 0, n-1);

// to check how many duplicate values are 
there

for(i=n-1;i>=0;i--)
{   
    if(i == 0)
    { ; }        
    else if(arr[i]==arr[i-1])
    { count++; duparr[i] = arr[i]; }
}
// for storing the two max values
for(i=n-1;i>=0;i--)
{   
    if(i == 0)
    { ; }

    else if(duparr[i]!=duparr[i-1] && duparr[i] > max1 && (count >= 2))
    {
        max1 = duparr[i];
    }
    else if(duparr[i]!=duparr[i-1] && duparr[i] < max1 && duparr[i] > max2 && (count >= 2))
    {
        max2 = arr[i];
    }
}

int product = 0, product2 = 0, final_product = 0; 
product = max1*max2; 
product2 = sqrt(product); // to check for a square
final_product = (product2 % 2);
      
if(count < 2 || product2 == 0)
printf("-1\n");

else if(count >= 2)
printf("%d\n", (product));
}
return 0;
}
2

There-

Input
1
5
6 6 6 6 2
Your Output
-1
Expected Output
36

A very elegant approach is to make a frequency array and count how many times each element occurs. Then iterate through 1000 to 1, and see which element occured 2 (or 4 times- corner case!) and include it in the rectangle.

3

While reading the editorial someone said to ignore square case as in the problem only rectangle’s area is asked. So I specifically found the square root of the final anewer to check for the square condition. So when you did 6 6 6 6 2 , the answer should be -1 as it is a square not rectangle. Any input to this logic would really help me!

4

No, thats wrong. Setter’s solution itself gives 36 (I verified). Take it as “Square is a rectangle with equal length and breadth” .

5

I will try this out. Thanks!

6

I added the case and compiled, it matches all of the setter’s solution but i am still getting WA. https://www.codechef.com/viewsolution/15641945

7

This TC fails-

1
3
2 2 2

Your code prints 4 for this.