UVA Problem 10324 ( Zeros and Ones ) Solution

UVA Problem 10324 ( Zeros and Ones ) Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

Here I have provided naive solution for this problem which is very slow. This code can be solved much much faster. I’ll update to it later.

This One was painful. Got Runtime Error a few times before solving this. Still my best time for this so far is 1.899 sec. My main problem was that it said the problem could end with both an EOF or a new line character. The main problem was new line. So I used getchar() ( found it here one of the best sites for contest programming ) and checked for EOF and string length in the string input while condition.

The problem is quite descriptive. It says our string or character array size can be 1000000The string will contain only ‘0’ and ‘1’ characters. Basically we are to find if the characters between the given interval min(i,j)  and max(i,j)Meaning check for the characters from the minimum number between i or j to the maximum number of i or j.

Important:  Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Code Explanation:

Here the input format is first take a string or character array ( of size 1000000 ) and next take an integer which is the number if inputs to come. Now loop that many times and take two integers ( i and j ) every loop.

I used a flag named works which is set to 1 by default and use this to check condition if the characters match or not.

Now i loop thorough the given interval ( i and jto check if the character in the given interval are same.

In the loop i check every character of the interval string with the first character of that given interval. Since all character need to be same to output is this code is valid.

Now in the loop if any character doesn’t match I set the flag ( works ) to 0, print No since all characters don’t match and break from loop immediately. 

Next thing I check if flag is 1 then I print Yes.

Lastly the getchar()


Input:

0000011111
3
0 5
4 2
5 9
01010101010101010101010101111111111111111111111111111111111110000000000000000
5
4 4
25 60
1 3
62 76
24 62
1
1
0 0

Output:

Case 1:
No
Yes
Yes
Case 2:
Yes
Yes
No
Yes
No
Case 3:
Yes

Code Naive Solution ( Slow ):

/**
 * Author:  Quickgrid ( Asif Ahmed )
 * Site:    https://quickgrid.wordpress.com
 * Problem: UVA 10324 - Zeros and Ones
 */

#include<stdio.h>
#include<string.h>

#define N 1000000

static char s[N];


int main(){

    int i;
    int works, c = 1;
    int n, a, b;


    while(gets(s)){

        scanf("%d", &n);
        printf("Case %d:\n", c++);

        while( n-- ){

            works = 1;

            scanf("%d%d",&a,&b);

            if(a == b){
                printf("Yes\n");
                continue;
            }

            if(a > b){
                for(i = b; i <= a; ++i){
                    if(s[i] != s[a]){
                        works = 0;
                        printf("No\n");
                        break;
                    }
                }
            }else{
                for(i = a; i <= b; ++i){
                    if(s[i] != s[a]){
                        works = 0;
                        printf("No\n");
                        break;
                    }
                }
            }

            if(works)
                printf("Yes\n");

        }
        getchar();
    }
    return 0;
}
Advertisements