ICPC India 2021 Preliminary Online Round [Discussion]

ICPC India 2021 Preliminary Online Round [Discussion]

2 days ago, # | How to solve LEXRIS? I tried with trie and segment tree but that didn't work.

• 2 days ago, # ^ | ← Rev. 2 →   +6 I solved it with Polynomial Hashing with DP Segment Tree.

  • 2 days ago, # ^ | If anyone wants the implementation then here you go :)

• 2 days ago, # ^ | ← Rev. 8 →   +5 First calculate the lexicographic order of substrings. Now dp[i][j] = best possible result if (i,j) is your first substring. You will need to maintain suffix maximums to query over only substrings lexicographically larger than first string

  • 2 days ago, # ^ | calculate the lexicographic order of substrings. Is there a way to do this quickly? During the contest we felt that sorting all substrings naively would TLE.

    • 2 days ago, # ^ | No that won't give TLE since it is N^3

      • 2 days ago, # ^ | I thought that sorting of every substring using std::sort would take O(N3log(N2))O(N3log⁡(N2)) time in the worst case. Isn't that true ?

        • 2 days ago, # ^ | log(n2)=2lognlog(n2)=2logn so it is O(n3logn)O(n3logn) in worst case which is fine

• 2 days ago, # ^ | ← Rev. 2 →   0 It's easy, dp[i][j]=max score if s[i..j] is your last substring. Now the transition is dp[i][j]=score[j-i+1]+max(dp[k][l]) where l<i and s[k..l]<s[i..j]. Now notice that you can easily check this using LCP and Suffix Array. Then it's just some case handling depending on whether the LCP is s[k..l], s[i..j], or both, or neither. Notice that you can maintain prefix max for each row of the DP to quickly get the answer. Then you can take max over all (and 0, of course). Submission (uncommented) Spoiler

• 2 days ago, # ^ | Sorting (Lexicographically), then calculated all substring which are same because we cannot select substring with same values we need to select strictly increasing in lexicographic order. Used Fenwick tree to find prefix maximum score. Now to select each substring (l , r). We need to find the a substring which ends before l (Non overlapping) and is Lexicographically smaller which was maintained by sorting already. So i used fenwick tree to find maximum score till [0 , l-1] and updated current score at r because no substring starting before r can be selected with current subrting. This update also makes a maximum update from (r , n). Please view code for better understanding. Code for reference Click Here

• 2 days ago, # ^ | ← Rev. 3 →   +17 Idea PS Solution Also what would be the CF rating for this problem ?. My guess is 2100+ . Regret

• 47 hours ago, # ^ | ← Rev. 4 →   +14 This is what we did(without any Complicated data structures): Define dp[i][j] as the maximum score for the suffix [i..n] such that the first substring starts at index i and has a length j. Now, step 1 is to precompute longest_common_prefix[i][j] as the length of the longest common prefix of substrings starting at i and j respectively for all i,j. This can be done naively in O(n^3) time. Now, coming to the transitions, to calculate dp[i][j], we will iterate for k, that is, the starting point of the next substring. Now if lcp[i][k] is 'L' and s[k+L] > s[i] OR if L>=j, then we can say that dp[i][j] = max (dp[k][L+1] + a[j], dp[k][L+2] + a[j]....). This can be done quickly by maintaining suffix maximums.

• 35 hours ago, # ^ | ← Rev. 3 →   +9 There is no need for seg tree or fenwick tree. Just sort all the substrings in increasing order. Consider a substring [i,j][i,j] as an interval (i,j)(i,j). Every interval has some priority (which is of course, determined by its position in sorted order). Now imagine placing intervals in increasing order of their priority (i.e from smallest lexographical order to largest). Suppose you're at the ithith substring. Let l(i)l(i) and r(i)r(i) denote the left and right endpoint of the substring. Define dp[r(i)]dp[r(i)] as the maximum score you can get if you place the ithith substring at the last operation, so, dp[r(i)]=max(dp[j]+cost[r(i)−l(i)+1])dp[r(i)]=max(dp[j]+cost[r(i)−l(i)+1]) for all jj such that j<l(i)j<l(i). This is because at last I'm placing the substring [l(i),r(i)][l(i),r(i)], so before that I must have placed a substring [l(j),r(j)][l(j),r(j)] such that r(j)<l(i)r(j)<l(i) (substrings must be non overlapping), and since I'm placing substring in increasing order, its guaranteed that jthjth string will be smaller than ithith string (there's a small catch here but you can easily fix it ;) ). Since there are O(n2)O(n2) substrings and for every substring I will iterate through all jj's, there are only O(n)O(n) right endpoints, so it would take O(n3)O(n3) time. Note that you can sort all substrings using trie, so that would also take O(n3)O(n3) time :)

  • 19 hours ago, # ^ | Very neat and simple solution, thanks for sharing. Can we extend this and use Suffix Array/Segment tree to solve in O(N2)O(N2)?

    • 19 hours ago, # ^ | Looks difficult, sorting is also the bottleneck. You can optimize dp transitions using seg tree, but I don't see how can we do sorting in O(n2)O(n2) using suffix tree. (I don't know much about suffix array)

      • 18 hours ago, # ^ | ← Rev. 4 →   +5 We can do the sorting in O(n2logn)O(n2log⁡n) by precalculating lcp in O(n2)O(n2) for all pair of suffix of the string starting at i,ji,j.

        • 15 hours ago, # ^ | Nice !

  • 9 hours ago, # ^ | Hey, thanks a lot for the simple solution as well as for the well written explanation. I found it the most intuitive compared to the others. Code for reference

• 24 hours ago, # ^ | When will the final result come?