May 11th, 2014

Google Code Jam 2014 Solution - New Lottery Game

Problem
The lottery had a problem where people were cheating so they decided to upgrade their machines. Cassandra managed to get hold of a formula that, given values A, B and K would tell her how many potential wins she would get.

Solution
The text for this made this problem seem a lot harder than it was. Basically you needed to generate all the bitwise values that cassandra won with then compare them to the values that the machine generated...Really that simple.

Originally I did this and stored all of the generated values for Cassandra & the lottery machine in a list and did a lotteryValues.count(i=>cassandraValues.Any(i)) comparison using Linq. However this was probably a rookie mistake as when the larger datasets came in the permutations rose making the lists huge and clogging up the memory which also made the query slow (Code Jam tip #1, never generate massive data structures). However I rewrote it to use the least amount of memory possible and it seems to have done the trick. Lesson learnt for the future!

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Question2
{
    class Program
    {

    private static StreamReader _input;
    private static StreamWriter _output;

    static int ReadLn()
    {
        return int.Parse(_input.ReadLine());
    }

    static string[] ReadArray()
    {
        return _input.ReadLine().Split(' ');
    }

    static List<int> ReadIntList()
    {
        return ReadArray().Select(int.Parse).ToList();
    }

    static void Main(string[] args)
    {

        _input = new StreamReader("in.txt");
        _output = new StreamWriter("out.txt", false);

        var cases = ReadLn();

        for (int @case = 1; @case <= cases; @case++)
        {

            Console.WriteLine("Case " + @case);

            var values = ReadIntList().ToArray();

            var a = values[0];
            var b = values[1];
            var k = values[2];

            var cassWinVals = new List<int>();

            // generate values where Cassandra wins
            for (int i = 0; i < k; i++)
            {
                for (int j = 0; j < k; j++)
                {
                    var bitwise = i & j;

                    if (!cassWinVals.Contains(bitwise))
                    {
                        cassWinVals.Add(bitwise);
                    }
                }
            }

            var wins = 0;

            // loop through all the combinations the two lottery machines can generate
            for (int i=0; i<a; i++) {
              for (int j=0; j<b; j++) {
                 var bitwise = i & j;

                 // check if the value is one of cassandas if so then she wins.
                 if (cassWinVals.Contains(bitwise))
                 {
                     wins++;
                 }  

              }
            }

            _output.WriteLine("Case #"+ @case + ": " + wins);


        }

        _output.Close();


    }
}
}
comments powered by Disqus