The wondering mind of Mark, the Great and Powerful

Single Round Match 295

Mark Gordon — Fri, 31 Mar 2006 17:52:00 GMT

Ok, so I think I'm going to start using this blog to discuss TopCoder Competitions. Single Round Match 295, which was on Wednesday, was pretty fun, although I'm a little disappointed that I only got the first problem. My rating went up nonetheless.

So, you can view the first problem here, (you have to be logged in, sorry) basically the idea was that you were trying to build a bridge of D length with cards of L length and you had to return the amount of cards necessary to complete it. It had some stuff about equilibriums and center of masses... but the pictures they provided made it clear that each card added 1/(2n) units to the bridge where n is the card number. So all you had to do was sum 1/(2n) until it was greater than D/L (lol)

class BuildBridge
{
public:
int howManyCards(int D, int L)
{
    int i;
    double dist = 0.0;
    for (i = 2; L * dist < D - 1e-9; i+=2)
    {
        dist += 1.0 / (double)i;
    }
    return i / 2 - 1;
}
};

Unfortunately, I misread the 500 point question. You can view it here. You had to assist thief “Jimmy Lightning” steal the greatest value of diamonds. You were given a list of diamonds that each had a value, the amount of time it took to steal, and the room it was located in. Jimmy instantly moves from one room to another. To make things complicated, each door closes at a certain time after the robbery begins. Rooms are connected linearly, so you need to go through room 3 to go from room 2 to room 4 (I missed this part). Also, you must leave through door 1.

One of the rules on TopCoder is that your algorithm must complete in 2 seconds. That means you just can't brute force this with a recursive method. I attacked this problem by realizing that at any time t, after the robbery began there is only one way to get the greatest value of diamonds. So at any time t you should try to steal every type of diamond that you can with the room being accessible after you steal it, and recursively call the same function at t + the time it takes to steal that diamond. After the highest value has been obtained from those returned values, simply store that number to a cache, and if later is your function is called at that same value of t you already have the answer. (Note I got this wrong during the competition but I fixed it after)

class JimmyLightning
{
public:
vector <int> doors;
vector <int> dv;
vector <int> dt;
vector <int> dr;
vector <int> maxdoor;
vector <int> cache;

int robTheBank(vector <int> d, vector <string> diamonds)
{
    doors = d;
    for (int i = 0; i < diamonds.size(); i++)
    {
        int v, t, r;
        stringstream ss;
        ss << diamonds[i];
        ss >> v >> t >> r;
        dv.push_back(v);
        dt.push_back(t);
        dr.push_back(r);
    }
    int i = 0;
    do
    {
        int md = -1;
        for (; md < (int)doors.size() - 1; md++)
        {
            if (i >= doors[md + 1])
                break;
        }
        maxdoor.push_back(md);
        cache.push_back(-1);
    } while (maxdoor[i++] != -1);
    solve(0);
    return cache[0];
}
void solve(int t)
{
    if (cache[t] != -1)
    return;

    vector <int> res;
    for (int i = 0; i < dv.size(); i++)
    {
        if (t + dt[i] < maxdoor.size())
            if (dr[i] - 1 <= maxdoor[t + dt[i]])
            {
                solve(t + dt[i]);
                res.push_back(cache[t + dt[i]] + dv[i]);
            }
    }
    int max = 0;
    for (int i = 0; i < res.size(); i++)
        if (res[i] > max)
            max = res[i];
    cache[t] = max;
}
};

The third problem was sort of a downer. You can view it here. I didn't get this problem and I still haven't been able to get it to work. I had to read the analysis of this problem after it was posted to figure out how you were supposed to do it. This problem statement is pretty long so I'll leave out a summary of it.

This problem was supposed to be done by a simple simulation. Obviously you can get into an infinite loop of “W“s that would cause a problem. Another rule of top coder is that when you are returning double values you can be off by (absolutely or relatively) 1e-9. So the idea in this problem was just to simulate the problem until the results of the function call become so insignificant (by running into a lot of “W”s) that you don't have to go any further in the simulation. I tried to implement this idea but I couldn't get it working on all of the test cases.

zsocket

Mark Gordon — Tue, 28 Mar 2006 20:59:00 GMT

All code highlighting was done by SourceFormatX

Class: zsocket : Header | Html
Author: Mark, the Great and Powerful
Date of Creation: 9/2/05
Last Update: 3/11/06
Library Dependencies: Ws2_32.lib

