UVA Problem 11192 ( Group Reverse ) Solution

UVA Problem 11192 ( Group Reverse ) Solution:


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

Solving Technique:

This one is a bit tricky. Also it seems to be closely related to this ( 483 word scramble ) uva problem. Basically for this problem we are to take an integer ( which is the number of groups ) and a string until we are given a 0. Now our input is given like this,

3 ABCEHSHSH

5 FA0ETASINAHGRI0NATWON0QA0NARI0

0

So, the first problem for beginner is taking input for this. From the input we can easily see that there are two parts and the first part is an integer and second part is a string. Also we need to keep taking input until we find 0. What if we divide our scanf or input taking into two parts. First take the integer and check if its 0 or not then if it’s not zero then take the string and continue like this.

Our first input is an integer which is group number or number of parts the string can be divided to. So, from the given problem statement,

TOBENUMBERONEWEMEETAGAINANDAGAINUNDERBLUEICPCSKY

This string has length 48. We have divided into 8 groups of equal length and so the length of each group is 6. Meaning each group or each part of sentence will consist of 6 characters.

UNEBOTNOREBMEEMEWENIAGATAGADNAEDNUNIIEULBRYKSCPC

Our task is to reverse print/output each and every group. We can easily find how many members are in each group by dividing the length of the string with input ( number of groups ) we are given.

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 I have used stack data structure ( see this and this ) to solve this problem. First I find the length of the string then find how many characters in each group by dividing string length with group number. I also keep a counter ” x “ and keep pushing each character of the string in stack until I reach the last character or until our counter is not equal to the group member count. Also increment the counter each time i push into the stack. Also I keep a condition to check if  I have reach the last character or until our counter is equal to the group member count then pop until our loop counter has reached zero. Since stack is a LIFO data structures the last character i pushed into the stack are the first one to come out ( meaning they are outputted in reverse order ). This process keeps running until we reach the end of the sentence.


Input:

3 ABCEHSHSH
5 FA0ETASINAHGRI0NATWON0QA0NARI0
0

Output:

CBASHEHSH
ATE0AFGHANISTAN0IRAQ0NOW0IRAN0

Commented Code ( See the next Code for easier understanding of stack ):

/**
 * @author Quickgrid ( Asif Ahmed )
 * @url https://quickgrid.wordpress.com
 */

#include<stdio.h>

/**
 * Input string buffer
 */
static char s[128];

/**
 * Global index for accessing input array, may be declared inside main
 */
int top = -1;

int main(){
    register unsigned j,u,n,i,x;

    /**
     * Input group count and Check if count is Not Zero
     */
    while (scanf("%u", &n) && n) {
        scanf("%s", s);

        /**
         * Find out input string size
         */
        for (j = 0; s[j]; ++j);

        /**
         * Find out length of each group
         */
        n = j / n;

        /**
         * Group Reverse loop
         */
        for (x = i = 0; i < j; ++i) {
            /**
             * For checking is the item after is NUL terminator
             */
            u = s[i + 1];

            /**
             * @var u
             * If the character after current is NUL then NOT u, is True
             *
             * @var n
             * Check to see if characters in group count is NOT full, then push more to stack
             */
            if ( !u || x != n ) {
                /**
                 * Push current character on top of stack
                 */
                s[++top] = s[i];
                /**
                 * Keep a count of characters pushed on stack
                 */
                ++x;
            }

            /**
             * If character limit per group is reached then Condition is True
             */
            if ( !u || x == n ) {
                /**
                 * Empty the the stack for every pushed character
                 */
                while (x--){
                    /**
                     * Output character by character in reversed form
                     */
                    printf("%c", s[top]);
                    --top;
                }
                x = 0;
            }

        }
        printf("\n");
    }
    return 0;
}

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */

#include<stdio.h>

char s[101];
int top = -1;

void push(char c){
    if(top + 1 >= 101)
        return;

    s[++top] = c;
}

void pop(){
    if (top == -1)
        return;

    printf("%c", s[top]);
    s[top--] = '\0';
}

int main(){
	int n,j,i,x;
	while (scanf("%d", &n) == 1 && n != 0){
        x = 0;
        scanf("%s", &s);
        for (i = 0; s[i]; ++i);
        n = i / n;

        for (i = 0; s[i]; ++i){
            if (s[i+1] == '\0' || x != n){
                push(s[i]);
                ++x;
            }

            if (s[i+1] == '\0' || x == n){
                while (x--)
                    pop();

                x = 0;
            }
        }

        printf("\n");
	}
	return 0;
}

One thought on “UVA Problem 11192 ( Group Reverse ) Solution

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s