Competitive Programming – Bus Stops Problem – Video

Posted on October 12, 2019 by

In competitive programming, following the ICPC rules, one of the best strategies is to scan the problems given to your team and to start with the easiest ones. The easiest ones are not always the first problems and sometimes these do not have a tag “EASY” on the first 2 sentences. On the contrary, one should read them up to the end to determine these are not some complicated algorithmic implementation, but rather a challenge to use list of list correctly. As a rule of a thumb, the implementation of a solution for these problems is never complicated, however understanding the problem correctly and coming up with a good solution is the task is sometimes challenging.

I have made a video of me, doing live-coding on one of the “easy” problems, given by the Moscow Workshops ICPC in Riga 2019. The task is available for a download here.

The code, used in the video is this one:

using System;
using System.Collections.Generic;
using System.Linq;

class Startup
{
    static void Main()
    {
        List input = ReadLineAndParseToList();
        int startingStop = input[0] - 1;
        int numberOfBuses = input[1];
        int numberOfStops = input[2];

        List routes = new List();
        List thingsToSee = new List();

        int maxStops = 0;

        for (int i = 0; i < numberOfStops; i++)
        {
            thingsToSee.Add(0);
        }

        for (int i = 0; i < numberOfBuses; i++)
        {
            string busRoute = Console.ReadLine();
            routes.Add(busRoute);
        }

        foreach (string route in routes)
        {
            if (route[startingStop] == '1')
            {
                for (int i = 0; i < numberOfStops; i++)
                {
                    if (route[i] == '1' &&  thingsToSee[i]!=1)
                    {
                        thingsToSee[i] = 1;
                        maxStops++;
                    }
                }
            }
        }
        if (maxStops>0)
        {
            maxStops--;
        }
        Console.WriteLine(maxStops);
    }

    private static List ReadLineAndParseToList()
    {
        return Console.ReadLine().Split().Select(int.Parse).ToList();
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Startup

{

static void Main()

{

List input = ReadLineAndParseToList();

int startingStop = input[0] - 1;

int numberOfBuses = input[1];

int numberOfStops = input[2];

List routes = new List();

List thingsToSee = new List();

int maxStops = 0;

for (int i = 0; i < numberOfStops; i++)

{

thingsToSee.Add(0);

}

for (int i = 0; i < numberOfBuses; i++)

{

string busRoute = Console.ReadLine();

routes.Add(busRoute);

}

foreach (string route in routes)

{

if (route[startingStop] == '1')

{

for (int i = 0; i < numberOfStops; i++)

{

if (route[i] == '1' && thingsToSee[i]!=1)

{

thingsToSee[i] = 1;

maxStops++;

}

if (maxStops>0)

{

maxStops--;

}

Console.WriteLine(maxStops);

}

private static List ReadLineAndParseToList()

{

return Console.ReadLine().Split().Select(int.Parse).ToList();

}

Enjoy it! 🙂