hi_cf's blog

By hi_cf, 9 years ago, In English

Hi,I am looking for an online competitive programming coach , who can provide competitive programming lesson over skype/hangout. Those who are interested , please message me.

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

By hi_cf, 9 years ago, In English

Find all maximum sub-array in which all pairs have their sum >= k. I feel it can be solved using monotonic queue like this solution , but i am not able to think correct answer. Please give some hints.

e.g. Array :[ 1 5 2 3 6 5 4 2 2 8 ] and K = 8

then answer is [ 3 6 5 ] or [6 5 4 ] because any pair's sum is greater than or equal to 8

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By hi_cf, 11 years ago, In English

Given a 2D Boolean matrix consisting of 0s and 1s. Find the largest size rectangle having all four borders as 1. The interior of it may or may not be entirely filled with 1s . I can think of O(n^4) solution . How can we improve it ?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By hi_cf, 11 years ago, In English

Can anyone suggest a solution for question below ?

Mastermind is a game of two players. In the beginning, first player decides a secret key, which is a sequence (s1,s2,...sk) where 0 < si <= n, Then second player makes guesses in rounds, where each guess is of form (g1,g2, ...gk), and after each guess first player calculates the score for the guess. Score for a guess is equal to number of i's for which we have gi = si.

For example if the secret key is (4,2,5,3,1) and the guess is (1,2,3,7,1),then the score is 2, because g2 = s2 and g5 = s5.

Given a sequence of guesses, and scores for each guess, your program must decide if there exists at least one secret key that generates those exact scores.

Input

First line of input contains a single integer C (1 <=C <= 100). C test-cases follow. First line of each test-case contains three integers n,k and q. (1 <=n,k <=11, 1<=q<=8 ). Next q lines contain the guesses.

Each guess consists of k integers gi,1, gi,2,....gi,k separated by a single space, followed by the score for the guessbi (1 <= gi,j <=n for all 1 <=i <=q, 1 <=j <=k; and 0 <= bi <=k )

Output For each test-case, output "Yes" (without quotes), if there exists at least a secret key which generates those exact scores, otherwise output "No".

Sample Input 2
4 4 2
2 1 2 2 0
2 2 1 1 1
4 4 2
1 2 3 4 4
4 3 2 1 1

Sample Output Yes
No

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By hi_cf, 11 years ago, In English

ByteLand

Byteland consists of N cities numbered 1..N. There are M roads connecting some pairs of cities. There are two army divisions, A and B, which protect the kingdom. Each city is either protected by army division A or by army division B.

You are the ruler of an enemy kingdom and have devised a plan to destroy Byteland. Your plan is to destroy all the roads in Byteland disrupting all communication. If you attack any road, the armies from both the cities that the road connects comes for its defense. You realize that your attack will fail if there are soldiers from both armies A and B defending any road.

So you decide that before carrying out this plan, you will attack some of the cities and defeat the army located in the city to make your plan possible. However, this is considerably more difficult. You have estimated that defeating the army located in city i will take up ci amount of resources. Your aim now is to decide which cities to attack so that your cost is minimum and no road should be protected from both armies A and B.

Input:

The first line contains the number of test cases T. T test cases follow. The first line of each test case contains N and M. The next N lines describe the cities in Byteland. The ith line contains a letter 'A' or 'B' signifying the army division located in city i and the cost ci of defeating that army. The next M lines descibe the roads in the city. The ith line contains xi and yi, the numbers of the cities connected by a road.

Output:

Output T lines, one corresponding to each test case containing the cheapest cost of accomplishing your goal.

Constraints: 1<= T <= 10

1 < N <= 50

1 <= M <= 400

1 <= ci <= 100

Sample Input: 3

3 3

A 1

A 1

B 1

1 2

1 3

2 3

3 3

A 1

A 1

B 10

1 2

1 3

2 3

6 4

A 10

A 10

A 10

B 10

B 10

B 10

1 2

2 3

4 5

5 6

Sample Output:

1

2

0

Explanation:

In the first example, the city 3 should be attacked which costs 1 unit. In the second example, it is cheaper to attack cities 1 and 2 rather than attack city 3. In the third example, there is no road defended by both armies and so there is no need to attack any city.

Full text and comments »

  • Vote: I like it
  • -21
  • Vote: I do not like it

By hi_cf, 11 years ago, In English

The beauty of a number X is the number of 1s in the binary representation of X.

Two players are plaing a game. There is number n written on a black board. The game is played as following:

Each time a player chooses an integer number (0 <= k) so that 2^k is less than n and (n-2^k) has as beautiful as n. Next he removes n from blackboard and writes n-2^k instead. The player that can not continue the game (there is no such k that satisfies the constrains) looses the game.

The First player starts the game and they play in turns alternatively. Knowing that both two players play optimally you have to specify the winner.

Input:

First line of the Input contains an integer T, the number of testcase. 0 <= T <= 5.

Then follow T lines, each containing an integer n.

n more than 0 and less than 10^9 +1.

Output

For each testcase print "First Player" if first player can win the game and "Second Player" otherwise.

Sample Input

7

1

2

8

16

42

1000

123

Sample Output

Second Player

First Player

First Player

Second Player

Second Player

First Player

Second Player

Explanation

In the first example n is 1 and first player can't change it so the winner is the second player.

In the second example n is 2, so the first player subtracts 1 (2^0) from n and the second player looses the game.

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it