Codeforces round #396 editorial

Правка en6, от mohammedehab2002, 2017-02-07 03:06:58

[problem:A] If the strings are the same, Any subsequence of a is indeed a subsequence of b so the answer is "-1", otherwise the longer string can't be a subsequence of the other (if they are equal in length and aren't the same, No one can be a subsequence of the other) so the answer is maximum of their sizes.

Time complexity : O(|a| + |b|).

Problem author : me.

Solution author : me.

Testers : me and mahmoudbadawy.

[problem:B]

First solution:-

Let x, y and z be the lengths of 3 line segments such that x ≤ y ≤ z, If they can't form a non=degenerate triangle, Line segments of lengths x - 1, y and z or x, y and z + 1 can't form a triangle, So we don't need to try all the combinations, If we try y as the middle one, We need to try the maximum x that is less than or equal to y and the minimum z that is greater than y, The easiest way to do so is to sort the line segments and try every consecutive 3.

Time complexity : O(nlog(n)).

Second solution:-

Depending on the note from the first solution, If we try to generate a sequence such that after sorting every consecutive 3 line segments will form a degenerate triangle, It will be 1 1 2 3 5 8 13 ... which is Fibonacci sequence, Fibonacci is a fast growing sequence, fib(45) = 1134903170, Notice that Fibonacci makes maximum n with "NO" as the answer, That means the answer is indeed "YES" for n ≥ 45, For n < 45, You can do the naive O(n3) solution or the first solution.

let x be the number that satisfies these inequalities:-

fib(x) ≤ maxAi.

fib(x + 1) > maxAi.

Time complexity : O(x3) or O(xlog(x)).

Problem author : me.

Solutions author : me.

Tester : me and mahmoudbadawy.

[problem:C]

Let dp[i] be the number of ways to split the prefix of s ending at index i into substrings that fulfills the conditions. Let it be 0-indexed. Our base case is dp[0] = 1. Our answer is dp[n - 1]. Now let's calculate it for every i. Let l be the minimum possible index such that the substring from l to i satisfies the condition, Let x be a moving pointer, At the beginning x = i - 1, every time we move x we calculate new l depending on the current character like that l = max(l, i - as[x]). While x is greater than or equal to l we add dp[x] to dp[i], To find the longest substring find maximum i - l, To find the minimum number of substrings, there is an easy greedy solution, Find the longest valid prefix and delete it and do the same again until the string is empty, The number of times this operation is repeated is our answer.

Time complexity : O(n2).

Try to find O(n) solution(I'll post a hard version of some problems on this blog soon).

Problem authors : me and mahmoudbadawy.

Solution author : me.

Testers : me and mahmoudbadawy.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en24 Английский mohammedehab2002 2017-02-07 22:52:00 0 (published)
en23 Английский mohammedehab2002 2017-02-07 22:50:50 44
en22 Английский mohammedehab2002 2017-02-07 22:44:01 153
en21 Английский mohammedehab2002 2017-02-07 19:09:17 64
en20 Английский mohammedehab2002 2017-02-07 19:01:28 3
en19 Английский mohammedehab2002 2017-02-07 18:56:55 1053
en18 Английский mohammedehab2002 2017-02-07 18:40:41 139
en17 Английский mohammedehab2002 2017-02-07 18:05:35 108
en16 Английский mohammedehab2002 2017-02-07 17:43:14 499
en15 Английский mohammedehab2002 2017-02-07 16:58:30 3 Tiny change: 'y to find $O(n)$ so' -> 'y to find an $O(n)$ so'
en14 Английский mohammedehab2002 2017-02-07 16:56:23 61
en13 Английский mohammedehab2002 2017-02-07 16:47:14 11
en12 Английский mohammedehab2002 2017-02-07 16:37:58 52
en11 Английский mohammedehab2002 2017-02-07 16:23:20 21
en10 Английский mohammedehab2002 2017-02-07 16:18:49 8
en9 Английский mohammedehab2002 2017-02-07 16:05:25 52
en8 Английский mohammedehab2002 2017-02-07 15:31:04 2931
en7 Английский mohammedehab2002 2017-02-07 03:21:31 36 Tiny change: 'uthor : me.\n\nTeste' -> 'uthor : me and [user:mahmoudbadawy].\n\nTeste'
en6 Английский mohammedehab2002 2017-02-07 03:06:58 2 Tiny change: 'l=max(l,i-{a_s[x]})$. W' -> 'l=max(l,i-a_{s[x]})$. W'
en5 Английский mohammedehab2002 2017-02-07 03:05:28 2 Tiny change: 'l=max(l,i-a_s[x])$. While ' -> 'l=max(l,i-{a_s[x]})$. While '
en4 Английский mohammedehab2002 2017-02-07 03:04:46 1 Tiny change: ',i-a_s[x]). While $x' -> ',i-a_s[x])$. While $x'
en3 Английский mohammedehab2002 2017-02-07 03:03:41 54
en2 Английский mohammedehab2002 2017-02-07 03:00:50 87
en1 Английский mohammedehab2002 2017-02-07 02:52:07 2956 Initial revision (saved to drafts)