SuffixDecomposition

SRM 786 · 2020-05-14 · by jeel_vaishnav

SRM 786 · 2020-05-14 · by jeel_vaishnav · Simple Search, Iteration

Show categories

Class Name: SuffixDecomposition

Return Type: long

Method Name: findTotalFun

Arg Types: (vector<int>, int, int, int, int, int, int, int)

Problem Statement

An array A is considered to be smaller than an array B (denoted A < B) if each element of A is strictly smaller than all the elements of B.

An array A can be decomposed into subarrays A1, A2, ... Ak, if and only if A = A1 + A2 + ... + Ak and A1 < A2 < â¦. < Ak. In words, the original array is the concatenation of the pieces (without any reordering) and each piece is smaller than the next one.

Let's define fun value f(A) of an array A as : f(A) = maximum number of subarrays that the array A can be decomposed into. Given an array S of length N, you need to find the sum of f(B), where B are all the possible suffixes of the given array S. In other words, given an array S, you need to find f(S[0..n - 1]) + f(S[1..n - 1]) + â¦.. f(S[n - 1..n - 1]).

You are given integers A0, X, Y, B0, X1, Y1, N and an integer array P. Use the pseudocode below to generate the array S.

A[0] = A0 for i = 1 to N-1: 	A[i] = (A[i-1] * X + Y) modulo 1812447359 B[0] = B0 for i = 1 to N-1: 	B[i] = (B[i-1] * X1 + Y1) modulo 1812447359 S = P for i = size(P) to N-1: 	S[i] = max(A[i], B[i])

Constraints

The length of P will be between 0 and min(N, 100) (inclusive)
Integers in P will be between 0 and 1812447358 (inclusive)
A0 will be between 0 and 1812447358 (inclusive)
X will be between 0 and 1812447358 (inclusive)
Y will be between 0 and 1812447358 (inclusive)
B0 will be between 0 and 1812447358 (inclusive)
X1 will be between 0 and 1812447358 (inclusive)
Y1 will be between 0 and 1812447358 (inclusive)
N will be between 1 and 200,000 (inclusive)

Examples

{269541138, 98269875, 874364850, 444294777, 1305936847}
429690734
1528829418
856109577
116991038
1418621477
1472004046
5
Returns: 11

{366621809, 545062264, 1717232926, 534281820, 439706831}
291597053
598582527
632932187
936473845
386078111
1004224793
5
Returns: 6

{1621829699, 1338326396, 1037489523, 884519293, 1737267364}
1056606954
1182554919
269154033
66539945
971006514
61831918
5
Returns: 9

{617222038, 1273657117, 492594082, 1313363955, 929067885}
1032982318
173134962
1265899626
1157465723
875277366
1273142720
5
Returns: 6

{708979257, 1041005359, 182628611, 344043397, 197964909}
441157809
826749135
1338326073
751891166
540434133
946574109
5
Returns: 6

100)

{3, 9, 5}
0
0
0
0
0
0
3
Returns: 4

Here, there are three possible suffixes {5}, {9, 5}, {3, 9, 5}. Now, f({5}) = 1, f({9,5}) = 1 (as it cannot be decomposed into more than one subarrays), f({3, 9, 5}) = 2 (the two-subarray decomposition will be {3}, {9, 5}). Hence, the total fun value is 1 + 1 + 2 = 4.

101)

{10}
1
2
2
3
1
2
4
Returns: 8

Here, the array is {10, 5, 10, 22}. There are four possible suffixes : {22}, {10, 22}, {5, 10, 22}, {10, 5, 10, 22}. f({22}) = 1, f({10, 22}) = 2, f({5, 10, 22}) = 3, f({10, 5, 10, 22}) = 2. Hence, total fun = 1 + 2 + 3 + 2 = 8.

102)

Here, the array is {5000001, 1344505193, 919789863, 999879289}. f({5000001, 1344505193, 919789863, 999879289}) = 2, f({1344505193, 919789863, 999879289}) = 1, f({919789863, 999879289}) = 2, f({999879289}) = 1. Hence, total fun value = 2 + 1 + 2 + 1 = 6.

Submissions are judged against all 118 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SuffixDecomposition with a public method long long findTotalFun(vector<int> P, int A0, int X, int Y, int B0, int X1, int Y1, int N) · 118 test cases · 2 s / 256 MB per case