3
\$\begingroup\$

How can I improve it and its running time efficiency?

Problem (SPOJ/CANDY)

Jennifer is a teacher in the first year of a primary school. She has gone for a trip with her class today. She has taken a packet of candies for each child. Unfortunately, the sizes of the packets are not the same.

Jennifer is afraid that each child will want to have the biggest packet of candies and this will lead to quarrels or even fights among children. She wants to avoid this. Therefore, she has decided to open all the packets, count the candies in each packet and move some candies from bigger packets to smaller ones so that each packet will contain the same number of candies. The question is how many candies she has to move.

Input specification

The input file consists of several blocks of data. Each block starts with the number of candy packets \$N (1 <= N <= 10000)\$ followed by \$N\$ integers (each less than 1000) in separate lines, giving the number of candies in each packet. After the last block of data there is the number -1.

Output specification

The output file should contain one line with the smallest number of moves for each block of data. One move consists of taking one candy from a packet and putting it into another one. If it is not possible to have the same number of candies in each packet, output the number -1.

Solution

 //candy.cpp
#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

int main()
{
string n;
int avg,t,k; // t = test cases , avg = average
while(true)
{
    scanf("%d",&t);
    int sum = 0; // initialise sum and cnt(next line) to 0 
    int cnt = 0;
    if(t == -1) // Last line to end the program(Mentioned in the ques.)
        break;

    else
    {
        for(int i = 0 ; i < t ; i++)
        {
            cin >> n[i];
            sum += n[i];
        }

        if(sum % t != 0) // If it is not possible to have the same number of candies in each packet, output the number -1(mentioned in the question)
            cout << "-1" << endl;   

        else
        {
            avg = sum/t;
            for(int i = 0 ; i < t ; i++)
            {
                k = n[i];               
                while(k > avg) //Adds the moves 
                {
                    k-- ;
                    cnt++ ;
                }
            }   
            printf("%d\n", cnt);
        }
    }

}

}
\$\endgroup\$
3
\$\begingroup\$

This is really silly:

while(k > avg) //Adds the moves 
{
    k-- ;
    cnt++ ;
}

When you can do the same thing in one step:

if (k > avg) cnt += k - avg;

I don't see anything else to make this faster. But there are many many coding style issues.

Limit the scope of variables

Instead of declaring all the variables at the top, it's better to declare them in the smallest scope, for example:

int avg = sum/t;
for(int i = 0 ; i < t ; i++)
{
    int k = n[i];               
    if (k > avg) cnt += k - avg;
}   

Use the right types

Why do you read the numbers into a string? The program won't work if a pocket contains more than 9 candies, which it might, since the requirement states "less than 1000". Use an int[] instead.

Misc

  • You should not using namespace std
  • You're mixing C++ style input/output using cin/cout and old-style scanf/printf. Since you're in C++, you should use C++ everywhere consistently
  • It's recommended to use braces even with single-statement ifs and loops
  • After the break statement, you can simplify a bit by eliminating the else block

Corrected and improved implementation

With the above suggestions, the implementation becomes:

#include <iostream>
#include <stdio.h>

int main()
{
    while(true)
    {
        int t;
        std::cin >> t;
        if (t == -1) {
            break;
        }

        int sum = 0;
        int n[t];
        for(int i = 0 ; i < t ; i++)
        {
            std::cin >> n[i];
            sum += n[i];
        }

        if (sum % t != 0) {
            std::cout << "-1" << std::endl;   
            continue;
        }

        int avg = sum/t;
        int cnt = 0;
        for(int i = 0 ; i < t ; i++)
        {
            int k = n[i];               
            if (k > avg) cnt += k - avg;
        }   
        std::cout << cnt << std::endl;
    }
}

Take special note as to how each variable is declared and initialized right before it's really needed.

\$\endgroup\$
  • \$\begingroup\$ In competitive programming time really matters and trust me scanf , print is faster than cin , cout so yeah I use scanf and printf in some cases. \$\endgroup\$ – Himagra Chawla Jan 17 '15 at 14:48
  • \$\begingroup\$ In the many contests I've participated, I've never seen that scanf vs cin would make a decisive difference. In time limit exceeded situations it's always the algorithm that was inefficient. That doesn't mean there cannot be exceptions, if you say it's a necessary micro-optimization for this contest, then I'll "trust you". But my recommendation as good C++ programming style still stands. Feel free to modify it for your contest submission. \$\endgroup\$ – Stop ongoing harm to Monica Jan 17 '15 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.