Category Archives: Top Coder

FoxAndClassroom: TopCoder Problem 12811

[The problem appeared in TopCoder SRM 594 (Div-2, Level-1)]
Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=12811

Problem Statement:
Fox Ciel is now in high school. The seats in her classroom are arranged into an n by m matrix. The rows are numbered from 0 to n-1 (front to back) and the columns from 0 to m-1 (left to right).
At the beginning, Ciel can choose any of the seats. Then, at the end of each week Ciel will shift one row to the back and one column to the right, wrapping around whenever necessary. Formally, if her current seat is in row r and column c, then her seat next week will be the one in row ((r+1) modulo n) and column ((c+1) modulo m).
Fox Ciel now wonders whether she can sit in all the seats in the classroom if she follows the above procedure. As we already mentioned, she can start in any of the seats. Also, she can attend the school for as many weeks as she wants to. Return “Possible” if she can sit in all the seats and “Impossible” otherwise.
Continue reading

Advertisements

LittleElephantAndBooks: TopCoder Problem 12112

[The problem appeared in TopCoder SRM 592 (Div-2, Level-1)]

Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=12112

Problem Statement:
Little Elephant from the Zoo of Lviv has a bunch of books. You are given a int[] pages. Each element of pages is the number of pages in one of those books. There are no two books with the same number of pages.

You are also given a int number. As a homework from the teacher, Little Elephant must read exactly number of his books during the summer. (Little Elephant has strictly more than number books.)

All other elephants in the school also got the exact same homework. Little Elephant knows that the other elephants are lazy: they will simply pick the shortest number books, so that they have to read the smallest possible total number of pages. Little Elephant wants to be a good student and read a bit more than the other elephants. He wants to pick the subset of books with the second smallest number of pages. In other words, he wants to pick a subset of books with the following properties:

1. There are exactly number books in the chosen subset.
2. The total number of pages of those books is greater than the smallest possible total number of pages.
3. The total number of pages of those books is as small as possible (given the above conditions).

Return the total number of pages Little Elephant will have to read.
Continue reading

DancingSentence : TopCoder Problem 5950

[The problem appeared in TopCoder SRM 279 (Div-2, Level-1) and SRM 279 (Div-1, Level-1)]

Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=5950&rd=8076

Problem Statement:
A sentence is called dancing if its first letter is uppercase and the case of each subsequent letter is the opposite of the previous letter. Spaces should be ignored when determining the case of a letter. For example, “A b Cd” is a dancing sentence because the first letter (‘A’) is uppercase, the next letter (‘b’) is lowercase, the next letter (‘C’) is uppercase, and the next letter (‘d’) is lowercase.

You will be given a String sentence. Turn the sentence into a dancing sentence by changing the cases of the letters where necessary. All spaces in the original sentence must be preserved.
Continue reading

PalindromeMaker : TopCoder Problem 5881

[The problem appeared in TopCoder SRM 274 (Div-2, Level-2) and SRM 274 (Div-1, Level-1)]
Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=5881&rd=8071

Problem Statement:
A palindrome is a string that is spelled the same forward and backward. We want to rearrange letters of the given string baseString so that it becomes a palindrome.

You will be given a String baseString. Return the palindrome that can be made from baseString. When more than one palindrome can be made, return the lexicographically earliest (i.e., the one that occurs first in alphabetical order). Return “” (the empty string) if no palindromes can be made from baseString.
Continue reading

FewestFactors : TopCoder Problem 5886

[The problem appeared in TopCoder SRM 272 (Div-1, Level-1) and SRM 271 (Div-2, Level-2)]
Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=5886

Problem Statement:
You will be given some decimal digits in a int[] digits. Build an integer with the minimum possible number of factors, using each of the digits exactly once (be sure to count all factors, not only the prime factors). If more than one number has the same (minimum) number of factors, return the smallest one among them.
Continue reading

CompletingBrackets : TopCoder Problem 5977

[The problem appeared in TopCoder SRM 280 (Div-1, Level-1) and TopCoder SRM 280 (Div-2, Level-2)]

Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=5977

Problem Statement:
A series of brackets is complete if we can pair off each left bracket ‘[‘ with a right bracket ‘]’ that occurs later in the series. Every bracket must participate in exactly one such pair.

Given a String text add the minimal number of brackets to the beginning and/or end of text to make it complete. Return the result.
Continue reading

SpamDetector : TopCoder Problem 2229

[The problem appeared in TopCoder SRM 205 (Div-1, Level-1) and TopCoder SRM 205 (Div-2, Level-2)]

Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=2229

Problem Statement:
You are writing part of a spam detection system. Your job is to analyze the subject lines of e-mail messages and return a count of known spam signalling keywords in the subject lines. Your task is made more difficult by the spammers who try to hide the keywords in several ways. Here we will consider just one obfuscation technique: duplicating characters. Duplicating characters means taking an existing character in a word and inserting more copies of that character into the same place in the word. This process can then be repeated on a different character in the word. The spam signalling keyword “credit” might be modified to “creddiT”, “CredittT” or “ccrreeeddiitt”, etc., but not “credict”.

For the purposes of this problem we will consider subject lines which contain only letters and spaces. The “words” in the subject line are delimited by spaces. A word in the subject line is considered a “match” if the entire word is the same as at least one entire keyword, after possibly removing some duplicated characters from the subject word. A keyword that matches only part of a subject word or a subject word that matches only part of a keyword does not count. Note that if a keyword contains a double letter, the subject word must also contain (at least) a double letter in the same position to match (“double letter” means two consecutive letters in the word that are the same). For this application, all matches (and the use of the term “same”) are case insensitive.

Given a subject line and a list of keywords, return the count of words in the subject line which “match” words in the keyword list. If multiple words in the subject line match the same keyword, they are each counted, but a word in the subject line that matches multiple keywords is only counted once.
Continue reading