UVa 10055: Hashmat the brave warrior

UVa 10055: Hashmat the brave warrior

Written by on 5 July 2012

Topics: UVa Online Judge

In problem 10055 at the UVa online judge, we are asked to help Hashmat the brave warrior to decide whether he should fight against his opponents. We do that by calculating the difference between the number of Hashmat’s soldiers and the number of his opponent’s soldiers.

Interpretation

Hashmat tells us the number of soldiers in his army, and the number of soldiers in the opponent’s army. We don’t know in what order they are given, but we do know that Hashmat’s soldier number is never greater than his opponent’s soldier number. We need to calculate the difference between his soldier number and his opponent’s soldier number. We also know that neither soldier number is greater than , but that is a big number, so we’re going to store them in a long integer to be on the safe side. Using a normal 32-bit integer could cause overflow problems and lead to an incorrect solution.

Implementation

We’re going to read each pair of numbers. We need to figure out which number is Hashmat’s army, and which number is his opponent’s army. That can easily be done since we know that Hasmat’s army is always the smaller number. Then we print out the difference between the numbers, which is the opponent’s number minus Hasmat’s number.

Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out, true);

while (in.hasNextLong()) {
	long a = in.nextLong(),
		 b = in.nextLong();

 	long hashmat, opposite;

 	if (a <= b) {
 		hashmat = a;
 		opposite = b;
 	} else {
 		hashmat = b;
 		opposite = a;
 	}

 	out.println(opposite - hashmat);
}

This is actually a lot of code for such a simple problem. Let’s try to make it more compact.

We can note that the difference is always positive, since Hashmat’s soldier number is never greater than his opponent’s soldier number. If we calculate Hashmat’s number minus the opponent’s number, instead of the opposite, then we will get the negative of the difference we’re after. So in either case the absolute value (the number without the sign) of , where is either Hashmat’s or his opponent’s soldier number and is the opposite, will be the difference we’re after.

The code in the while-loop can now be written as follows.

long a = in.nextLong(),
	 b = in.nextLong();

out.println(Math.abs(a - b));

Conclusion

With only a couple of lines of code we helped keep Hashmat, the brave warrior, and his soldiers alive. The problem was not a hard one, but many people have had issues with overflow, as well as misinterpreting the problem description.

The complete source code is located here. Leave a comment if you have any questions, or if you want to tell us how you solved the problem.