zsocket is a handy class that I created that handles tcp communication similarily to the WinSock control. I implemented “events” (error, statechange, connectionrequest, and dataarrival) by having the client code inherit the zsocket class and override these methods. (You don't have to override any of them) All of the classes functionality is run on one seperate thread (for all instances of zsocket) so even if the thread that created the socket is busy, it can still continue to function. One thing you have to watchout for however is the fact that all the events are called by the single thread that runs all of the sockets. So if you do something in that thread that takes an excessive amount of time, no other sockets (including the current socket) can continue to function and recieve messages. Note that syncconnect and flush will allow sockets to continue to function.

Below are the avaliable functions that a deriving class can override

virtual void error(int num, std::string description) {}
virtual void statechange(SocketState oldstate) {}
virtual void connectionrequest(int requestid) {}
virtual void dataarrival(int bytessent) {}

Here is a sample cleint program using zsocket. It just simply connects to google and requests its homepage.

#include <iostream>
#include "zsocket.hpp"
using namespace std;
class mysck: public zsocket
{
public:
    virtual void error(int num, std::string description)
    {
        cout << "Error #" << num << "\t" << description << endl;
    }
    virtual void statechange(SocketState oldstate)
    {
        if (oldstate != sckConnected && state() == sckConnected)
        {
            cout << "CONNECTED :D" << endl;
            //issue request
            sendstring("GET / HTTP/1.1\r\n\r\n");
        }
    }
    virtual void connectionrequest(int requestid)
    {
        //This is a client program so it should not be recieving any requests
    }
    virtual void dataarrival(int bytessent)
    {
        //To get a string containing the data sent, call getdata()
        cout << getdata() << endl;
    }
};
int main()
{
    //Let's try it out
    zsocket * sck = new mysck();
    sck->sckconnect("www.google.com", 80);
    system("pause");
    delete sck;
    return 0;
}

Here is an example server program using zsocket. This is just a basic http server. For purposes of keeping this code segment short, it has a memory leak due to mysck instances not being deleted. After running this, try going to http://127.0.0.1

#include <iostream>
#include "zsocket.hpp"
using namespace std;
class mysck: public zsocket
{
public:
    virtual void error(int num, std::string description)
    {
        cout << "Error #" << num << "\t" << description << endl;
    }
    virtual void dataarrival(int bytessent)
    {
        //Being a simple server, we'll just send back a hello world
        sendstring("HTTP/1.1 200 OK\r\nContent-Length: 11\r\n\r\nHello World");
    }
};
class myserver: public zsocket
{
public:
    virtual void error(int num, std::string description)
    {
        cout << "Error #" << num << "\t" << description << endl;
    }
    virtual void statechange(SocketState oldstate)
    {
        if (oldstate != sckListening && state() == sckListening)
        {
            cout << "LISTENING :D" << endl;
        }
    }
    virtual void connectionrequest(int requestid)
    {
        //spawn a socket to take the connection
        zsocket * sck = new mysck();
        sck->sckaccept(requestid);
    }
    virtual void dataarrival(int bytessent)
    {
        //This is a server socket so it shouldn't recieve data
        //but it could if it later connected or accepted a connection request
    }
};
int main()
{
    //Let's try it out
    zsocket * svr = new myserver();
    svr->scklisten(80);
    system("pause");
    delete svr;
    return 0;
}

Constructor
    zsocket();  //Creates a basic socket object and initializes the zsocket thread if needed
Methods
    //Syncronous connect methods
    bool syncconnect(std::string zhost, int zport,int timeout);
    bool syncconnect(int timeout);
    bool syncconnect(std::string zhost, int zport);
    bool syncconnect();
    //Asyncronous connect methods
    void sckconnect(std::string zhost, int zport, int timeout);
    void sckconnect(int timeout);
    void sckconnect(std::string zhost, int zport);
    void sckconnect();
    //Send methods
    void senddata(void * buf, int length);
    void sendstring(std::string str);
    void sendfile(std::string file);
    //Finishes sending all data for this socket
    void flush();
    //Recieve methods
    std::string getdata();  //Gets data and removes it from the buffer
    std::string peekdata();  //Gets data but does no remove it from the buffer
    //Listen functions
    bool scklisten(int zport);
    bool scklisten();
    //Other functions
    void close();  //Destroys the underlying socket object and creates a new one
    void sckaccept(int requestid);  //Accepts a connection request
    bool waitforconnection(int timeout);  //Attempts to wait for a connection request and connects to it
Properties
    //Local properties
    std::string localip();
    std::string localhost();
    //Remote properties
    std::string remoteip();
    std::string remotehost();
    int port(); //Port to listen on or connect to
    SocketState state(); //Current state of the socket
    int getlasttime(); //The last time (as returned by GetTickCount()) that the socket was sending or recieving data
    int timeout(); //Max timeout while attempting to connect
    int maxsendbuffersize(); //the maximum amount of data in bytes that can be sent in one packet.
    void sethost(std::string zhost); //Set the remote host
    void setport(int zport); //Set the port to listen on or connect to
    void settimeout(int ztimeout); //Set the time in milliseconds to attempt to connect

Who am I?

Mark Gordon — Tue, 28 Mar 2006 19:32:00 GMT

I am Mark, the Great and Powerful¹, revered and feared throughout the great blue nowhere.

I am Mark Gordon, 17 years old, and currently attending Churchill High School in Michigan. I am part of the Math, Science, and Computers program that my school runs which makes everyday... uh... interesting. Whether it be hopscotch on the desks² in the computers room, or dancing to moskau³ (projecting the movie on a wall of course), we try to have fun.

As far as programming goes, I started on VB6, then moved to C++ and Java. I kindof know how to use VB.Net. I love working with WinAPI and sockets and geometry. Alot of the code I post will likely be on those subjects. I also like to write algorithms, so I try to participate on TopCoder⁴ as often as I can. (which hasn't been often lately, but I plan on doing the one tommorow)

Most of the code you will see on my blog will either be in C++ or VB, or maybe even Java. (or in the case of Aaform, a whole lot of languages)

Side Notes⁵

1. I prefer to go my “Mark, the Great and Powerful“ in order to avoid confussion with the other Mark (drydo)

2. This was quite the incident, a certain individual was jumping around on the desks when he slammed his head into the metal projector mount hung from the ceiling. Before getting a paper towel to cover his head, he managed to bleed quite a bit. I believe the story was that he accidentily fell and hit his head on the corner of a desk.

3. This resulted in some detensions when the teacher walked in.

4. You can check out my profile here

5. I like side notes