CodeJam 2014 – Qualifying – C – Minesweeper Master

TC = input()
for tc in range(1, TC+1):
    r, c, b = map(int, raw_input().split())
    f = (r*c)-b;
    
    if r==1:
        st = "c" + "."*(f-1) + "*"*b
    elif c==1:
        st = ("c\n" + ".\n"*(f-1) + "*\n"*b)[:-1]
    elif f==1:
        st = "c" + (("*"*c + "\n")*r)[1:-1]
    elif f%2==0 and f<4:
        st = "Impossible"
    elif f%2==1 and f<9:
        st = "Impossible"
    elif f%2==1 and (r<3 or c<3):
        st = "Impossible"
    elif f%2==0 and f < 2*c:
        st = "c" + (("."*(f/2) + "*"*(c - f/2) + "\n")*2 + 
            ("*"*c + "\n")*(r-2))[1:-1]
    elif f%2==1 and f < (2*c + 3):
        x = (f-3)/2
        st = "c" + (("."*x + "*"*(c-x) + "\n")*2 + 
            ("."*3 + "*"*(c-3) + "\n") + 
            ("*"*c + "\n")*(r-3))[1:-1]
    elif f%c==1:
        st = "c" + (("."*c + "\n")*(f/c - 1) + 
            ("."*(c-1) + "*\n") + 
            ("."*2 + "*"*(c-2) + "\n") + 
            ("*"*c + "\n")*(r - f/c - 1))[1:-1]
    else:
        st = "c" + (("."*c + "\n")*(f/c) + 
            ("."*(f%c) + "*"*(c - f%c) + "\n")*(f%c>0) + 
            ("*"*c + "\n")*(r - f/c - (f%c>0)))[1:-1]
        
    print "Case #%d:\n%s"%(tc, st)

This week is the start of the codejam. Some of the problems this year were okay, I did the first 2 pretty quickly, but this 3rd one is rather tricky. There are many cases that I have to account for. I tried a few submissions, each time finding more special cases then the last. Finally I gave up.

Today, I went online to search for a working solution. This is my implementation of it in python. The document is pretty comprehensive. Although my solution is similar, there is one case which I did not accounted for, which is the last case of the non-single mine special case.

Anyway, this was a pretty fun experience. As of now, I have completed the first 3 questions, and if I have the time next week I will be embarking on the 4th question, the hardest in the set.

CodeJam 2008 Minimum Scale Product

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <map>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
using namespace std;

#define FOR(i, n) for(int i=0; i<n; i++)

int main(){
    int TC; scanf("%d", &TC);
    FOR(tc, TC){
        int n; scanf("%d", &n);
        double v[2][n];
        
        FOR(j, 2){
            FOR(i, n){ scanf("%d", &v[j][i]); }
        }
        
        sort(v[0], v[0]+n);
        sort(v[1], v[1]+n);
        
        double t = 0;
        FOR(i, n){
            t += v[0][i] * v[1][n-1-i];
        }
        
        printf("Case #%d: %d\n", tc+1, t);
    }
    
    return 0;
}

This problem was pretty simple once you figure out how it was supposed to be done. The phrasing of the question was somewhat problematic and it took me a few moments before I am able to figure out the solution. The solution was pretty simple, but it could be even easily computed in Python. Anyway, the result is that I have passed the small input, but for the large input, it was marked incorrect. So…

CodeForce Round #239 A – Triangles

I saw this programming website called codeforce, the problem there looked quite fun and to train my coding speed and increase exposure to these kinds of problems, i tried out some of them and it actually gave me a chance to understand the basics of C++ better. Looks like I will be completing more problems on this platform…

#include <cstdio>
#include <cmath>
#include <vector>
#include <utility>
using namespace std;

int main(){
    int a, b; scanf("%d %d", &a, &b);
    
    vector< pair<int, int> > p1, p2;
    float x=a, y=0, c, d;
    while(x>0){
        c = x*x + y*y; d = a*a;
        if(c==d){
            if(x!=0 && y!=0){
                p1.push_back(make_pair(x, y));
                p1.push_back(make_pair(-x, y));
                p1.push_back(make_pair(x, -y));
                p1.push_back(make_pair(-x,-y));
            }
            y++;
        }
        if(c>d) x--;
        if(c<d) y++;
    }
    
    x=b, y=0;
    while(x>0){
        c = x*x + y*y; d = b*b;
        if(c==d){
            if(x!=0 && y!=0){
                p2.push_back(make_pair(x, y));
                p2.push_back(make_pair(-x, y));
                p2.push_back(make_pair(x, -y));
                p2.push_back(make_pair(-x,-y));
            }
            y++;
        }
        if(c>d) x--;
        if(c<d) y++;
    }
    
    pair<int, int> p;
    float x1, y1, x2, y2;
    float g; d=0;
    for(int i1=0; i1<p1.size(); i1++){
        p = p1.at(i1);
        x1 = p.first; y1 = p.second;
        
        for(int i2=0; i2<p2.size(); i2++){
            p = p2.at(i2);
            x2 = p.first; y2 = p.second;
            if(y1==y2 || x1==x2) continue;
            
            if(y1/x1 == (x2/y2)*-1){ d=1; break; }
            
            g = -1*((y1-y2)/(x1-x2));
            if(g == x2/y2 || g == x1/y1){ d=1; break; }
        }
        if(d) break;
    }
    
    if(d) printf("YES\n%d %d\n%d %d\n0 0", int(x1), int(y1), int(x2), int(y2));
    else printf("NO");
    
    return 0;
}

CodeJam 2008 Reverse Words

#include <cstdio>
#include <cstring>
using namespace std;

int main() {
    char line[1024], line2[1024], ws[512][1024], *w;
        gets(line);
    
        int TC, wc=0; sscanf(line, "%d\n", &TC);
    for(int tc=1; tc<=TC; tc++){
        gets(line);
        memset(line2, NULL, 1024);
        memset(ws, NULL, 1024*512);
        
        w = strtok(line, " ");
        while(w!=NULL){
            strcpy(ws[wc], w); wc++;
            w = strtok(NULL, " ");
        }
        
        strcpy(line2, (char*) " ");
        for(int i=0; i<=wc; i++){
            strcat(line2, ws[wc-i]);
            strcat(line2, (char*) " ");
        }
        
        printf("Case #%d:%s\n", tc, line2);
    }
    return 0;
}

As part of learning the C++ language, I tried to do some problems requiring string processing. The process of string processing is indeed a much easier task in Python. In C++, the task of string formatting is pretty complicated and there is lots of extra steps that have to be taken to format the string into the characters array. Anyway, this is pretty good practise for me, so…