How about +12 up votes?

Granted.... Oops -83

Hmm, I will just leave the link to one of my comments here.

UPD: posting such articles or links during the contest is unacceptable behavior anyway.

It is bad to post it during the round. But also it is not the same problem :)

I was thinking it could be solved by solving System Linear Equation with Gauss Jordan with modules. But I failed in the implementation...

I checked x=0,1,2,3,4,5,6,7,8,9,10. And then calculated all values using Lagrange interpolation.

A $$$N$$$ degree polynomial is uniquely determined by $$$N+1$$$ distinct evaluations. You can ask $$$P(0), P(1), \cdots, P(10)$$$ and then interpolate. Then you can find the root in $$$O(mod)$$$ by checking all numbers in $$$[0, mod - 1]$$$.

Just ask for $$$f(0), f(1), ..., f(49)$$$, pray there is some recurrence like $$$f(i) = \sum_{j} a_j \times f(i - j)$$$. and find it using Berlekamp-Massey. Then you can calculate all $$$f(i)$$$ for $$$0 \le i < MOD$$$. The existance is proved here.

I used little Bézout's theorem. For any $$$a$$$ we have $$$f(x) = g_1(x) \cdot (x - a) + f(a)$$$, where $$$g_1(x)$$$ is a polynomial with less degree. So if we know $$$f(x)$$$ and we have asked for $$$f(a)$$$ before we can calculate $$$g_1(x)$$$.

You can continue, say $$$g_1(x) = g_2(x) \cdot (x - b) + g_1(b)$$$, and so on, remembering the remainder on each step. After a few iterations (about $$$10$$$) $$$g_i$$$ will become a constant function.

If we know $$$g_{i + 1}(x)$$$ we can easily find $$$g_i(x)$$$. So, since we know that for big enough $$$i$$$: $$$g_i$$$ is constant, for any $$$x$$$ we can caluclate $$$f(x)$$$ by going backwards through these functions.

Now just iterate through all $$$0 \le x < 10^6 + 3$$$ and check if $$$f(x)$$$ is zero.

http://www.cs.utexas.edu/vlr/papers/mincon.pdf

DP on subset of vertices. Note that 2-edge-connected graph admits an ear decomposition. Thus, the base case is where the graph admits a Hamiltonian cycle. For the inductive case, you split the set into two parts: One for the new ear, other for the minimum biconnected subgraph of remaining sets.

The time complexity is $$$O(3^N \times N^2)$$$ because you enumerate subsets for each subset. My code is pretty slow, and I think it could be done faster, something like $$$O(3^N \times N)$$$.

Randomized solution also works. If we fix the DFS tree of the graph, it is easy to choose minimum number of back-edges to make the graph bi-connected. (It can be done by simple dfs+greedy, in O(N+M)) So, we run the following iteration as many as can: 1. make a random DFS tree of the graph. 2. run greedy on that DFS tree to find minimum edge set. then print the best solution.

Here's my solution:

For each subset of the set of vertices, try finding a simple cycle which contains only those vertices, this can be done in $$$O(n^3 2^n)$$$. If there is a Hamiltonian cycle, then it is the solution. Otherwise, pray that there aren't many subsets of the set of vertices such that they form a cycle, and then do DP on them: I assumed that the solution will always be a union of such cycles. (I didn't prove it but it makes sense). The complexity of this part is $$$O(\frac{n^2 2^n C}{32})$$$ where $$$C$$$ is the number of cycles.

Code: 53156325

Finding the constants of the polynomial by solving linear equations (notice or google that 10^6+3 is a prime so it forms a field Zp) and then brute forcing on the polynomial as the degree is <=10 .

dp[i][0..2] mean haven't multiplied by x, have been multiplied by x, have multiplied x. So we have follow:

dp[i][0]=max(dp[i-1][0]+a[i],a[i])

dp[i][1]=max({dp[i-1][0]+a[i]*x,dp[i-1][1]+a[i]*x,a[i]*x})

dp[i][2]=max({dp[i-1][1]+a[i],dp[i-1][2]+a[i],a[i]})

the answer will equal to one of the dp array

My Segment Tree solution was overkill, as it was a DP problem. Because I'm jobless and narcissistic, I'm explaining my solution anyway.

1. Given numbers $$$a[0] .... a[n-1]$$$, let us calculate $$$upto[i]$$$ and $$$from[i]$$$ which would give you the maximum sum of the subarray the ends at position $$$i$$$, and starts from position $$$i$$$ respectively.

2. $$$upto[i] = max(0, a[i], upto[i-1] + a[i])$$$

3. $$$from[i] = max(0, a[i], from[i+1] + a[i])$$$

4. The first observation is that if we decide to apply the operation from $$$a[L] ... a[R]$$$, and it was optimal then $$$answer = upto[L-1] + (a[L] + ... a[R]) * x + from[R+1]$$$

5. Let us define a function $$$ f(l, r) = upto[l] + (a[l+1] + a[l+2] + ... + a[r-1]) * x + from[r]$$$. The required answer is the maximum of $$$f(l, r)$$$ for $$$l < r$$$. If we attempt to solve this naively by precomputing $$$upto[]$$$ and $$$from[]$$$ and prefix sums, then this can be done in $$$O(n^2)$$$, which is too slow.

6. Let us define $$$g_r(l) = upto[l] + (a[l+1] + .... a[r-1]) * x$$$. Here $$$f(l, r) = g_r(l) + from[r]$$$.

7. Obviously $$$g_{r+1}(l) = g_r(l) + a[r] * x$$$ for $$$l != r-1.$$$

8. If we keep a segment tree that supports range-max queries and range-sum updates to represent $$$g_r$$$ for different values of $$$r$$$. Initally all the values are 0. This represents $$$g_0$$$. For each r = 0 to $$$n-1$$$, do the following:

• calculate the maximum in the subarray right now. One possible $$$answer = max(g_r[0...r-1]) + upto[r]$$$.
• update the values from $$$0 ... r-1$$$ by $$$a[r] * x$$$.
• set $$$g_r[r] = upto[r]$$$.

If you get the boundary conditions right, then you have found an overkill $$$O(n log n)$$$ solution. See my submission 53151609 to know more.

I have applied the same logic ,but its failing in test case number 10. Code Link Can you please find the error.

DP! I passed it! But I TLE at the 3th problem

Try this:

5 0

-1 2 -6 4 -5

When x is 0 your solution fails as you can "erase" a negative subarray by multiplying it by 0 and combine its adjacent maximum subarrays, but that negative subarray is not necessarily minimal.

I solved E using Lagrange Interpolation. Also I have just seen a solution with Berlekamp Massey.

I think you meant $$$O(K^3 + MOD)$$$ since gauss takes $$$O(K^3)$$$.

4 -1
100 -100 90 -101

Try this:
5 -1
-5 -2 6 -3 -5

You are printing 9, but the answer is 14. This case lead me to DP.

Can you explain to me your idea?

for (int i = 0; i < n; i++) {
                if (s[i] == '8' && cnt8 > 0) {
                    s[i] = '?';
                    cnt8--;
                } else if (cnt1 > 0) {
                    s[i] = '?';
                    cnt1--;
                }
            }

What if s[i] == '8' but cnt8==0? If cnt1 is still positive, you will erase an 8

You have to have the GCD of every two consecutive differences. Test: 5 2 1 3 5 6 7 2 3 Your anwser is: Yes 1 1 Correct: No

3 2 2 8 11 2 3

Correct output:
YES 2 2

Your code output: No

You have declared temp as int.

Ну ты и петушара (translate from Russian)

it means they will be disqualified, this has happened before

This is not allowed.
See point no 16 of https://codeforces.com/blog/entry/456

Can you please explain your solution of D?

how did it even get AC.

It is not allowed. The user will be disqualified from the contest.

you should will never stop with undefined behavior while(*****s[j]=='8'*******){ j++; } s.erase(s.begin()+j); ////////////////////////////////// while(******j < s.size()******* and s[j] == '8')++j;

5 -1 -5 -2 6 -3 -5

Ans : 14

How do you find these submissions? Are you running a script for this?

what the moo Bessie why are you asking poor high schoolers to solve your relationship problems with my boy Farmer John when you can code the solutions yourself

Runtime Error is because you didnt use long long.

imaginative

Yes.

All we use when defining Gausssian elimination and Lagrange interpolation and when proving their correctness is that we can add/subtract/multiply numbers and divide by numbers that are not zero and that these numbers follow the standard rules (e.g. distributivity). As such, these algorithms work over any [field](https://en.wikipedia.org/wiki/Field_(mathematics)), not just over the real or rational numbers. It is a well-known fact that Z/pZ with p prime is a field.

Так как n нечётно то на решение это видимо не влияет

4 -1 100 -100 90 -101

answer is 290

Sorry.

Hesitating will be defeated!

Such a notorious coincidence that your submissions were the same on D as well. 53150449 vs 53147765

It is not a question of using third-party code. I do not have time to debate on this issue, I once again carefully looked at and studied all the arguments. My decision remains unchanged. A large number of suspicious coincidences do not leave it to be considered an accident:

• incredible coincidences in solutions on other problems,
• similar code in these programs that is not part of the third-party code.

Probably, there was an unintentional leak, which is also violation. I suggest you both to change passwords and use only https in the future. Good luck.

https://codeforces.com/problemset?order=BY_RATING_ASC&tags=dp