Noogler_from_Google's blog

By Noogler_from_Google, history, 3 years ago, In English

Yesterday I encountered this problem in a hiring contest.

Problem:

You are given the following:

  1. A tree T consisting of n nodes

  2. An integer x

  3. Each node has some value w[i] associated with it.

Task

Determine the number of simple paths in the tree, such that the bitwise xor of elements on the simple path is x.

Note: A simple path between node u and v is defined as a sequence of edges that connects node u and v and includes the occurrence of a node at most once.

Example

Assumptions

n = 3 w = [3,2,2] edges = [(1,2), (1,3)] x = 1 Approach

There exist two simple paths such that bitwise xor of elements on the path is x Two paths are from node 1 to node 2, 3 ^ 2 = 1 and node 1 to node 3, 3 ^ 2 = 1, where ^ is Bitwise Xor operator. Therefore, print 2.

Any approach?

Full text and comments »

By Noogler_from_Google, 3 years ago, In English

Given a directed graph we need to find a set of minimum vertices to be removed so that there will be no path from the given start node to the end node.

I tried to find the solution for this and I got to know that there is a solution with max-flow min-cut but I didn't get that. Or is there any other solution for this. By seeing the problem statement it looks pretty standard. Can anyone help me?

Full text and comments »

By Noogler_from_Google, history, 4 years ago, In English

Not able to think any solution in given Constraint. If anyone saw a similar question then please comment the link to that.

You are provided with a large string and one or more small strings. You need to find if the large string can be formed by combining all the small strings. You can interchange characters of small strings internally and you can combine small strings in any order. Print "YES" if it is possible, otherwise print "NO".

Note: All strings contain lower case alphabets only.

Constraints
1 <= length of large string <= 500000
1 <= length of small string <= 1000
1 <= N <= 500

Input
First line contains the large string
Second line contains an integer N denoting total number of small strings
Next N lines contain strings smaller than large string

Output
Print single line with YES or NO

Time Limit
1

Examples
Example 1

Input

dogisaloyalanimal
5
a
alloy
is
god
lamina

Output
YES

Explanation :

Large string is "dogisaloyalanimal". There are 5 small strings — "a", "alloy", "is", "god", "lamina". We can do following operations on small strings:
Interchange characters of "alloy" to form "loyal".
Interchange characters of "god" to form "dog".
Interchange characters of "lamina" to form "animal".
So, we formed new set of small strings — "a", "loyal", "is", "dog", "animal". Now combine small strings in the below order:
"dog" + "is" + "a" + "loyal" + "animal"
We got it combined as "dogisaloyalanimal". This is same as large string provided. So, the output is "YES".

Example 2

Input

thisisgood
4
god
is
so
hit

Output
NO

Explanation:

Large string is "thisisgood". There are 4 small strings — "god", "is", "so", "hit". We cannot form the large string by combining small strings even after interchanging its characters internally. So, the output is "NO".

Full text and comments »