My approach for problem D is quite different. I hope it would be easy to understand.

At first, I build 2 arrays Left(i) and Right(j) that return the maximum sum of a subarray ending at i with Left(i) and starting at j with Right(j). I also have array Sum(i) is sum of all elements from 1 to i.

When we multiply the subarray (l..r), the result in current case is

Left(l-1) + x * (Sum(r) - Sum(l-1)) + Right(r+1).

We can rewrite it by

(Right(r+1) + x * Sum(r)) + (Left(l-1) - x * Sum(l-1)).

With this formula, my solution is a loop for i from 1 to n, take i as the right most of the multiply subarray, get the best value of the left most to update the answer.

See my submission for more details: 53150702

why is E so easy

I can't get my head around as to why greedy won't work for D. If x is non positive, why can't we just find the maximum negative sum and multiply it by x? My code doesn't pass, so it is definitely wrong, but I don't know why.

Is there another way to get the polynomial on problem E? ( Not using Gaussian elimination )

I have an approach for D that is more in the 'style' of Kadane's algorithm. The beautiful part of the array consists of 3 "segments", the 1 part, the X part, and the 1 part again.

Like Kadane's, we loop through each x in the array, maintaining bestK = the largest value of K segments ending in the current x value.

def solve(N, X, A):
    ans = best1 = best2 = best3 = 0
    for a in A:
        best3 = max(0, a, best1 + a, best2 + a, best3 + a)
        best2 = max(0, X*a, best1 + X*a, best2 + X*a)
        best1 = max(0, a, best1 + a)
        ans = max(ans, best1, best2, best3)
    return ans

For problem B, wasn't it enough to simply ignore the last 10 characters of the string and check whether more than half of the remaining characters are equal to '8'?

Can anyone explain editorial's tutorial for problem D in simple and easy way.

I honestly don't get why my solution isn't working. I get WA on the 11th test case, but the output seems fine to me. Am I missing something?

https://codeforces.net/contest/1155/submission/53204105

In problem E, how can we be sure that the value of f(xi) that we use to interpolate the polynomial is actually the value of the polynomial or less than the actual value because of MOD 1e6 + 3

For example, if the polynomial is 1 + (1e6+1)x + x^2, f(0) = 1, f1(1) = 1e6+2, f(2) = 2e6 + 7 MOD 1e6 + 3 = 1. Now the polynomial we interpret will be wrong.

Another approach for problem D

We find the Best subarray ending at ith index and at every index maintain three possible sums 1) x has not yet been used previously nor being used by this element 2) x is being used by this element 3) x was used by some prev segment and hence this element cannot use x

Transitions for calculating ith index results

1) is simple to extend using prev index's result

2) either extend prev index result 1) or 2) should multiply a[i] by x

3) can extend 2) or 3) but should not multiply a[i] by x

https://codeforces.net/contest/1155/submission/53223589

My "solution" for F: first use dp to calculate for each subset of vertices and each pair of vertices if there is a path between those vertices passing through exactly gives subset of vertices, exactly once. From this we can get for each subset if there is a cycle passing through each of them exactly once. Iterate over all subsets and identify those, which have a Hamiltonian cycle, but none of their proper supersets does. Now while we have time left pick a random of those subsets, put all edges from the cycle to the graph, random_shuffle all other edges, add them in order and if this edge is not redundant (i.e their endpoints aren't already in the same biconnected componend) add it. After each iteration check if current solution is better, than best found so far. If it is store it. I saw some other people getting accepted with similar approach. Any idea how to defeat it? 53200092

I've solved problem F with a random way. We can delete some edges in E, and then run Tarjan algorithm to find all strongly connected components. If the graph is bi-connected, the all nodes are supposed to form a single strongly connected component. The number of deletion strategy is 2^|E|, it's too large to try all possible strategies. But we can turn to a greedy way, iterate over each edge, if it's redundant, just delete it. You need run the process several times to get a satisfying result, before each process, shuffle the E at first.

I find a way using greedy and segment tree to solve D You can see my submission 53466247.awoo

Problem E: What would be the problem if the limit was not a prime?? Can anyone explain??

Where can I read about Gaussian elimination method?

For problem D can someone explain me what ecnerwala did to solve it. His code looks quite simple but I am unable to understand it :( . Here's the link to his solution 53141642

what is wrong in this code 1155D

include<bits/stdc++.h>

using namespace std;

define ll long long

define mod 1000000007

define pii pair<ll,ll>

define mp make_pair

define se second

define fi first

define pb push_back

ll max(ll a,ll b) { if(a>b) return a; return b;

}

int main() { ll n,x; cin>>n>>x; ll a[10000007]={0}; for(ll i=0;i<n;i++) { cin>>a[i];

}
ll dp[100005][3];
dp[0][0]=max(a[0],0);
dp[0][1]=max(a[0]*x,0);
dp[0][2]=max(a[0],0);
for(ll i=1;i<n;i++)
{
    dp[i][0]=max(0,dp[i-1][0]+a[i]);
    dp[i][0]=max(dp[i][0],dp[i][2]+a[i]);
    dp[i][2]=max(dp[i-1][1]+a[i],dp[i][0]);
    dp[i][2]=max(dp[i-1][2]+a[i],dp[i][2]);
    dp[i][2]=max(0,dp[i][2]);

    dp[i][1]=max(dp[i-1][0]+a[i]*x,dp[i-1][1]+a[i]*x);
    dp[i][1]=max(0,dp[i][1]);
}
ll maxi=0;
for(ll i=0;i<n;i++)
{
    for(ll j=0;j<3;j++)
    {
    // cout<<dp[i][j]<<" ";
    if(maxi<dp[i][j])
    maxi=dp[i][j];
    }
//  cout<<endl;
}

cout<<maxi;

}

1155D - Beautiful Array — My solution is similar to alexwice and arajatchauhan813, you just have a dp table of n * 3 in which you have:

dp[i][1]:the maximum sum without multiplying until i

dp[i][2]:the maximum sum up to i having already multiplied and without multiplying from i

dp[i][3]:the maximum sum up i multiplying a piece that ends in i

Then :

    for(int i=0;i<n;i++){

        dp[i][1]=max(0ll,arr[i]);

        dp[i][2]=max(0ll,arr[i]);

        dp[i][3]=max(0ll,arr[i]*x);

        if(i==0)continue;

        dp[i][1]=max({ dp[i][1] , arr[i]+dp[i-1][1] });

        dp[i][2]=max({ dp[i][2] , arr[i]+dp[i-1][2] , arr[i]+dp[i-1][3]});

        dp[i][3]=max({ dp[i][3] , dp[i-1][3]+(arr[i]*x) , dp[i-1][1]+(arr[i]*x)});

    }

So you only need visit the table and find the greatest solution

There is my solution 55211386