PuzzlersWorld.com

Java

Consonants Solution: Google codejam 2013 Round 1C

by Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Online Round 1C 2013, top 1000 from this round will be eligible for next online round.

Problem Statement

In English, there are 26 letters that are either vowels or consonants. In this problem, we consider a, e, i, o, and u to be vowels, and the other 21 letters to be consonants.

A tribe living in the Greatest Colorful Jungle has a tradition of naming their members using English letters. But it is not easy to come up with a good name for a new member because it reflects the member’s social status within the tribe. It is believed that the less common the name he or she is given, the more socially privileged he or she is.

The leader of the tribe is a professional linguist. He notices that hard-to-pronounce names are uncommon, and the reason is that they have too many consecutive consonants. Therefore, he announces that the social status of a member in the tribe is determined by its n-value, which is the number of substrings with at least n consecutive consonants in the name. For example, when n = 3, the name “quartz” has the n-value of 4 because the substrings quartz, uartz, artz, and rtz have at least 3 consecutive consonants each. A greater n-value means a greater social status in the tribe. Two substrings are considered different if they begin or end at a different point (even if they consist of the same letters), for instance “tsetse” contains 11 substrings with two consecutive consonants, even though some of them (like “tsetse” and “tsetse“) contain the same letters.
[Read more…]

Falling Diamonds Solution: Google codejam 2013 Round 1B

by Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the second problem from Online Round 1B 2013, top 1000 from this round will be eligible for next online round.

Problem Statement

Diamonds are falling from the sky. People are now buying up locations where the diamonds can land, just to own a diamond if one does land there. You have been offered one such place, and want to know whether it is a good deal.

Diamonds are shaped like, you guessed it, diamonds: they are squares with vertices (X-1, Y), (X, Y+1), (X+1, Y) and (X, Y-1) for some X, Y which we call the center of the diamond. All the diamonds are always in the X-Y plane. X is the horizontal direction, Y is the vertical direction. The ground is at Y=0, and positive Y coordinates are above the ground.

The diamonds fall one at a time along the Y axis. This means that they start at (0, Y) with Y very large, and fall vertically down, until they hit either the ground or another diamond.

When a diamond hits the ground, it falls until it is buried into the ground up to its center, and then stops moving. This effectively means that all diamonds stop falling or sliding if their center reaches Y=0.

When a diamond hits another diamond, vertex to vertex, it can start sliding down, without turning, in one of the two possible directions: down and left, or down and right. If there is no diamond immediately blocking either of the sides, it slides left or right with equal probability. If there is a diamond blocking one of the sides, the falling diamond will slide to the other side until it is blocked by another diamond, or becomes buried in the ground. If there are diamonds blocking the paths to the left and to the right, the diamond just stops.

falling diamonds problem google codejam round 1b 2013

falling diamonds problem google codejam round 1b 2013

Consider the example in the picture. The first diamond hits the ground and stops when halfway buried, with its center at (0, 0). The second diamond may slide either to the left or to the right with equal probability. Here, it happened to go left. It stops buried in the ground next to the first diamond, at (-2, 0). The third diamond will also hit the first one. Then it will either randomly slide to the right and stop in the ground, or slide to the left, and stop between and above the two already-placed diamonds. It again happened to go left, so it stopped at (-1, 1). The fourth diamond has no choice: it will slide right, and stop in the ground at (2, 0).
[Read more…]

Osmos Solution: Google codejam 2013 Round 1B

by Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Online Round 1B 2013, top 1000 from this round will be eligible for next online round.

Problem Statement

Armin is playing Osmos, a physics-based puzzle game developed by Hemisphere Games. In this game, he plays a “mote”, moving around and absorbing smaller motes.

A “mote” in English is a small particle. In this game, it’s a thing that absorbs (or is absorbed by) other things! The game in this problem has a similar idea to Osmos, but does not assume you have played the game.

