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

Advertisements

Little Elephant and Lemonade : CodeChef Problem LELEMON

Problem link: http://www.codechef.com/AUG13/problems/LELEMON

Problem Statement:
Little Elephant likes lemonade.

When Little Elephant visits any room, he finds the bottle of the lemonade in that room that contains the greatest number of litres of lemonade and drinks it all.

There are n rooms (numbered from 0 to n-1), each contains C_i bottles. Each bottle has a volume (in litres). The first room visited by Little Elephant was P_0th, the second P_1th, …, the m-th P_{m-1}th room. Note that Little Elephant may visit a room more than once.

Find for Little Elephant the total volume of lemonade he has drunk.
Continue reading

Hello Hello : CodeChef Problem HELLO

Problem link: http://www.codechef.com/AUG13/problems/HELLO/

Problem Statement:
Chef talks a lot on his mobile phone. As a result he exhausts his talk-value (in Rokdas) very quickly. One day at a mobile recharge shop, he noticed that his service provider gives add-on plans which can lower his calling rates (Rokdas/minute). One of the plans said “Recharge for 28 Rokdas and enjoy call rates of 0.50 Rokdas/min for one month”. Chef was very pleased. His normal calling rate is 1 Rokda/min. And he talked for 200 minutes in last month, which costed him 200 Rokdas. If he had this plan activated, it would have costed him: 28 + 0.5*200 = 128 Rokdas only! Chef could have saved 72 Rokdas. But if he pays for this add-on and talks for very little in the coming month, he may end up saving nothing or even wasting money. Now, Chef is a simple guy and he doesn’t worry much about future. He decides to choose the plan based upon his last month’s usage.

There are numerous plans. Some for 1 month, some for 15 months. Some reduce call rate to 0.75 Rokdas/min, some reduce it to 0.60 Rokdas/min. And of course each of them differ in their activation costs. Note – If a plan is valid for M months, then we must pay for (re)activation after every M months (once in M months). Naturally, Chef is confused, and you (as always) are given the task to help him choose the best plan.
Continue reading

Splitting Candies : CodeChef Problem SPCANDY

Problem link: http://www.codechef.com/AUG13/problems/SPCANDY/

Problem Statement:
Cyael is a teacher at a very famous school in Byteland and she is known by her students for being very polite to them and also to encourage them to get good marks on their tests.

Then, if they get good marks she will reward them with candies 🙂 However, she knows they are all very good at Mathematics, so she decided to split the candies evenly to all the students she considers worth of receiving them, so they don’t fight with each other.

She has a bag which initially contains N candies and she intends to split the candies evenly to K students. To do this she will proceed as follows: while she has more than K candies she will give exactly 1 candy to each student until she has less than K candies. On this situation, as she can’t split candies equally among all students she will keep the remaining candies to herself.

Your job is to tell how many candies will each student and the teacher
receive after the splitting is performed.
Continue reading

Utopian Identification Number: Hackerrank

Problem link: https://www.hackerrank.com/challenges/utopian-identification-number

Problem Statement:
A new identification number is given for every Citizen of the Country Utopia and it has the following format.

1. The string must begin with between 0 and 3 (inclusive) lowercase letters.
2. Immediately following the letters, there must be a sequence of digits. The length of this segment must be between 2 and 8, both inclusive.
3. Immediately following the numbers, there must be at least 3 uppercase letters.

Your task is to find out if a given identification number is valid or not.
Continue reading

Detect HTML Tags: Hackerrank

Problem link: https://www.hackerrank.com/challenges/detect-html-tags

Problem Statement:
In this problem you will use regular expressions to help you detect the various Tags used in an HTML document.

Here are a few examples of tags:

The “p” tag for paragraphs:

<p>This is a paragraph</p>

It is also okay to have one or more spaces before or after the tag name:

<  p >This is also a paragraph</p>

Then, there is also something called a void or an empty tag such as:

<p></p>

Some tags can also have attributes. For example, here we see the “a” tag which is used for adding links to a document.

<a href="http://www.google.com">Google</a> 

There are also tags such as this which haven’t been split into an opening and closing tag:

In the above case, “a” is the tag and “href” is an attribute, the value of which is “http://www.google.com”. Ignore any attributes. Your task is to find out all the tags present in the given document.
Continue reading

String Similarity: Hackerrank

Problem link: https://www.hackerrank.com/challenges/string-similarity

Problem Statement:
For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings “abc” and “abd” is 2, while the similarity of strings “aaa” and “aaab” is 3.

Calculate the sum of similarities of a string S with each of it’s suffixes.
Continue reading