or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
![image alt](https:// "title") | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | Emoji list | ||
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
SRM 718 Editorials
Div II - Easy - RelativeHeights
In this problem you are given the heights of ‘n’ towers. You are required to choose n-1 of the towers and rank them according to their heights (ranks range between 0 to n-2). So, there would be C(n,n-1) choices. Of these you need to print out the choices that have unique rank ordering. To be more specific, if the rank orderings, for some example sequence, are as follows:
Of the above six possibilities, only 4 orderings look unique and the answer is thus 4.
You can follow a brute force method for this problem.
Pseudo Code:
My implementation is as follows:
Div II - Medium - InterleavingParenthesisDiv2
We will use dp to solve this problem. Now consider dp[i][j] as total ways of interleaving for first ‘i’ characters of string s1 & ‘j’ characters of string s2. Now it’s pretty easy to see that the last character of this string of length i + j will either be ith character of string s1 or jth character of string s2. Therefore the transitions of dp will be
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (check for i = 0 & j = 0)
That’s pretty much it. Just check few cases like in the end total ‘(‘ characters should match ‘)’ characters and any intermediate dp state should have more ‘(‘ characters than ‘)’ if not that dp value will correspond to zero.
Java Code :
Div II - Hard - ChainCity
The solution of this problem is binary search.
In each step of binary search, we will find how many transporters required if all buildings must be at most X/2 distances away from nearest transporter.
Note that X is a center value of binary search range.
If all buildings are at most X/2 distances away from nearest transporter, we can move from any building to another building at most X distances.
Because, start building to nearest transporter is at most X/2, and destination from nearest transporter is at most X/2.
So, total cost must be at most X.
If less than or equal to k transporters required, X is possible answer and update the binary search range.
If more than k transporters required, X is impossible answer and also update the search range.
To find how many transporters required, just build a transporter from left to right if current building is more than X/2 distances away from nearest transporter.
Example)
dist = {3, 5, 4}
k = 2
Buildings are at 0, 3, 8, 12
step 1) Range is [0, 12(= 3 + 5 + 4)], X = (0 + 12) / 2 = 6
Building at 0 is not covered because no transporter is built.
So, build transporter at 3(= 0 + 6 / 2) and the transporter is covers from 0 to 6.
We don't need to care about left buildings of current building. Because we build transporter from left to right.
So, build transporter at 3 is most efficient choice in this situation.
3 is covered because transporter is at 3
8 is not covered. So, build transporter at 11(= 8 + 6 / 2) and covers from 8 to 14.
11 is covered by transporter at 11.
Need 2 transporter to cover all buildings.
So, 6 is possible answer.
New range is [0, 6].
step 2) Range is [0, 6], X = 3
Build transporter at 1.5 and [0, 3] is covered.
Note that we can build transporter at anywhere.
3 is covered.
8 is not covered. So, build transporter at 9.5 and covers from 8 to 11
12 is not covered. build transporter at 13.5
Need 3 transporter to cover all buildings.
So, 3 is impossible answer.
New range is [4, 6]
step 3) Range is [4, 6], X = 4 ((int)4.5)
Build transporter at 2 and covers from 0 to 4
3 is covered
8 is not covered. build transporter at 10 and covers from 8 to 12
12 is covered
Need 2 transporter and 4 is possible answer.
new range is [4, 4]
4 is answer of this case.
Complexity:
D := distance between first building and last building
N := number of buildings
Time Complexity : O(NlogD)
- logD : cost of binary search
- N : cost to judge
Space Complexity : O(N)
- N : size of distances array
Div I - Easy - InterleavingParenthesis
This is a straightforward dynamic programming problem. We need to count the number of strings which satisfy the following two conditions:
Let dp[i][j] be of the number of ways to combine the first i characters of s1 and the first j characters of s2 into a string such that the second condition is satisfied. If there are more right parentheses than left parentheses among the first i characters of s1 and the first j characters of s2, then we set dp[i][j]=0, because the second condition will be violated. Otherwise, we set dp[i][j]=dp[i-1][j]+dp[i][j-1], taking mod 10^9+7 as necessary.
Finally, we must check if the first condition holds when we use all characters from both strings. If it does, the answer is dp[s1.length()][s2.length()]. Otherwise, the answer is 0.