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;
}
Advertisements

UVA Problem 11172 ( Relation Operator ) Solution

UVA Problem 11172 ( Relation Operator ) Solution:


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

Some off topic ideas:

Aimed at absolute beginners. This is an ad hoc problem and one of the problems easiest on uva online judge. I don’t know if it’s a good practice but first the first thing I do when given a problem I look at the inputs and outputs. After solving some problems how inputs for some problems are given we can see a pattern. Among them some problems run until they find EOF, some run until they find a given input and some take an input first for the number of input sets to come.

Solving Technique:

First if we just look at the input and output even without looking at the problem set we can see it takes the number 3 and followed by 3 lines of input. So from this we can identify the first line of input will take the number of inputs to come and the next line will iterate that many times.

Now if we look at the input style given for the problem it says the first input will less than 15 so we can safely use an integer to store this variable. For example we call this stored variable t.

Now the next lines of inputs will be given t times. And there are two integers per input. For example, we denote the first one a and the second one b. Both will be ranged within 1000000001 and this number safely fits in 4 byte integer so we can use an int data type to store this variables.

Finally, the problem’s statement asks us to find the comparison relations between two given inputs. Check to see if the

First one is greater than the second. In this case output ” > ” without the quotes.

or,

First one is less than the second. In this case output ” < ” without the quotes.

or,

First and second one is equal. In this case output ” = ” without the quotes

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:

Just like other problems there are many better ways and faster to solve this. Here I scan the first line of input. Now I use a while loop. In the condition for while loop I used i – – this basically subtracts 1 from i for each completed loop. This way after some loops value of i will be. So the condition of while loop will be while(0) and it means false and the loop will exit.

Now for each loop I input two numbers. Next thing I use ternary operator to compare and put this as the output parameter of print. So the value that will be true according to conditions will get printed.


Input:

3
10 20
20 10
10 10

Output:

<
>
=

C Code:

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

#include<stdio.h>

int main(){
    register unsigned i;
    unsigned a, b;

    scanf("%u", &i);
    while (i--){
        scanf("%u%u", &a, &b);
        printf("%c\n", a > b ? '>' : a < b ? '<' : '=');
    }

    return 0;
}

 

In C++:

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

#include<iostream>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    register unsigned i;
    unsigned a,b;

    std::cin >> i;
    while(i--){
        std::cin >> a >> b;
        std::cout << (a > b ? '>' : a < b ? '<' : '=') << "\n";
    }

    return 0;
}

UVA Problem 12468 ( Zapping ) Solution

UVA Problem 12468 ( Zapping ) Solution:


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

Solving Technique:

Another easy problem. The problem mainly deals with changing channel in tv using only up and down button. So there are only 2 directions. We are to find the least key press from given channel (Input 1) to Channel (Input 2) in any direction up or down. The output should be the least number of key pressed to move from given channel to another given channel.

The program will keep running until it find two -1. It will mark the end of input. There will be two input per line. Both inputs will be a channel ranging within 0 to and including 99 ( 0<= a,b <=99 ).First we can easily see from 0 to 99 there are 100 channels. So the most key press either using up or down button will be 50. It is always same for this range.

For example, If input is:

10 90

here if we press the up button on remote it will take 80 press to reach but if we keep pressing down key it will only take 20 press. Why? because it is mentioned in the problem that we can reach to 0 from channel 99 also the inverse is true we can reach 99 from channel 0. So our answer should be 20 because the problems wants the least number of key presses.

Important: 

The most key press in any direction is 50 for range 0 to 99 ( try to think ).

Solving Technique:

We can easily find the distance ( or number of key press ) between two channels by subtracting one from another. Here I have used abs() absolute function so even if subtract the larger number from the smaller I’ll always get a positive value. Now i check if the subtraction result is smaller than 50 then it is the least number of key press in any direction. But if its greater than 50 then we are going the wrong direction. We subtract the result from the total number of channels ( here total 100 ) to find the least number of key presses in the opposite direction.


Input:

3 9
0 99
12 27
-1 -1

Output:

6
1
15

Code:

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

#include<stdio.h>
#include<stdlib.h>

int main(){
    int a, b, i, s;
    while (scanf("%d%d", &a, &b) == 2 && (a != -1 && b != -1)){
        s = abs(a - b);

        if(s > 50)
            s = 100 - s;

        printf("%d\n", s);
    }
    return 0;
}

BFS Sequence for Unirected Graph in C++

Code Explanation:

Coming soon maybe…… Until then please look at the commented code.

Example Graph:

Example Undirected Graph for applying BFS
Example Undirected Graph for applying BFS

Code:

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

#include<stdio.h>

#define size 100

/**
 * Here nodes are represented with characters
 */
char vertex[size], visited_sequence[size], q[size];

/**
 * The graph which is a 2D matrix
 */
int graph[size][size];

/**
 * Counters for visited sequence, queue etc
 */
int count_visited_seq = 0, f = 0, r = 0, n;


/**
 * Update the visited sequence array
 */
void visit(char v)
{
    visited_sequence[count_visited_seq++] = v;
}


/**
 * Check the visited sequence array against a node
 * to see if it is already visited
 */
int isVisited(char v)
{
    for(int i = 0; i != count_visited_seq; ++i)
    {
        if(visited_sequence[i] == v)
        {
            return 1; // means already visited
        }
    }
    return 0; // not visited
}


/**
 * Display the BFS visited sequence
 */
void displayVisitedSequence()
{
    for(int i = 0; i < count_visited_seq; ++i)
    {
        printf("%c ", visited_sequence[i]);
    }
    printf("\n");
}


void enqueue(char v)
{
    int s = (r + 1) % (size + 1);
    if(s == f)
    {
        return;
    }
    q[s] = v;
    r = s;
}


char dequeue()
{
    if(f == r)
    {
        return '\0';
    }
    f = (f + 1) % (size + 1);
    char v = q[f];
    q[f] = '\0';
    return v;
}


/**
 * Check the adjacent nodes of given node to see if there is an edge
 * Also check if it is not already visited then enter it to queue
 */
void checkAdjecency(char v)
{
    for(int i = 0; i != n; ++i)
    {
        if(vertex[i] == v)
        {
            for(int j = 0; j != n; ++j)
            {
                if(graph[i][j] == 1 && !isVisited(vertex[j]))
                {
                    enqueue(vertex[j]);
                }
            }
        }
    }
}


/**
 * Create undirected graph, map characters as nodes identifiers
 * Reset the graph meaning set 0, to point out no edge exist
 */
void createGraph()
{
    int i, j;
    for(i = 0; i < 26; ++i)
    {
        vertex[i] = i + 'A';
    }

    printf("How many vertex:\n");
    scanf("%d", &n);
    for(i = 0; i != n; ++i)
    {
        for(j = 0; j != n; ++j)
        {
            graph[i][j] = 0;
        }
    }

    for(i = 0; i != n; ++i)
    {
        for(j = i + 1; j != n; ++j)
        {
            printf("%c-%c exist:\n", vertex[i], vertex[j]);
            scanf("%d", &graph[i][j]);
            if(graph[i][j] == 1)
            {
                graph[j][i] = graph[i][j];
            }
        }
    }
}


/**
 * Start processing the queue
 */
void BFS()
{
    char v;
    int exit = 0;
    while(1)
    {
        fflush(stdout);
        printf("Enter a node to Enqueue:\n");
        fflush(stdin);
        scanf("%c", &v);
        for(int i = 0; i != n; ++i)
        {
            if(vertex[i] == v)
            {
                enqueue(vertex[i]);
                exit = 1;
            }
        }
        if(exit)
        {
            break;
        }
    }

    while(f != r)
    {
        char v = dequeue();
        if(!isVisited(v))
        {
            visit(v);
        }
        checkAdjecency(v);
    }
}


int main()
{
    createGraph();
    BFS();
    displayVisitedSequence();
    return 0;
}

Stack Queue Array Hybrid (Data Structure)

Description: Here i combined my knowledge of stack and queue array into a single code. Firstly we are working with Queue. We can enqueue items in a queue. But when we dequeue the dequeued item is pushed to the stack ( We push the dequeued item in stack ) . The items pushed in stack are in the same order as they were in queue  since Queue is FIFO ( First In First Out ) data structure. We can also pop items from that stack. Now when we pop them they are enqueued back to the queue. The interesting thing is when they are popped they fill up the queue in reverse order since Stack is LIFO ( Last In First Out ) data structure.


input system
stack queue data structure 1
input system
stack queue data structure 2

Stack Functions: pop(), push(), displayStack(), searchStack()

Queue Functions: enqueue(), dequeue(), displayQueue(), searchQueue()


Code:

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

#include<stdio.h>

#define size 100

int q[size+1], f = 0, r = 0;
int s[size], top = -1;

void showMenu()
{
    printf("1.Enqueue\n");
    printf("2.Dequeue\n");
    printf("3.Show Queue\n");
    printf("4.Search Queue\n");
    printf("5.Show Stack\n");
    printf("6.Search Stack\n");
    printf("7.Pop stack\n");
    printf("8.Exit\n");
}

void push(int item)
{
    if(top+1 >= size)
    {
        printf("stack Overflow.\n");
        return;
    }
    s[++top] = item;
}

void displayQueue()
{
    int i = (f+1) % (size+1);
    for(int j=i; j!=r+1; ++j)
    {
        if(j>size)
        {
            j = 0;
        }
        if(f != r)
        {
            printf("%d ", q[j]);
        }
    }
    printf("\n");
}

void enqueue(int num)
{
    int s = (r+1) % (size+1);
    if(s == f)
    {
        printf("Queue Full.\n");
        return;
    }
    q[s] = num;
    r = s;
}

void dequeue()
{
    if(f == r)
    {
        printf("Queue empty.\n");
        return;
    }
    f = (f+1) % (size+1);
    printf("%d\n", q[f]);
    push(q[f]);
    q[f] = 0;
}

void searchQueue(int item)
{
    int i = (f+1) % (size+1);
    for(int j=i; j!=r+1; ++j)
    {
        if(j > size)
        {
            j = 0;
        }
        if(f!=r)
        {
            if(q[j] == item)
            {
                printf("%d found in queue\n", item);
            }
        }
    }
}

void searchStack(int item)
{
    for(int i=0; i<=top; ++i)
    {
        if(s[i] == item)
        {
            printf("%d found at index: %d\n", item, i);
        }
    }
}

void displayStack()
{
    for(int i=0; i<=top; ++i)
    {
        printf("%d ", s[i]);
    }
    printf("\n");
}

void pop()
{
    if(top == -1)
    {
        printf("Stack Underflow.\n");
        return;
    }
    printf("%d\n", s[top]);
    enqueue(s[top]);
    s[top--] = 0;
}

