PuzzlersWorld.com

All Puzzles Solved Unsolved

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…]

Find a pythagorean triplet from an array

by 1 Comment

Problem Statement:
Given an array a of n integers find all possible Pythagorean triplets from the array.

What is Pythagorean triplet?

A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. this formula is derived from Pythagoras theorem: “For every right angle triangle with side lengths a, b, and c=> a2 + b2 = c2“.

Pythagorean Triplet

Pythagorean Triplet

Solution:
[Read more…]

3 SUM problem

by Leave a Comment

Problem Statement:
Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.

Solution:
Brute force approach is of O(n^4) but we can solve it in O(n^2) by using the approach in Non duplicate pairs that sum to S.

First sort the array(Order O(nlogn)), than finding a, b, c pairs is equal to finding=> For every element a in the array, if there exists a pair with sum equal to -a. As explained in Non duplicate pairs that sum to S, we can get the pair with sum -a in O(n) and we have to repeat this exercise n times so order of complexity will be O(n^2).

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…]

RoboElection solution: Facebook hacker cup 2013 Round 2

by 1 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 second question(Carried 35 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 the not so distant future the world is populated by robots and ruled by an evil robot emperor. Every robot in the world can be identified by a unique numeric ID, and the list of all the existing robot IDs is easily accessible to everyone. One day the emperor decided to call for a general election to preserve an illusion of democracy. He set it up in the following way:

  • – Every robot can cast at most one vote per round of voting and the votes are anonymous.
  • – The only option on the ballot is the vote for reelection of the emperor.
  • – If at least P percent of the population cast votes for the emperor he becomes reelected for the next millennium.
  • – Otherwise the emperor declares the vote void, disassembles K robots with the lowest ID numbers (who he finds to be the most rebellious), and then if there are any functional robots left he restarts the whole process.

All the robots are perfectly logical but also rather lazy and prone to procrastination. That’s why after figuring out the plan of the emperor, they will abstain from voting unless they have to vote to survive the election (including this round and all later rounds). If they will die whether or not they vote, they will vote in the hope that the emperor will spare them. (He won’t, because he’s evil!).

Problem

Given N – the initial population size, K – the number of robots disassembled after an unsuccessful vote and P – the required percentage of votes.

Compute the number of times the vote will take place.
[Read more…]

Cake Cutting 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 first question(Carried 20 marks out of 100) for the Round 2 of 2013 hacker cup.

Problem Statement

“Happy birthday to you… Happy birthday to you… Happy birthday to Grovyle… Happy birthday to you…”

Today is Grovyle’s birthday and he is going to invite his friends to his birthday party. To have an awesome party, each of the attendants should get one piece of cake. Your job is to help Grovyle invite as many friends as you can.

However, Grovyle’s parents are very mean, and make him use the following rules when cutting his cake:

  • There is only ONE cylindrical cake.
  • Grovyle cuts the cake N times, each cut being perpendicular to the surface of the cake.
  • The i-th cut is a broken line with a[i] vertices.
  • The knife is only allowed to intersect the edge of the cylindrical cake at the start and end of the cut.What is the maximum number of pieces Grovyle could get?
    [Read more…]

Dead Pixels solution: Facebook hacker cup 2013 Round 1

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 1 of 2013 hacker cup. only top 500 contestants will be moved to Round 2.

Problem Statement

John’s friend Peter purchases a new high resolution monitor with dimension W * H where W is the number of pixels in each row (i.e. width) and H is the number of pixels in each column (i.e. height).

However, there are N dead pixels on the monitor. The i-th dead pixel is located at (x[i], y[i]). (0, 0) is the top-left pixel and (W – 1, H – 1) is the bottom-right pixel. The locations of the dead pixels could be generated by 6 given integers X, Y, a, b, c and d by the following rules. If 2 pixels are at the same location, they are considered the same. It is possible that there are less than N distinct dead pixels.

  • x[0] = X
  • y[0] = Y
  • x[i] = (x[i – 1] * a + y[i – 1] * b + 1) % W (for 0 < i < N)
  • y[i] = (x[i – 1] * c + y[i – 1] * d + 1) % H (for 0 < i < N)

Peter connects his monitor to his computer and opens an image with dimension P (width) * Q (height). How many unique positions can the image be placed so that it can be displayed perfectly (i.e. all pixels of the picture are shown on the monitor)? The image cannot be rotated.
[Read more…]

Security problem solution: Facebook hacker cup 2013 Round 1

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 second question(Carried 35 marks out of 100) for the Round 1 of 2013 hacker cup. only top 500 contestants will be moved to Round 2.

Problem Statement

You are designing a new encryption system that works in the following way:

For server-client communication you need a key k, composed of m sections, each of length l, and the key consists only of lowercase characters in the set {a, b, c, d, e, f}. The server has a key k1 and the client has a key k2 where:

  • k1 = f(k). f is a function that receives a key and replace some random letters by ? indicating that those characters can be any lowercase letter of the set described before.
  • k2 = f(g(k)). g is a function that takes a key and produces a random permutation of its m sections. And f is the function defined above.

For example: let m = 3, l = 2

  • f(‘abacbc’) = ‘?ba??c’
  • g(‘abacbc’) = ‘acbcab’ (each section was moved one place to the left).

Your task is given k1 and k2, find key k. If there are several solutions, print the lexicographically smallest key. And if there is no solution at all, print “IMPOSSIBLE” (without the quotes).

Input description:

[Read more…]

Card Game solution: Facebook hacker cup 2013 Round1

by 1 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 first question(Carried 20 marks out of 100) for the Round 1 of 2013 hacker cup. only top 500 contestants will be moved to Round 2.

Problem Statement

John is playing a game with his friends. The game’s rules are as follows: There is deck of N cards from which each person is dealt a hand of K cards. Each card has an integer value representing its strength. A hand’s strength is determined by the value of the highest card in the hand. The person with the strongest hand wins the round. Bets are placed before each player reveals the strength of their hand.

John needs your help to decide when to bet. He decides he wants to bet when the strength of his hand is higher than the average hand strength. Hence John wants to calculate the average strength of ALL possible sets of hands. John is very good at division, but he needs your help in calculating the sum of the strengths of all possible hands.

Problem

You are given an array a with N ≤ 10 000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1 000 000 007.

Input

[Read more…]

Social

privacy policy