When Armin’s mote absorbs a smaller mote, his mote becomes bigger by the smaller mote’s size. Now that it’s bigger, it might be able to absorb even more motes. For example: suppose Armin’s mote has size 10, and there are other motes of sizes 9, 13 and 19. At the start, Armin’s mote can only absorb the mote of size 9. When it absorbs that, it will have size 19. Then it can only absorb the mote of size 13. When it absorbs that, it’ll have size 32. Now Armin’s mote can absorb the last mote.

Note that Armin’s mote can absorb another mote if and only if the other mote is smaller. If the other mote is the same size as his, his mote can’t absorb it.

You are responsible for the program that creates motes for Armin to absorb. The program has already created some motes, of various sizes, and has created Armin’s mote. Unfortunately, given his mote’s size and the list of other motes, it’s possible that there’s no way for Armin’s mote to absorb them all.

You want to fix that. There are two kinds of operations you can perform, in any order, any number of times: you can add a mote of any positive integer size to the game, or you can remove any one of the existing motes. What is the minimum number of times you can perform those operations in order to make it possible for Armin’s mote to absorb every other mote?

For example, suppose Armin’s mote is of size 10 and the other motes are of sizes [9, 20, 25, 100]. This game isn’t currently solvable, but by adding a mote of size 3 and removing the mote of size 100, you can make it solvable in only 2 operations. The answer here is 2.
[Read more…]

Manage Your Energey Solution: Google codejam 2013 Round 1A

by Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Online Round 1A 2013, top 1000 from this round will be eligible for next online round.

Problem Statement

You’ve got a very busy calendar today, full of important stuff to do. You worked hard to prepare and make sure all the activities don’t overlap. Now it’s morning, and you’re worried that despite all of your enthusiasm, you won’t have the energy to do all of this with full engagement.

You will have to manage your energy carefully. You start the day full of energy – E joulesof energy, to be precise. You know you can’t go below zero joules, or you will drop from exhaustion. You can spend any non-negative, integer number of joules on each activity (you can spend zero, if you feel lazy), and after each activity you will regain R joules of energy. No matter how lazy you are, however, you cannot have more than E joules of energy at any time; any extra energy you would regain past that point is wasted.

Now, some things (like solving Code Jam problems) are more important than others. For the ith activity, you have a value vi that expresses how important this activity is to you. The gain you get from each activity is the value of the activity, multiplied by the amount of energy you spent on the activity (in joules). You want to manage your energy so that your total gain will be as large as possible.

Note that you cannot reorder the activities in your calendar. You just have to manage your energy as well as you can with the calendar you have.
[Read more…]

Bullseye Solution: Google codejam 2013 Round 1A

by 4 Comments

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Online Round 1A 2013, top 1000 from this round will be eligible for next online round.

Problem

Maria has been hired by the Ghastly Chemicals Junkies (GCJ) company to help them manufacture bullseyes. A bullseye consists of a number of concentric rings (rings that are centered at the same point), and it usually represents an archery target. GCJ is interested in manufacturing black-and-white bullseyes.

Maria starts with t millilitres of black paint, which she will use to draw rings of thickness 1cm (one centimetre). A ring of thickness 1cm is the space between two concentric circles whose radii differ by 1cm.

Maria draws the first black ring around a white circle of radius r cm. Then she repeats the following process for as long as she has enough paint to do so:

  1. Maria imagines a white ring of thickness 1cm around the last black ring.
  2. Then she draws a new black ring of thickness 1cm around that white ring.

Note that each “white ring” is simply the space between two black rings.

The area of a disk with radius 1cm is π cm2. One millilitre of paint is required to cover area π cm2. What is the maximum number of black rings that Maria can draw? Please note that:

  • Maria only draws complete rings. If the remaining paint is not enough to draw a complete black ring, she stops painting immediately.
  • There will always be enough paint to draw at least one black ring.

[Read more…]

Fair and Square Solution: Google codejam 2013 Qual Round

by Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the third problem from Qualification Round 2013.

Problem Statement