15 Comments For This Post I'd Love to Hear Yours!

  1. Eman says:

    Why are you solving such an easy problems? :) You should solve more PE instead.

  2. Bjarki Ágúst says:

    Kristian handles the Project Euler problems, while I write about UVa problems. You need to talk to him if you want more PE :)
    But the first reason for doing such an easy problem is that I’ve started going through the “Next Problems to Solve” list on uHunt. It is loosely sorted by increasing difficulty, so the first problems are easy. But they’ll get hard soon enough.
    The second reason for doing an easy problem is that everybody needs to start with the basics. A newcomer can start by reading these easier posts before advancing to the more harder posts/problems.
    If you have a good reason for me not writing about these easier problems, then please let me know. Otherwise I will keep on going, and over time get to the harder problems.

  3. Kristian says:

    What is easy for some might not be it for others. I tend to agree with you that this is an easy problem.

    The typical reader of these problems will be people who are new to UVa. They are not searching for a solution strategy since that is fairly straight forward, but for some reason they are stuck on a problem related to the input formatting or the like.

    Besides that it apparently helps to get people like you involved in the discussion. A side bonus I didn’t see comming.

    /Kristian

  4. Eman says:

    ok, so I’ll do Uva also, as a training in C

  5. Bjarki Ágúst says:

    That’s a great idea! Take a look at the UVa introduction if you need help with the UVa judge. You can also take a look at our UVa solutions.

  6. Eman says:

    No need to introduce me to Uva :) I am registrated there, but i didn’t know about uHund. From my previous post I’ve already solved 3 Uva problems. Good luck :)

  7. raj says:

    #include
    int main()
    {
    long long int x,a,b;
    while(scanf(“%lld %lld”,&a,&b)==2)
    {
    if(a>b)
    x=a-b;
    else
    x=b-a;
    printf(“%lld\n”,x);
    }
    return 0;
    }

  8. afrida says:

    why while(scanf(“%lld%lld”,&a,&b)==2) is used in hashmat solution?

  9. Bjarki Ágúst says:

    afrida: The scanf function returns the number of items that it was able to read. So when it reads two integers, it returns 2. But when there are no more integers to be read, it won’t return 2 (instead, it will return EOF). So this line in raj’s solution is basically reading in each test case, one after another, until there are no more test cases.

  10. hoimonty says:

    how to reduce run time in this problem. with this answer it takes 0.064s.

  11. Bjarki Ágúst says:

    hoimonty: The fastest I can get it down to is 0.040s with the following C code:

    #include <stdio.h>
    #include <math.h>
    
    char readn( register unsigned long long *n )
    {
    	char any = 0;
        register int t;
        register char c;
        *n = 0;
        while( ( t = getc_unlocked( stdin ) ) != EOF )
        {
        	any = 1;
        	c = (char)t;
            switch( c )
            {
                case ' ': goto hell;
                case '\n': goto hell;
                default: (*n) *= 10; (*n) += ( c - '0' ); break;
            }
        }
    hell:
    	return any;
    }
    
    int main()
    {
    	while (1)
    	{
    		unsigned long long a, b;
    		if (!readn(&a)) break;
    		readn(&b);
    
    		if (a < b) printf("%lld\n", b - a);
    		else printf("%lld\n", a - b);
    	}
    
    	return 0;
    }

    The readn function is a modified version of the readn function found here.
    In this problem, the bottleneck is reading the input, since apart from that you are almost not doing anything. So if you want a faster solution, you need to optimize the input reading (and possibly also the output writing).

  12. Bjarki Ágúst says:

    Oh wow, I just noticed that there are 25635 users that have solved the problem, and 0.040s puts me in 31th place. It probably wont get much better than that…

  13. Bjarki Ágúst says:

    In case anyone is interested, I got the running time down to 0.032s (which puts me in 23rd place) by optimizing the output. Now I convert the integers to a string myself, and also store all output in a buffer which I output only once at the end with fwrite. I also tried reading all the input at once into a buffer, but that was slower for whatever reason.

    #include <stdio.h>
    #include <math.h>
    
    char readn( register unsigned long long *n )
    {
    	char any = 0;
        register int t;
        register char c;
        *n = 0;
        while( ( t = getc_unlocked( stdin ) ) != EOF )
        {
        	any = 1;
        	c = (char)t;
            switch( c )
            {
                case ' ': goto hell;
                case '\n': goto hell;
                default: (*n) *= 10; (*n) += ( c - '0' ); break;
            }
        }
    hell:
    	return any;
    }
    
    char buff[10];
    char outbuf[5000000];
    int outat = 0;
    
    void writen(unsigned long long n)
    {
    	if (n == 0)
    	{
    		outbuf[outat++] = '0';
    	}
    	else
    	{
    		int at = 0;
    		while (n)
    		{
    			buff[at++] = (n % 10) + '0';
    			n /= 10;
    		}
    
    		while (at > 0)
    		{
    			outbuf[outat++] = buff[--at];
    		}
    	}
    
    	outbuf[outat++] = '\n';
    }
    
    int main()
    {
    	while (1)
    	{
    		unsigned long long a, b;
    		if (!readn(&a)) break;
    		readn(&b);
    
    		if (a < b) writen(b - a);
    		else writen(a - b);
    	}
    
    	fwrite(outbuf, sizeof(char), outat, stdout);
    
    	return 0;
    }
    

    Usually I’m more for the high-level optimization, but in this instance I found it was quite fun to get down and dirty and do some low-level optimization.

  14. Hoimonty says:

    Thanx 2 Bjarki Ágúst.
    It will help me 2 know more.

  15. shohan says:

    why take long long int i knew that int size is 32 bit so pow(2,32) is fits to the int

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.