Algorithms Meetup Problem #8 Easy, #9 Medium, #10 Hard, Game Competitions

From: Andy P.
Sent on: Sunday, August 29, 2010 12:41 PM
Hi Everyone,

1) Competitions

I want to start new tradition. Game competitions. I created couple of folders on github (Competition_xxxx ). So far we have TTT, Checkers, Chess, and Go.

http://github.com/AlgorithmsNYC/AlgorithmsNYC/tree/master/Competition_0001_TicTacToe/
http://github.com/AlgorithmsNYC/AlgorithmsNYC/tree/master/Competition_0002_Checkers/
http://github.com/AlgorithmsNYC/AlgorithmsNYC/tree/master/Competition_0003_Chess/
http://github.com/AlgorithmsNYC/AlgorithmsNYC/tree/master/Competition_0004_Go/

We will have an open discussion about the game design during our next meetup in October. I hope that we will have a couple of implementations ready soon, so we can have actual competition and choose the winning algorithm in each category. It would be awesome to share knowledge and help each other design and implement fully operational game algorithm.

2) Meetup

I scheduled our next meetup for Oct 6h.

http://www.meetup.com/algorithms-and-data-structures/calendar/14502658/

Our speaker will be
Charlie Oshman, Co-Founder, CEO of Reconomy.com. He will be talking about the world of commercial real estate research and data analysis.

We will also have open discussion about designing game algorithms. Please, feel free to share your ideas about this subject during our October meeting.

In the end we will go over a couple of TopCoder problems and look at a few solutions to the "Problem of the week".

3) Problem #8 Easy

Full description is here http://github.com/AlgorithmsNYC/AlgorithmsNYC/tree/master/Problem_0008_Easy/


TopCoder Security Agency (TSA, established today) has just invented a new encryption system! This encryption system takes as its input a list of numbers to encrypt.



You work at TSA and your task is to implement a very important part of the encryption process. You are allowed to pick one number in the input list and increment its value by 1. This should be done in such way that the product of all numbers in the list after this change becomes as large as possible.



Given the list of numbers as int[] numbers, return the maximum product you can obtain. It is guaranteed that the return value will not exceed 2^62.

4) Problem #9 Medium

Full description is here http://github.com/AlgorithmsNYC/AlgorithmsNYC/tree/master/Problem_0009_Medium/

TopCoder Security Agency (TSA, established today) is going to search for dangerous content in the internet.



There are N candidate websites numbered 0 through N-1. Each website has an address given as address[i]. It also has one or more keywords associated with it. The i-th element of keyword is a String describing all keywords associated with the i-th website. It is formatted as a single space separated list of keywords without leading or trailing spaces, where each keyword consists only of lowercase letters.



It is known to TSA that some keywords are dangerous. These keywords are given in String[] dangerous, where each element is a single dangerous keyword. For all other keywords it is not initially known whether they are dangerous or not.



TSA uses the following algorithm to identify all dangerous websites:

?Initially, all websites are considered to be safe.

?While there exists a website W such that it's considered safe and
? ? ? ?at least threshold of its keywords are known to be dangerous

? ?Website W becomes dangerous
? ?All keywords associated with W become dangerous ?

?End While



Return a String[] containing the addresses of all dangerous websites found by the algorithm described above sorted in increasing order of website numbers. Return an empty String[] if no dangerous website is found.

4) Problem #10 Hard

Full description is here http://github.com/AlgorithmsNYC/AlgorithmsNYC/tree/master/Problem_0010_Hard/


Gogo has been hired by the newly founded TopCoder Security Agency (TSA) and has been tasked to encrypt a signal code generated by a radar.



The signal will consist of several positive integers. The order of integers within the signal is not important and therefore should not be preserved during encryption. However, there may be duplicate integers, and the number of occurrences of each integer is important and must be preserved during encryption.



Gogo's idea is to encrypt these integers into a String that consists only of digits '1' and '0'. The encryption scheme is as follows:

? ?* Start with an infinite String consisting solely of '0' characters. The characters within the string are indexed from left to right 1, 2, 3, ... .
? ?* For each input integer X in the signal, Gogo will allocate it within the string. To do this, he will select an index 2^p, where p is a non-negative integer that he may choose arbitrarily, but in such way that characters at indices between 2^p and 2^p + X - 1, inclusive, are all equal to '0'. The allocating procedure consists of replacing all these characters with '1's. This newly created sequence of consecutive '1' characters is said to represent the allocated integer X.
? ?* In order to allow unique decryption, the following property must hold after all numbers from the signal are allocated. For every two integers from the input signal, there must be at least one '0' character between the sequences of '1's that represent these integers.

After all numbers are allocated within the string properly, the '1' character with the largest index is found and all '0' characters to the right of it are removed. The obtained finite string is the result of the encryption procedure.



Given integers to encrypt in int[] numbers, return the length of the shortest string that encrypts them and can be obtained according to the scheme described above. It is guaranteed that this length will not exceed 2^62.

Thanks,
Andy

Our Sponsors

  • Pivotal Labs

    Pivotal Labs

  • Vendavo

    Vendavo is the leader in front-line profit optimization

  • Wolfram Research

    Mathematica is the world's ultimate application for computations.

  • Yodle

    Local online advertising for small businesses.

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy