Kalmakka (kalmakka) wrote in topcoder,

  • Mood:

TCO 06 Round 3

A very simple binary game problem. A position is a winning position (to be given) if it is possible to reach a loosing position from it. It is a loosing position if only winning positions can be reached from it.
I read the constraints a bit too fast, so my program only worked for n<200. I noticed this before submitting, but only changed it for my array size and not for how long my loop was too run. A resubmit brought me down to 176 pts.

While checking for loops to see if anybody had temself as an ancestor was simple, checking for genders properly was something that most people (including me) forgot, thus resulting in a LOT of challenges. For instance, if A and B have a child, and B and C have a child, then it is impossible for A and C to have a child.
To check wether a valid gender-assignment exists, make a graph where the nodes are the people and the edges are the people who have had a child. Color the nodes of people with known genders with your two favorite colours, and spread out with colours so that no edge connects to nodes with the same colour. If any nodes remain uncoloured, colour a random uncoloured node with your favorite colour and progress.

I never seem to solve these problems involving sexes :P

My original solution for this was based on just finding the probability of being able to be at home at any time. After submitting, I realized that this wouldn't work. For instance, if one bus leaves every minute and takes 10 minute to get you home, and the other bus leaves every 7 minutes and takes 5 minutes to get you home, my program would think that you could always be home 10 minutes after start. However, waiting for the fast bus is always advantageous, so it might take up to 11 minutes to get home. I almost had a correct solution done when the timer ran out. Basicly, you need to DP and see if waiting 1 minute and hoping to catch a faster bus is better than taking a slow bus now.

My recursive solution was, after cleaning it up a bit,
     //bus contains <tripTime,waitTime> pairs sorted by ascending traveltime, kt is time after start
double dome(vector<pair<int,int> > &bus, int kt){ 
  if (kt==bus[0].second-1) return bus[0].first;
  double timeIfWait = 1+dome(bus,kt+1);
  double s=0.0;
  double pwait=1.0; //probability of waiting
  for (int i=0;i<bus.size();i++){
    double p = 1.0/max(bus[i].second-kt,1); //probability that bus i gets here now
    if (bus[i].first < timeIfWait){
  return s+pwait*timeIfWait;

Solving the 200 really really really fast was sufficient to advance. Or you could just do like futo or bugzpoddere and break a lot of solutions. Or, like I did, you can do something in between. I found a 200 solution in C++ where the DP array was of size exactly 100000. Knowing that 176pts wouldn't be enough to advance, I took a chance and challenged it.
  • Post a new comment


    default userpic

    Your IP address will be recorded