Problem Analysis for Zeke and his Password Encryption

PROBLEM: Zeke and his Password Encryption

This problem can be solved as follows:
This problem can be solved easily using the concept of AVL trees.
Output is preorder traversal of the AVL tree created after balancing.

Problem setter's solution in C:

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

struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
};

int height(struct node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

int max(int a, int b)
{
    return (a > b)? a : b;
}

struct node* newNode(int key)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;
    return(node);
}

struct node *rightRotate(struct node *y)
{
    struct node *x = y->left;
    struct node *T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;

    // Return new root
    return x;
}

// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
    struct node *y = x->right;
    struct node *T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;

    // Return new root
    return y;
}

// Get Balance factor of node N
int getBalance(struct node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

struct node* insert(struct node* node, int key)
{
    /* 1.  Perform the normal BST rotation */
    if (node == NULL)
        return(newNode(key));

    if (key < node->key)
        node->left  = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    /* 2. Update height of this ancestor node */
    node->height = max(height(node->left), height(node->right)) + 1;

    /* 3. Get the balance factor of this ancestor node to check whether
       this node became unbalanced */
    int balance = getBalance(node);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

void preOrder(struct node *root)
{
    if(root != NULL)
    {
        printf("%d", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main()
{
  struct node *root = NULL;
  int n,a,i,t;
  scanf("%d",&t);
  while(t--)
  {
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    scanf("%d",&a);
    root=insert(root,a);
  }
  preOrder(root);
  root=NULL;
  printf("\n");
  }
  return 0;
}

Problem Analysis for Sid and his Dream Home

PROBLEM: Sid and his Dream Home

This problem can be solved as follows:
Instead of using the traditional brute force technique to solve this problem.
This problem can be solved easily using the method of long multiplication and using the concept of strings.
Both numbers are taken as strings, converted to numbers and multiplication is carried out and then output is again a string.

Problem setter's solution in C:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10000

char * multiply(char [],char[]);
int main()
{
    char a[MAX];
    char b[MAX];
    char *c;
    int la,lb;
    int i,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",a);
        scanf("%s",b);
        c = multiply(a,b);
        printf("%s\n",c);
    }
    return 0;
}

char * multiply(char a[],char b[]){
    static char mul[MAX];
    char c[MAX];
    char temp[MAX];
    int la,lb;
    int i,j,k=0,x=0,y;
    long int r=0;
    long sum = 0;
    la=strlen(a)-1;
    lb=strlen(b)-1;

        for(i=0;i<=la;i++){
                a[i] = a[i] - 48;
        }

        for(i=0;i<=lb;i++){
                b[i] = b[i] - 48;
        }

    for(i=lb;i>=0;i--){
         r=0;
         for(j=la;j>=0;j--){
             temp[k++] = (b[i]*a[j] + r)%10;
             r = (b[i]*a[j]+r)/10;
         }
         temp[k++] = r;
         x++;
         for(y=0;y<x;y++){
             temp[k++] = 0;
         }
    }
    k=0;
    r=0;
    for(i=0;i<la+lb+2;i++){
         sum =0;
         y=0;
         for(j=1;j<=lb+1;j++){
             if(i <= la+j){
                 sum = sum + temp[y+i];
             }
             y += j + la + 1;
         }
    if(((((sum+r) %10)==0)&&i<(la+lb+1))||((((sum+r)%10)!=0)))
         c[k++] = (sum+r) %10;
         r = (sum+r)/10;
    }
    c[k] = r;
    j=0;
    for(i=k-1;i>=0;i--){
         mul[j++]=c[i] + 48;
    }
    mul[j]='\0';
    return mul;
}

Problem analysis for Funny Numbers

PROBLEM: Funny numbers

This problem can be solved as follows:
Using Sieve of Eratosthenes, generate a array primes[] such that
primes[x] = 1 if x is prime.
Now for each input N, check for divisibility starting from 2 till square root of N.
whenever a number divides N, repeatedly divide it until, it is
not divisible by that number anymore. Each time it is divisible,
increment a count variable to keep track of the number
of prime factors.
If N != 1 after all the repeated divisions till sqrt(N), then, what remains is guaranteed to be prime number and hence increment count once again.
Next, check if primes[count] == 1.
If so, print Yes, else print No.

Problem setter's solution in C++:

#include <iostream>
#include <cmath>

using namespace std;

static const long long MAX = 1000000;

long long primes[MAX+1];


// uses sieve of Eratosthenes to generate prime numbers till 1000000
void init() {
    primes[1] = 1;
    primes[0] = 1;
    for(long long i = 2; i <= MAX; i++) {
        for(long long j = i*i; j <= MAX && !primes[i]; j += i) {
            //cout << j << endl;
            primes[j] = 1;

        }
    }
}

int main(void) {
    init();
    long long t;
    cin >> t;
    while(t--) {
        long long x;
        cin >> x;
        long long c = 0;
        int sq = sqrt(x);
        for(int i = 2; i <= sq; i++) {
            if(x%i == 0)
                c++;
            while(x%i == 0)
                x /= i;
        }
        if(x > 1)
            c++;
        if(!primes[c])
            cout << "Funny" << endl;
        else
            cout << "Not Funny" << endl;
    }
    return 0;
}

Problem analysis of Help Amanda

PROBLEM: HELP AMANDA

Amanda's problem can be easily solved using depth first search (DFS).
In fact, finding connectivity and cyclicity is one of the applications of DFS.


PSEUDOCODES:

// To find cyclicity
#define CON_A MAT[src][i] == 1
#define CON_B src != i
#define CON_C (i is visited)
#define CON_D tos >= 2
#define CON_E stack.elementAt(tos-2) != i


void dfs(int src) {
    source is marked as visited.
    stack.push(source)
    for(int i = 0; i < nodes; i++) {
        if(CON_A && CON_B && CON_C && CON_D && CON_E) {
            cyclic = 1;
        }
        if(adj[src][i] == 1 && s[i] == 0) {
            dfs(i);
        }
    }
    top--;
}

/* stack.elementAt(tos-2) != i means to say that the vertex visited just immediately is not i. since a cycle has at least 3 vertices. */
// so if tos-2 is not i and i is visited, it means there is a cycle.


// TO FIND CONNECTIVITY

dfs(src)

void isConnected(void) {
    for(int i = 0; i < nodes; i++)
        if(s[i] == 0) {
            connected = false;
            return;
        }
}

Problem analysis of Is it Fibbonacci

PROBLEM: IS IT FIBONACCI

The program asks you to find whether the given number is a fibonacci number or not.
Instead of generating fibonacci numbers for every query F, we can generate all fibonacci numbers till 2^64 and store it in an array FIB[].
For each query F, you can have a binary search (Since the fibonacci numbers are always in ascending order) and see if the number exists in the array.
If yes, print YES else print NO.

PSEUDOCODE:

FIB[]

def generate():
    a = 0
    b = 1
    LIM = 2**64 ## i.e., 2^64
    while a < LIM:
        FIB.append(a)
        c = a+b
        a = b
        b = c

def binarySearch(low, high, find):
    while low <= high:
        mid = (low+high)//2        ## integer division
        if FIB[mid] == find:
            return 1
        elif FIB[mid] < find:
            low = mid+1
        else
            high = mid-1
   
    return 0
   
## DRIVER FUNCTION

generate()
T = int(input())
while t > 0:
    f = int(input())
    if binarySearch(0, len(FIB)-1, f):
        print ("YES")
    else
        print ("NO")
    t = t - 1
   
   

PROBLEM SETTER'S CODE IN C++:

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
static const int LIM = 94;   
typedef unsigned long long ull;

ull FIB[LIM];

void generate() {
    ull a = 0;
    ull b = 1;
    ull c;
    for(int i = 0; i < LIM; i++) {
        FIB[i] = a;
        c = a+b;
        a = b;
        b = c;
    }
}


int main(void) {
    generate();
    int t;
    cin >> t;
    ull f;
    while(t--) {
        cin >> f;
        bool status = binary_search(FIB, FIB+LIM, f);
        if(status == false)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}

Problem analysis of Ponyo

PROBLEM: PONYO

Simply put, the problem asks you to find the longest subsequence of STR containing only R.
This can be done as given in the following pseudocode:

PSEUDOCODE:

STR = input()
i = 0
m = 0
c = 0
l = len(STR)
while i < l:
    if STR[i] == 'R':
        c++
    else
        c = 0
    if(m < c)
        m = c
    i = i + 1
print(m)

PROBLEM SETTER'S CODE IN C++:

#include <iostream>
#include <string>

using namespace std;

int main(void) {
    int t;
    cin >> t;
    string str;
    while(t--) {
        cin >> str;
        int d = 0;
        int len = str.size();
        int cnt = 0;
        for(int i = 0; i < len; i++) {
            if(str[i] == 'R')
                cnt++;
            else
                cnt = 0;
            if(cnt > d)
                d = cnt;
        }
        cout << d << endl;
    }
    return 0;
}

UCode - August

***********Congratulation to the Winners of UCode***************
****Overall Winners
1 Man Mohan Mishra - m_17 IIIT-A
2 VijayaRaghavan Jamdarkhana - vijayarsenal10 - RVCE
3 Vishnu V Narayan - vvneagleone - RVCE
****UVCE Winners
1 Shubham Kumar Bhuyan - shubham_kumar - UVCE
2 Bharat Ugru - bharatugru - UVCE
3 Vikas Raju - robinhud - UVCE
UCode was one of the most successful competition conducted by us. Many UVCEans turned up and freshers performed really well.
Thanks to all the participants for making this contest a successful one.
Thanks to Vishal Antony and Abhishek Dutta who designed the questions for the contest.
Thanks to CodeChef for providing the platform for our contest and Thanks to IEEE UVCE for supporting us in making this contest a successful one.
Please provide your feedback https://docs.google.com/forms/d/1aIM1OiDNrzCXEyoUjW0zIs511OJdLOubBA-yQ8cH004/viewform
See you in the UCode-September.....
Till then Happy Coding.........