int main()
{
    int choice, exitcode = 1, item;

    do
    {
        showMenu();
        printf("Enter choice:\n");
        scanf("%d", &choice);
        switch(choice)
        {
        case 1:
            printf("Enter item to enqueue:\n");
            scanf("%d", &item);
            enqueue(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 2:
            dequeue();
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 3:
            displayQueue();
            break;
        case 4:
            printf("Enter item to search:\n");
            scanf("%d", &item);
            searchQueue(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 5:
            displayStack();
            break;
        case 6:
            printf("Enter item to search:\n");
            scanf("%d", &item);
            searchStack(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 7:
            pop();
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 8:
            exitcode = 0;
            break;
        }
    }
    while(exitcode == 1);

    return 0;
}

UVA Problem 458 (The Decoder) Solution

UVA Problem 458 (The  Decoder) Solution:


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

Solving Technique:

Run time 15 ms ( 0.015 s ), Rank 377

This problem is really easy. The description is quite straight forward. The codes are scrambled based on simple arithmetic manipulation in ASCII value. From comparing input and output we can find the value of how much we need to shift ( add or subtract ) the ASCII value to match the output. In this problem if we subtract all character of given sentence by 7 then we get the correct output. Here I have first modified all the character of the string with 7 less than given character ASCII value.

Here I have modified the string inline in the for loop increment portion. It is rather short.

Important: No extra space or blank lines. Also one can modify and keep printing characters one by one. But that process is really slow.


Input:

1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5

Output:

*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.

Code:

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link https://quickgrid.wordpress.com
 * Problem: UVA 458 ( The Decoder )
 */

#include<stdio.h>

static char t[1024];

int main(){
    register unsigned i;
    while(gets(t)){
        for(i = 0; t[i]; t[i] -= 7, ++i);
        puts(t);
    }
    return 0;
}

UVA Problem 483 (Word Scramble) Solution

UVA Problem 483 (Word Scramble) Solution:


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

Solving Technique:

This problem asks us to reverse each words in a given sentence. There may be other better and faster solutions. I’ve implemented my solution using stack. First we are looking for space or null character. If those are not found we keep pushing characters in stack until we find space or null character. While doing that we also keep a count of number of items we pushed in the stack. So now if we find a space character or a null character we keep popping and printing the items the number of times pushed. We also check to see if we reached the last character in which case we don’t print any space character.

Important: We should not reverse the whole string but only each words. Also make sure there are no trailing space ( I got Presentation Error (PE) for this ) after the end of sentence. Also there should not be extra blank lines.


Critical Input:

I love you.
You love me.
We're a happy family.

Critical Output:

I evol .uoy
uoY evol .em
er'eW a yppah .ylimaf

Code:

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

#include<stdio.h>

int top = -1;
char st[1000], sentence[1000];

void push(char c){
    st[++top] = c;
}

void pop(){
    printf("%c", st[top]);
    st[top--] = '\0';
}

int main(){
    int c = 0;
    
    while (gets(sentence)){
        for (int i = 0; sentence[i]; ++i){
            if (sentence[i + 1] == '\0' || sentence[i] != ' '){
                push(sentence[i]);
                ++c;
            }
            if (sentence[i] == ' ' || sentence[i + 1] == '\0'){
                for (int j = 0; j < c; ++j){
                    pop();
                }
                c = 0;
                if(sentence[i + 1] != '\0'){
                    printf(" ");
                }
            }
        }
        printf("\n");
    }

    return 0;
}

UVA Problem 272 (TEX QUOTES) Solution

UVA Problem 272 (TEX QUOTES) Solution:


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

Solving Technique:

This problem is relatively easy. In this problem we are asked to replace a pair of quotes. The first quote replaced with two ( ` ) character and next quote replaced with two ( ‘ ) character. Besides testing with given inputs we should also test with other inputs such as inputs given below before submission.

We can also solve this problem by printing characters one by one when they are found. But that process is really slow. We should consider first creating a string for the things we want to print then print them altogether using only one printf.

Also consider making loop counter variables register. This doesn’t guarantee that variables will be stored on register but if they are then our program runs a lot faster.

Another thing is we need some kind of ON OFF switch, or Flip Flop to check when we get Grave Caret ( ` ) or when we get a single quote ( ). Here in my code the variable ( c ) is doing that job.

ASCII values instead of characters,

' 39     /* Single Quote */
` 96     /* Grave Caret */
" 34     /* Double Quote */

Important: The quotes should be considered for the whole input not line by line.


Critical Input:

""
"""
""""

Critical Output:

``''
``''``
''``''``

Code:

#include<stdio.h>

static char t[256];

int main(){
    register unsigned i, k, c = 0;

    while(gets(t)){
        char inp[256] = {'\0'};

        for (i = k = 0; t[i]; ++i){
            /*
             * ASCII decimal value of " (Double Quotes) is 34
             */
            if (t[i] == 34 && !c){
                /*
                 * ASCII decimal value of ` (Grave Caret) is 96
                 */
                inp[k] = inp[k+1] = 96;
                /*
                 * We added TWO characters
                 */
                k += 2;
                /*
                 * Flag or ON OFF
                 */
                c = 1;
            }else if(c && t[i] == 34){
                /*
                 * ASCII decimal value of ' (Single Quote) is 39
                 */
                inp[k] = inp[k+1] = 39;
                k += 2;
                c = 0;
            }else{
                /*
                 * If neither single or Double Quote found
                 */
                inp[k] = t[i];
                ++k;
            }
        }
        printf("%s\n", inp);
    }
    return 0;
}