Kotlin Heroes: Episode 6 — Editorial
source link: http://codeforces.com/blog/entry/88522
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
First of all, I would like to thank all testers of the round: Um_nik, IlyaLos, Roms, nuipojaluista, Supermagzzz, Stepavly, hg333. Also huge thanks to co-authors of the contest: Neon, adedalic, vovuh and awoo.
I hope you enjoyed participating in the round!
Okay, now for the editorial itself:
Idea: BledDest, preparation: Neon
Idea: BledDest, preparation: BledDest
Idea: vovuh, preparation: vovuh
Idea: vovuh, preparation: awoo
Idea: BledDest, preparation: awoo
Idea: BledDest and Neon, preparation: Neon
Idea: BledDest, preparation: awoo
Idea: BledDest, preparation: BledDest
Idea: BledDest, preparation: Neon and adedalic
Tutorial of Kotlin Heroes: Episode 6
|
The solution codes will be uploaded shortly. UPD: here they are. |
|
Problem E seems to be well-known after you realize that it's the LCS of and its reverse, and the number of matches between the two strings is in . If the problem is strengthened to having at most occurrences of each integer, the problem can be solved in time. |
-
can you tell name of algo or provide some link for "how to find no of match between two strings in O(n)"
-
To find the number of elements in string that match with a given element of string , simply do this:
Construct the frequency array/map of , and then for each element in , simply read off the number of elements in that match with it.
However, this was not what I meant by the comment above. I meant that if is the reverse of , the number of matches between and (defined as the sum of the elements found in the above algorithm) is upper bounded by some constant multiple of , and if the maximum frequency of an element of is , then an explicit upper bound is .
In general, if there are at most matches between two strings, you can figure out an algorithm to find the LCS in .
-
|
1488C - Двое полицейских can be solved in time via binary search. In an optimal solution, the left policeman (at ) will visit while the right policeman (at ) will visit . With this in our mind, we can binary search for the total time. The lower bound is since the left policeman needs to cover , while the right policeman needs to cover . And the upper bound is since in any case, they would need no more than minutes to finish. Now for a given time , we can find the largest position that the left policeman can cover, and the smallest position that the right policeman can cover. Then if it is possible to cover all positions within time. Otherwise, we cannot cover. Code: 109510140 |
|
19 months ago, # | A screencast with video solutions if you're into those... and also the first one with a facecam |
|
19 months ago, # | For J: you can remove the term because the polynomials we care about are all geometric sums, so you can take the Fourier transform in time by precomputing powers of the root of unity. |
|
In problem E, For even length palindromic subsequences, how can the answer be found from longest decreasing subsequence of second occurrences. If a = [4,3,2,1,1,2,3,4] Then the answer should be 8 but finding longest decreasing subsequence of second occurrences will not provide that answer. |
|
22 minutes ago, # | can anyone explain problem A's solution please |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK