Sorry for the very very long interruption between the daily dose.I will be regular from now.
The following is the day 7 question.
You are given a list of numbers and you will have a continuous flow of numbers coming in the list.
For every new number you need to tell that whether that number could be made using the numbers previously available in the list.
The first line contains number m (1 ≤ m ≤ 2000), showing how many numbers are there goo be in the list.
The next m lines contain the numbers in the order in which the numbers are being put in the list. Each number is a positive integer strictly less than 10600 that doesn’t contain leading zeroes.
For each number either print a 0 on the corresponding line, if the number cannot be represented as a XOR sum of numbers that are in the list, or print integer k showing how many numbers are in the representation and the indexes of these numbers. Separate the numbers by spaces. Each number can occur in the representation at most once.
Assume that the list was initially empty.
3 0 1 2
2 1 2
2 0 2
2 0 1
Comment any ideas or your way of approach to the question.
Due to the small restrictions, the problem could be solved with the straightforward O(n*m*(n+m)) algo of finding for each symbol whether there is other such symbol in the corresponding row or column. More fast approach is to count for each symbol how many times it appears in any row/column, and do corresponding checks in O(1) instead.
I am attaching my solution link below :
Given a n*m grid of characters you have to perform following operations:
1.Cross out the common letters in a particular row.
2.Cross out the common letters in a particular column.
Now make a string according to the following rule:
1.The letters that occupy a higher position follow before the letters that occupy a lower position.
2.If the letters are located in one row, then the letter to the left goes first.
The resulting string is the answer.
The first line contains two integers n and m (1 ≤ n, m ≤ 100). Next n lines contain m lowercase letters each.
Print the encrypted word on a single line. It is guaranteed that the answer consists of at least one letter.
You will surely appreciate the simplicity of the problem once you get the solution.
Let’s draw a straight line between the two centers.
Clearly to move the center with maximum distance we need to rotate it around the intersection of the line and the circle with 180 degrees. So the maximum distance we can move the center each time is 2 * R. Let’s continue moving the center with 2 * R distance each time until the two circles intersects. Now obviously we can make the center moves into its final position by rotating it around one of the intersection points of the two circles until it reaches the final destination.
Every time we make the circle moves 2 * R times except the last move it’ll be ≤ 2 * R. Assume that the initial distance between the two points is d So the solution to the problem will be
You can have a look at my code below:
In order to calculate the minimum possible lifted weight, we should find the initial stack first. Let’s find the positions one by one.
- First, let’s decide the position of book b1. After day 1, book b1 will be on the top of the stack, regardless of the order of the initial stack. Therefore, in order to minimize the lifted weight during day 1, book b1 must be on the top of the initial stack. (so actually, in day 1, you won’t lift any book)
- Next, let’s decide the position of book b2. (assume that b1 ≠ b2 for simplicity) Currently, b1 is on the top of the stack, and it cannot be changed because of the procedure. Therefore, in order to minimize the lifted weight during day 2, book b2 must be immediately below book b1.
Considering this, we can find the optimal strategy to create the initial stack: Scan b1, b2, …, bm step by step. Let’s assume that I am handling bi now. If bi has appeared before (formally, if ), erase bi from the sequence. Otherwise, leave bi. The resulting sequence will be the optimal stack.
You should note that it is not necessary for you to read all the books during 2015, which means the size of the resulting sequence may be smaller than n. The books which doesn’t appear in the resulting sequence must be in the bottom of the initial stack (obviously). However, this problem doesn’t require us to print the initial stack, so it turned out not to be important.
In conclusion, finding the initial stack takes O(n + m) time.
After finding the initial stack, we can simulate the procedure given in the statement naively. It will take O(nm) time.
- Time: O(nm)
- Memory: O(n + m)
You could also check out my solution at :