Little John likes palindromes, and thinks them to be fair (which is a fancy word for nice). Apalindrome is just an integer that reads the same backwards and forwards – so 6, 11 and 121 are all palindromes, while 10, 12, 223 and 2244 are not (even though 010=10, we don’t consider leading zeroes when determining whether a number is a palindrome).

He recently became interested in squares as well, and formed the definition of a fair and square number – it is a number that is a palindrome and the square of a palindrome at the same time. For instance, 1, 9 and 121 are fair and square (being palindromes and squares, respectively, of 1, 3 and 11), while 16, 22 and 676 are not fair and square: 16 is not a palindrome, 22 is not a square, and while 676 is a palindrome and a square number, it is the square of 26, which is not a palindrome.

Now he wants to search for bigger fair and square numbers. Your task is, given an interval Little John is searching through, to tell him how many fair and square numbers are there in the interval, so he knows when he has found them all.
[Read more…]

Lawnmower Solution: Google codejam 2013 Qual Round

by Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the second problem from Qualification Round 2013.

Problem

Alice and Bob have a lawn in front of their house, shaped like an N metre by M metre rectangle. Each year, they try to cut the lawn in some interesting pattern. They used to do their cutting with shears, which was very time-consuming; but now they have a new automatic lawnmower with multiple settings, and they want to try it out.

The new lawnmower has a height setting – you can set it to any height h between 1 and 100 millimetres, and it will cut all the grass higher than h it encounters to height h. You run it by entering the lawn at any part of the edge of the lawn; then the lawnmower goes in a straight line, perpendicular to the edge of the lawn it entered, cutting grass in a swath 1m wide, until it exits the lawn on the other side. The lawnmower’s height can be set only when it is not on the lawn.

Alice and Bob have a number of various patterns of grass that they could have on their lawn. For each of those, they want to know whether it’s possible to cut the grass into this pattern with their new lawnmower. Each pattern is described by specifying the height of the grass on each 1m x 1m square of the lawn.

The grass is initially 100mm high on the whole lawn.
[Read more…]

Tic-Tac-Toe-Tomek Solution: Google codejam 2013 Qual Round

by Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Qualification Round 2013.

Problem Statement

Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single ‘T’ symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X’s symbol is ‘X’, and player O’s symbol is ‘O’.

After a player’s move, if there is a row, column or a diagonal containing 4 of that player’s symbols, or containing 3 of her symbols and the ‘T’ symbol, she wins and the game ends. Otherwise the game continues with the other player’s move. If all of the fields are filled with symbols and nobody won, the game ends in a draw. See the sample input for examples of various winning positions.

Given a 4 x 4 board description containing ‘X’, ‘O’, ‘T’ and ‘.’ characters (where ‘.’ represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:

  • “X won” (the game is over, and X won)
  • “O won” (the game is over, and O won)
  • “Draw” (the game is over, and it ended in a draw)
  • “Game has not completed” (the game is not over yet)

If there are empty cells, and the game is not over, you should output “Game has not completed”, even if the outcome of the game is inevitable.
[Read more…]

Permutations solution: Facebook hacker cup 2013 Round 2

by Leave a Comment

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the third question(Carried 45 marks out of 100) for the Round 2 of 2013 hacker cup. only top 100 contestants will be moved to Round 3.

Problem Statement

In this problem you need to count number of possible permutations p of the first N integers, given N-1 constraints of the form pi < pj.

Input

The first line contains an integer T, T ≤ 20, followed by T test cases. Each test case begins with an integer N, N ≤ 1000, which is the number of integers in the permutation. The next N – 1 lines each contain a single constraint in the following format: “i sign j“, where 0 ≤ i, j ≤ N – 1 and sign is either “<” or “>“, which denotes whether the i-th element of the permutation should be less than or greater than the j-th element.

It is guaranteed that it is not possible to partition indices into two disjoint sets A and B such that there is no constraint involving elements from both A and B.
[Read more…]

Social

privacy policy