Ralph And Code-Sigma

This problem was a very straight forward one. There was no tricky part at all. Simply the contestants were to use any efficient algorithm for 0/1 KnapSack problem. 

The purpose behind this problem was to make newbies search the net and find out more about the 0/1 KnapSack problem and it's variants. The best way of solving this problem during a contest is to use Dynamic Programming techniques.

Here is the master Solution in C++:

#include <cstdio>
using namespace std;

class problem 
{
    private:
        int N,H,n;
        long AVG;
        int DIF[550];
        int TIM[550];
        int RAT[550];
        int dp [550][330];
        
        inline void print()
        {
            int rating = AVG/10;
            if ( AVG == 0 )
            {
                printf("FIASCO\n");
                return;
            }
            rating++;
            if ( rating == 11 )
            {
                printf("OUT OF BOX\n");
                return;
            }
            printf("%d\n",rating);
        }
            
    public:
        explicit problem()
        {
            int D,R,T;
            n=0;
            AVG=0;
            scanf("%d %d",&N,&H);
            for(int i=1;i<=N;i++)
            {
                scanf("%d %d %d",&D, &R, &T );
                DIF[i]=D;
                RAT[i]=R;
                TIM[i]=T;
            }
            for(int i=0; i<=H; i++ ) dp[0][H] = 0;
            for( int i=1; i<=N; i++)
                for( int j=0; j<=H; j++)
                {
                    if ( j>= TIM[i] )
                    {
                        if (dp[i-1][j-TIM[i]]+DIF[i] > dp[i-1][j] )
                        {
                            AVG += RAT[i];
                            n++;
                            dp[i][j] = dp[i-1][j-TIM[i]]+DIF[i];
                        }
                        else dp[i][j] = dp[i-1][j];
                    }
                    else dp[i][j] = dp[i-1][j];
                }
            AVG/=n;
            print();
        }
};

int main()
{
    int T;
    scanf("%d",&T);
    while(T--) problem p = problem();
    return 0;

} 


Here is the link to the wikipedia page of 0/1 KnapSack Problem  http://en.wikipedia.org/wiki/Knapsack_problem

Turk And The Colors

This was supposed to be one of the easy problems of Codex 3.0, infact it's solution is much simpler than you might imagine. 

Here is the master solution in C:

#include <stdio.h>

long long MIN3(long long a,long long b,long long c)
{
    if ( a < b && a < c ) return a;
    else if ( b < c ) return b;
    else return c;
}

int main()
{
    int T;
    long long l1, l2, l3, b1, b2, b3, l_min, b_min, ans, mod1, mod2, mod3;
    scanf("%d",&T);
    while ( T-- )
    {
        scanf("%lld %lld %lld %lld %lld %lld",&l1,&b1,&l2,&b2,&l3,&b3);
        l_min = MIN3(l1,l2,l3);
        b_min = MIN3(b1,b2,b3);
        mod1=l1%3; mod2=l2%3; mod3=l3%3;
        if (mod1 == mod2 || mod2 == mod3 || mod1 == mod3)
        {
            printf("0\n");
            continue;
        }
        ans = l_min * ( b_min - (long long)((b_min-1)/3) - 1);
        printf("%lld\n",ans);
    }
    return 0;
}

As you can see, the answer depends on minimum length and minimum breadth. But many people went for nested loops counting the number of squares that will be white. This counting approach is excessively time taking given the limits of input. So, naturally those attempts got TLE ( Time Limit Exceeded ).

Turk and the Message

Master Solution in C:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

char encryption_key[30] = "muyalrdfnzbewvsgxtichokqpj";
char decryption_key[30] = "dktglhpuszweaivyxforbnmqcj";

int shift(int k,int i)
{
if ( i+k > 25 ) return i+k-26;
if ( i+k < 0 ) return 26+i+k;
return i+k;
}

void build_decryption_key()
{
int i;
for ( i=0; i<26; i++ ) decryption_key[encryption_key[i]-97] = i+97;
}

void shift_encryption_key(int k)
{
int i,j=0;
char temp[26];
for (i=0; i<26; i++)
   temp[i]=encryption_key[shift(k,i)];
strcpy (encryption_key, temp );
}

char decrypt(char p) { return decryption_key[tolower(p)-97]; }

void decrypt_file()
{
char p;
int x;
while ( (p=getchar()) != '$' )
{
if ( p=='<')
{
scanf("%d",&x);
getchar();
shift_encryption_key(x);
build_decryption_key();
continue;
}
isalpha(p)?putchar(decrypt(p)):putchar(p);
}
}

int main()
{
decrypt_file();
return 0;
}



This was a simple question on Encryption and Decryption.

There were just 2 tricky things about this question. 1st thing is that in the given encrypted message the keys of 'q' and 'x' were not to be found. But as the question speaks it clearly , " in the initial encryption no english letter is encrypted to itself ", the solution is clear. That 'q' is encrypted to 'x' and 'x' is encrypted to 'q'.

Now, here is another point to notice, the initial encryption key is not in a linear manner. So when the encryption keys are shifted like an Caeser Cipher, just shifting the Decryption key won't do the trick. You will have to shift the encryption keys and then build the decryption keys from it.

Rest of the problem is simple... Read -> Decrypt -> Print. :)

Vampire Diaries

Master Solution in python 3:

for i in input().split():
print(2**(len(bin(int(i)))-2)-1)

As you can see, just 2 lines of code in python 3 ( though a bit tricky ) and the problem is solved. :)

This problem was the simplest of all and even more simple for pythonheads. 

The purpose of this problem was to make the contestants acquainted with bitwise operations. But as you can see, it was not at all necessary to perform bitwise OR on all integers upto n. Because the result is always 2^[log_2(n)+1] -1, where [] is the greatest integer function and log_2 means logarithm of base 2. 

But here is an optimisation trick. You wont need to calculate the log at all, because the value of [log_2(n)+1] is equal to the number of digits when n is written in binary. And all numbers are stored in binary in the computers memory. So, the trick was to find out the length of the number when written in binary.

Many might ask why I wrote " 2**(len(bin(int(i)))-2)-1 ".  In python 3 when you represent a number in binary using the bin function, the output is a string starting with '0b'. For example bin(6) is 0b110. Hence the length of the number is equal to the ( length of the output string - 2 ).